Robust separation of finite sets via quadratics

Given a pair of finite disjoint sets A and B in Rn, a fundamental problem with many important applications is to efficiently determine a non-trivial, yet ‘simple’, function f(x) belonging to a prespecified family F which separates these sets when they are separable, or ‘nearly’ separates them when they are not. The most common class of functions F addressed to data are linear (because linear programming is often a convenient and efficient tool to employ both in determining separability and in generating a suitable separator). When the sets are not linearly separable, it is possible that the sets are separable over a wider class F of functions, e.g., quadratics. Even when the sets are linearly separable, another function may ‘better’ separate in the sense of more accurately predicting the status of points outside of A∪B. We define a ‘robust’ separator f as one for which the minimum Euclidean distance between A∪B and the set View the MathML source is maximal. In this paper we focus on robust quadratic separators and develop an algorithm using sequential linear programming to produce one when one exists. Numerical results are presented.