Robust separation of finite sets via quadratics

Given a pair of finite disjoint sets A and B in R", 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 boolean ORB. We define a 'robust' separator f as one for which the minimum Euclidean distance between A boolean ORB and the set S = {x epsilon R(n): f(x)5 = 0} 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.