On OM-decomposable sets
- PDF / 487,567 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 43 Downloads / 228 Views
On OM-decomposable sets A. N. Iusem1
· M. I. Todorov2
Received: 10 May 2017 / Revised: 11 July 2017 / Accepted: 12 July 2017 © SBMAC - Sociedade Brasileira de Matemática Aplicada e Computacional 2017
Abstract We introduce and study the family of sets in a finite-dimensional Euclidean space which can be written as the Minkowski sum of an open, bounded, and convex set and a closed convex cone. We establish several properties of the class of such sets, called OM-decomposable, some of which extend related properties holding for the class of Motzkin decomposable sets (i.e., those for which the convex and bounded set in the decomposition is requested to be closed, hence compact). Keywords Motzkin decomposable sets · Convex sets · Convex cones Mathematics Subject Classification 52A07 · 54F65
1 Introduction It has been known at least since the mid nineteenth century that the set of solutions of a system of linear equations admits an explicit representation, as the sum of a particular solution plus an arbitrary linear combination of the vectors forming a basis of the linear subspace consisting of the solutions of the associated homogeneous system. The corresponding result for systems
Communicated by José Mario Martínez. The work of A. N. Iusem was partially supported by CNPq Grant no. 301280/86. The work of M. I. Todorov was partially supported by Mineco (Spain) and ERDF (EU), Grant MTM2014-59179-C2-1-P, and Sistema Nacional de Investigadores, México. M. I. Todorov: On leave IMI-BAS.
B
A. N. Iusem [email protected]
1
Instituto de Matématica Pura e Aplicada (IMPA), Estrada Dona Castorina 110, Rio de Janeiro, RJ CEP 22460-320, Brazil
2
Department of Actuary and Mathematics, Universidad de las Américas, Cholula, Puebla, Mexico
123
A. N. Iusem, M. I. Todorov
of linear inequalities is much more recent. In his doctoral thesis Motzkin (1936), proved that the set F of solutions of such a system consists of the sums of convex combinations of a finite set of vectors (the vertices of F) and nonnegative combinations of another finite set (the extreme rays of F). In modern terminology, every (possibly unbounded) convex polyhedron is the Minkowski sum of a convex and compact polytope and a closed and convex cone. This characterization turned out to be quite useful for establishing finite convergence of pivotal algorithms for Linear Programming (e.g., the Simplex Method, see Dantzig 1963), and more specifically, for Quadratic Programming, like Lemke’s method, see Cottle et al. (1992). Motzkin’s representation result suggested the consideration of a class of convex sets more general than polyhedra, resulting from removing the “linear” nature of these, while keeping the decomposition aspect. More precisely, those sets in Rn can be written as the Minkowski sum of a compact and convex set and a closed and convex cone. Such sets were introduced in Goberna et al. (2010a), where they were called Motzkin decomposable, or Mdecomposable, in short, and further studied in Goberna et al. (2010b, 2013), together with the M-decomposable functi
Data Loading...
