Set separation problems and global optimization

✍ Scribed by James E. Falk; Yelena Dandurova; Lana Yeganova

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 372 KB
• Volume: 47
• Category: Article
• ISSN: 0362-546X
• DOI: 10.1016/s0362-546x(01)00316-9

✦ Synopsis

Given a pair of finite, disjoint sets and in , a fundamental problem with numerous applications is to find a simple function () defined over which separates the sets in the sense that () > 0 for all ∈ and () < 0 for all ∈ . This can always be done (e.g., with the piecewise linear function defined by the Voronoi partition implied by the points in ⋃ ). However typically one seeks a linear (or possibly a quadratic) function if possible, in which case we say that and are linearly (quadratically) separable. If and 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 and 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.