Content area
Full Text
J Optim Theory Appl (2011) 148: 550570
DOI 10.1007/s10957-010-9767-1
Published online: 8 December 2010 Springer Science+Business Media, LLC 2010
Abstract We propose a new approach to the strict separation of convex polyhedra. This approach is based on the construction of the set of normal vectors for the hyperplanes, such that each one strict separates the polyhedra A and B. We prove the necessary and sufcient conditions of strict separability for convex polyhedra in the Euclidean space and present its applications in optimization.
Keywords Polyhedron Separating hyperplane Normal vector Supporting
hyperplane Thickness of the separation margin Distance between the polyhedra
1 Introduction
In the theory of extremal problems and its applications, the so-called strict separability theorems for disjoint convex sets play a fundamental role. Both theorems describing conditions of separability (see [15]) and algorithms (see [613]) computationally realizing the separation represent a particular interest. The review of a wide range of algorithms can be found in [8].
Usually the proof of the theorems on separability of convex sets A and B (A B = ) in Euclidean space
Rn (for instance, see [14, c. 310]; [15, p. 201]; [16, p. 72]; [17, p. 26]) is reduced to the construction of a unique normal vector for the separating hyperplanes: d = PAB(0), where d is the projection of the origin of
the space onto the set A B.
Communicated by V.F. Demyanov.
Z.R. Gabidullina ( )
Department of Computing Mathematics and Cybernetics, Chair of Economic Cybernetics, Kazan (Volga Region) Federal University, 18, Kremljovskaja street, Kazan 420008, Russiae-mail: mailto:[email protected]
Web End [email protected]
Z.R. Gabidullinae-mail: mailto:[email protected]
Web End [email protected]
A Theorem on Strict Separability of Convex Polyhedra and Its Applications in Optimization
Z.R. Gabidullina
J Optim Theory Appl (2011) 148: 550570 551
In this paper, a necessary and sufcient conditions of strict separability of convex polyhedra are proved by the construction of the set of normal vectors to hyperplanes such that each one strictly separates the sets A and B. The proposed approach is characterized by the variability of the choice of the separating hyperplane. This allows one to separate disjoint convex polyhedra by margin with different thickness, including, the margin with maximum thickness determined by the distance between polyhedra. It should be noted that, frequently, for solving many...