Set Containment Characterization
Abstract
Characterization of the containment of a polyhedral set in a closed halfspace, a key factor in
generating knowledge-based support vector machine classi ers [7], is extended to the following:
(i) Containment of one polyhedral set in another.
(ii) Containment of a polyhedral set in a reverse-convex set de ned by convex quadratic constraints.
(iii) Containment of a general closed convex set, de ned by convex constraints, in a reverse-convex
set de ned by convex nonlinear constraints.
The rst two characterizations can be determined in polynomial time by solving m linear programs
for (i) and m convex quadratic programs for (ii), where m is the number of constraints de ning the
containing set. In (iii), m convex programs need to be solved in order to verify the characterization,
where again m is the number of constraints de ning the containing set. All polyhedral sets, like
the knowledge sets of support vector machine classi ers, are characterized by the intersection of a
nite number of closed halfspaces.
Subject
quadratic programming
linear programming
knowledge-based classifier
set containment
Permanent Link
http://digital.library.wisc.edu/1793/64310Type
Technical Report
Citation
01-10