Robust separation of finite sets via quadratics

Robust separation of finite sets via quadratics

0.00 Avg rating0 Votes
Article ID: iaor20014223
Country: United Kingdom
Volume: 28
Issue: 6
Start Page Number: 537
End Page Number: 561
Publication Date: May 2001
Journal: Computers and Operations Research
Authors: ,
Keywords: programming: linear
Abstract:

Given a pair of finite disjoint sets A and B in Rn, 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 AB. We define a ‘robust’ separator f as one for which the minimum Euclidean distance between AB and the set S = {x ∈ ℛn: f(x) = 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.

Reviews

Required fields are marked *. Your email address will not be published.