Abstract

Theorems on the separation of convex sets by hyperplanes are among the basic tools of convex analysis and mathematical programming. The main results of the present paper are new (and in a sense best possible) separation theorems in the setting of a finite-dimensional vector space 𝕏 over an archimedean ordered field 𝔽. There is an emphasis on the differences between the case in which 𝔽 is the real field ℝ and that in which 𝔽 is a proper subfield of ℝ. The rational field ℚ is of special importance because of its relevance to computation. A new theorem for Rd\mathbb{R}^d concerns the free separation of two convex sets, where this means that there is a separating hyperplane H such that all sufficiently small perturbations of H still separate the two sets. In a sense that is made precise, this is the unique maximal theorem for free separation in Rd\mathbb{R}^d. A theorem for general 𝕏 implies that if a proper convex subset C of 𝕏 is s-closed, then C is an intersection of open halfspaces. (The condition of s-closedness, defined in the text, is satisfied by all closed convex subsets of Rd\mathbb{R}^d. In an arbitrary 𝕏, it is satisfied by polyhedra and by many other convex sets, but when 𝔽 ≠ ℝ it is stronger than mere closedness.) There is also a study of conditions under which an 𝔽-valued convex function on a convex subset C of 𝕏 is the supremum of a collection of 𝔽-valued affine functions on 𝕏. (In Rd\mathbb{R}^d, this leads to the usual subdifferentiability of convex functions.) The s-closedness of C is again a relevant condition. In conjunction with the relevance of s-closedness to line-searches, and the related fact that the standard theorems on extremal structure of convex sets in Rd\mathbb{R}^d extend to s-closed subsets of Fd\mathbb{F}^d, this suggests that results on the behavior of s-closed sets may eventually provide useful tools in the development of genuinely rational optimization algorithms.

Author information

Contact details are reproduced from the original publication and may be historical.

Peter Gritzmann

Technische Universität München, Zentrum f. Mathematik, 80333 München, Germany.

Victor Klee

University of Washington, Department of Mathematics, Box 354350, Seattle, WA 98195-4350, USA

Keywords

  • archimedean field
  • finite-dimensional vector space
  • convex set
  • s-closed
  • separation
  • support
  • convex function
  • epigraph
  • optimization

References

  1. I. Adler, P. A. Beling: Polynomial algorithms for LP over a subring of the algebraic integers with applications to LP with circulant matrices, Math. Programming B 57 (1992) 121-143.https://doi.org/10.1007/BF01581077Google Scholar
  2. I. Adler, P. A. Beling: Polynomial algorithms for linear programming over the algebraic numbers, Algorithmica 12 (1994) 436-457.https://doi.org/10.1007/BF01188714Google Scholar
  3. A. Auslender, P. Coutat: On closed convex sets without boundary rays, Set-Valued Analysis 2 (1994) 19-33.https://doi.org/10.1007/BF01027090Google Scholar
  4. P. C. P. Carvalho, L. E. Trotter, Jr.: An abstract linear duality model, Math. Operations Res. 14 (1989) 639-663.https://doi.org/10.1287/moor.14.4.639Google Scholar
  5. T. R. Deumlich, K. H. Elster, R. Nehse: Recent results on the separation of convex sets, Math. Operationsforsch. Statist. Ser. Optim. 9 (1978) 273-294.https://doi.org/10.1080/02331937808842491Google Scholar
  6. B. C. Eaves, U. G. Rothblum: Relationships of properties of piecewise affine maps over ordered fields, Linear Algebra Appl. 132 (1990) 1-63.https://doi.org/10.1016/0024-3795(90)90052-EGoogle Scholar
  7. B. C. Eaves, U. G. Rothblum: Dines-Fourier-Motzkin quantifier elimination and an application of corresponding transfer principles over ordered fields, Math. Programming A 53 (1992) 307-321.https://doi.org/10.1007/BF01585709Google Scholar
  8. D. Gale, V. Klee: Continuous convex sets, Math. Scand. 7 (1959) 379-391.https://doi.org/10.7146/math.scand.a-10585Google Scholar
  9. B. R. Gelbaum, J. M. H. Olmsted: Counterexamples in Analysis, Holden-Day, San Francisco, 1964.Google Scholar
  10. V. Klee: Extremal structure of convex sets. II, Math. Zeitschr. 69 (1958) 90-104.https://doi.org/10.1007/BF01187394Google Scholar
  11. V. Klee: Asymptotes and projections of convex sets, Math. Scand. 8 (1960) 363-370.https://doi.org/10.7146/math.scand.a-10618Google Scholar
  12. V. Klee: Extreme points of convex sets without completeness of the scalar field, Mathematika 10 (1964) 59-63.https://doi.org/10.1112/S002557930000348XGoogle Scholar
  13. V. Klee: Maximal separation theorems for convex sets, Trans. Amer. Math. Soc. 134 (1968) 133-147.https://doi.org/10.1090/S0002-9947-1968-0235457-9Google Scholar
  14. V. Klee: Separation and support properties of convex sets - a survey, In: Control Theory and the Calculus of Variations (ed. by V. Balakrishnan), Academic Press, New York (1969) 235-303.Google Scholar
  15. N. Megiddo: Towards a genuinely polynomial algorithm for linear programming, SIAM J. Comput. 12 (1983) 347-353.https://doi.org/10.1137/0212022Google Scholar
  16. N. Megiddo: On the complexity of linear programming, In: Advances in Economic Theory: Fifth World Congress (ed. by T. Bewley), Cambridge Univ. Press, Cambridge (1987) 225-268.https://doi.org/10.1017/CCOL0521340446.006Google Scholar
  17. N. Megiddo: Linear programming, Annual Review of Computer Science 2 (1987) 119-145.https://doi.org/10.1146/annurev.cs.02.060187.001003Google Scholar
  18. S. Onn, L. E. Trotter: On separation in vector spaces over ordered fields, manuscript, 1992, Department of Operations Research, Cornell University, Ithaca, N.Y.Google Scholar
  19. R. T. Rockafellar: Convex Analysis, Princeton Univ. Press, Princeton, N.J., 1970.https://doi.org/10.1515/9781400873173Google Scholar
  20. A. Schrijver: Theory of Linear and Integer Programming, Wiley, New York, 1986.Google Scholar
  21. S. Strascewicz: Über exponierte Punkte abgeschlossener Punktmengen, Fund. Math. 24 (1935) 139-143.https://doi.org/10.4064/fm-24-1-139-143Google Scholar
  22. S. Warner: Classical Modern Algebra, Prentice Hall, Eglewood Cliffs, N.J., 1971.Google Scholar
  23. G. Ziegler: Lectures on Polytopes, Springer-Verlag, New York, 1994.https://doi.org/10.1007/978-1-4613-8431-1_2Google Scholar

Suggested citation

P. Gritzmann, V. Klee. “Separation by Hyperplanes in Finite-Dimensional Vector Spaces Over Archimedean Ordered Fields.” Journal of Convex Analysis 5 (1998), No. 2, 279–301. https://doi.org/10.68381/jca05-20

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 1998. Rights now held by Banach Press.