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 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).

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.

Relationships between Borda voting and Zermelo ranking.

There are many situations wherein a group of individuals (e.g., voters, experts, sports writers) must produce an ordered list of 'best' alternatives selected from a given group of alternatives (e.g., candidates, proposals, sports teams). Two long established mechanisms that have been used for this task are 'Zermelo's Ranking Method' (1929) and 'Borda's Voting Scheme' (1781). The main purpose of this paper is to point out that they are, under certain common circumstances, identical. We then show that Zermelo's Method can be used in situations that Borda's Method is not designed to handle.