Set Separation Problems and Global Optimization.

Given a pair of finite, disjoint sets A and B in Rn , a fundamental problem with numerous applications is to find a simple function f(x) defined over Rn 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.

Robust Separation of Multiple Sets.

Given K finite disjoint sets {Ak }, k = 1, …, K in Euclidean n-space, a general problem with numerous applications is to find K simple nontrivial functions fk (x) which separate the sets {Ak } in the sense that fk (a) ≤ fi (a) for all a ⊂ Ak and i ≠ k, k = 1, …, K. This can always be done (e.g., with the piecewise linear function obtained by the Voronoi Partition defined for the points in [Formula: see text]). However, typically one seeks linear functions fk (x) if possible, in which case we say the sets {Ak } are piecewise linear separable. If the sets are separable in a linear sense, there are generally many such functions that separate, in which case we seek a 'best' (in some sense) separator that is referred as a robust separator. If the sets are not separable in a linear sense, we seek a function which comes as close as possible to separating, according to some criterion.

Robust Set Separation Via Exponentials.

Given a pair of finite disjoint sets A and B in Euclidean n-space, a fundamental problem with numerous applications is to efficiently determine a hyperplane H(ω, γ) which separates these sets when they are separable, or 'nearly' separates them when they are not. We seek a hyperplane that separates them in the sense that a measure of the Euclidean distance between the separating hyperplane and all of the points is as large as possible. This is done by 'weighting' points relative to A ∪ B according to their distance to H(ω, γ), with the closer points getting a higher weight, but still taking into account the points distant from H(ω, γ). The negative exponential is chosen for that purpose. In this paper we examine the optimization problem associated with this set separation problem and characterize it (convex or non-convex).