Separation by hyperplanes in finite-dimensional vector spaces over archimedean ordered fields

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 double-struck X sign over an archimedean ordered field double-struck F sign. There is an emphasis on the differences between the case in which double-struck F sign is the real field ℝ and that in which double-struck F sign is a proper subfield of ℝ. The rational field ℚ is of special importance because of its relevance to computation. A new theorem for ℝ^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 ℝ^d. A theorem for general double-struck X sign implies that if a proper convex subset C of double-struck X sign 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 ℝ^d. In an arbitrary double-struck X sign, it is satisfied by polyhedra and by many other convex sets, but when double-struck F sign ≠ ℝ it is stronger than mere closedness.) There is also a study of conditions under which an double-struck F sign-valued convex function on a convex subset C of double-struck X sign is the supremum of a collection of F-valued affine functions on double-struck X sign. (In ℝ^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 ℝ^d extend to s-closed subsets of double-struck F sign^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.