Technische Universität München, Zentrum f. Mathematik, 80333 München, Germany, gritzman@mathematik.tu-muenchen.de, and University of Washington, Department of Mathematics, Box 354350, Seattle, WA 98195-4350, USA, klee@math.washington.edu
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 $\mathbb{X}$ over an archimedean ordered field $\mathbf{F}$. There is an emphasis on the differences between the case in which $\mathbf{F}$ is the real field $\mathbb{R}$ and that in which $\mathbf{F}$ is a proper subfield of $\mathbb{R}$. The rational field $\mathbb{Q}$ is of special importance because of its relevance to computation. A new theorem for $\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 $\mathbb{R}^d$. A theorem for general $\mathbb{X}$ implies that if a proper convex subset $C$ of $\mathbb{X}$ 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 $\mathbb{R}^d$. In an arbitrary $\mathbb{X}$, it is satisfied by polyhedra and by many other convex sets, but when $\mathbf{F}\ne\mathbb{R}$ it is stronger than mere closedness.) There is also a study of conditions under which an $\mathbf{F}$-valued convex function on a convex subset $C$ of $\mathbb{X}$ is the supremum of a collection of $\mathbf{F}$-valued affine functions on $\mathbb{X}$. (In $\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 $\mathbb{R}^d$ extend to s-closed subsets of $\mathbf{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.
Keywords: archimedean field, finite-dimensional vector space, convex set, s-closed, separation, support, convex function, epigraph, optimization
Classification (MSC2000): 46A55, 52A07, 52A20, 52A41, 12J15, 52B11, 52B55, 90C25, 90C30
Full text of the article: