A Linear Separability Criterion for Sets of Euclidean Space
- PDF / 845,264 Bytes
- 27 Pages / 439.37 x 666.142 pts Page_size
- 9 Downloads / 253 Views
A Linear Separability Criterion for Sets of Euclidean Space Z.R. Gabidullina
Received: 6 May 2011 / Accepted: 8 August 2012 © Springer Science+Business Media, LLC 2012
Abstract We prove new theorems which describe a necessary and sufficient condition for linear (strong and non-strong) separability and inseparability of the sets in a finite-dimensional Euclidean space. We propose a universal measure for the thickness of the geometric margin (both the strong separation margin (separator) and the margin of unseparated points (pseudo-separator)) formed between the parallel generalized supporting hyperplanes of the two sets which are separated. The introduced measure allows comparing results of linear separation obtained by different techniques for both linearly separable and inseparable sets. An optimization program whose formulation provides a maximum thickness of the separator for the separable sets is considered. When the sets are inseparable, the same solver is guaranteed to construct a pseudo-separator with a minimum thickness. We estimate the distance between the convex and closed sets. We construct a cone of generalized support vectors for hyperplanes, each one of which linearly separates the considered sets. The interconnection of the problem of different types of linear separation of sets with some related problems is studied. Keywords Cone of support vectors · Distance between the sets · Separator · Pseudo-separator · Thickness of the separator (pseudo-separator) · Generalized supporting hyperplane · Generalized support vector · Projection
Communicated by Gianni Di Pillo. Z.R. Gabidullina () Institute of Computational Mathematics and Information Technologies, Department of Economic Cybernetics, Kazan Federal University, 18, Kremljovskaja street, Kazan 420008, Russia e-mail: [email protected] Z.R. Gabidullina e-mail: [email protected]
J Optim Theory Appl
1 Introduction Due to a large number of practical applications, the theory of the linear separation of sets is of an increasing interest. All applications, which can be combined under the term mathematical diagnostics, were reviewed, for instance, in [1]. Thanks to the close relationship of the issues, both working out the criterion on linear separability of the sets and developing its realizing solvers [2–7] deserve a particular interest. The strict connection of the sets separation with the optimality conditions also represents the area of great theoretical interest [8]. Let us note that, in [7], an approach to the strong separation of the convex polyhedra, which is based on the construction of the set of normal vectors for the hyperplanes each one of which strongly separates two polyhedra, has been proposed. Unlike the above-mentioned paper, here we introduce and prove a linear separability criterion for two sets of the Euclidean space. The main distinction of our criterion from the previously known ones [2] is that it allows us to distinguish the non-degenerate and degenerate cases of linear separability. This criterion also allows discriminati
Data Loading...
