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.