Set Separation Problems and Global Optimization

Given a pair of finite, disjoint sets A and B in Rⁿ , a fundamental problem with numerous applications is to find a simple function f(x) defined over Rⁿ which separates the sets in the sense that f(a) > 0 for all a ∈ A and f(b) < 0 for all b ∈ B. This can always be done (e.g., with the piecewise linear function defined by the Voronoi partition implied by the points in A ⋃ B). However typically one seeks a linear (or possibly a quadratic) function f if possible, in which case we say that A and B are linearly (quadratically) separable. If A and B are separable in a linear or quadratic sense, there are generally many such functions which separate. In this case we seek a 'robust' separator, one that is best in a sense to be defined. When A and B are not separable in a linear or quadratic sense we seek a function which comes as close as possible to separating, according to some well defined criterion. In this paper we examine the optimization problems associated with the set separation problem, characterize them (convex or non-convex) and suggest algorithms for their solutions.