V.V. Gorokhovik. Step-affine functions, half-spaces, and separation of convex sets with applications to convex optimization problems ... P. 51-70

We present the definition of step-affine functions defined on a real vector space and establish the duality between step-affine functions and half-spaces, i.e., convex sets whose complements are convex as well. Using this duality, we prove that two convex sets are disjoint if and only if they are separated by some step-affine function. This criterion is actually the analytic version of the Kakutani–Tukey criterion of the separation of disjoint convex sets by half-spaces. As applications of these results, we derive a minimality criterion for solutions of convex vector optimization problems considered in real vector spaces without topology and an optimality criterion for admissible points in classical convex programming problems not satisfying the Slater regularity condition.

Keywords: step-affine functions, half-spaces, separation of convex sets, convex vector optimization problems, convex programming

Received November 11, 2019

Revised January 10, 2020

Accepted January 14, 2020

Funding Agency: This work was supported by the National Program for Scientific Research of the Republic of Belarus for 2016–2020 “Convergence 2020” (project no. 1.4.01).

Valentin Vikent’evich Gorokhovik, Dr. Phys.-Math. Sci., Corresponding Member of NAS of Belarus, Prof., Institute of Mathematics, The National Academy of Sciences of Belarus, Minsk, 220072 Belarus, e-mail: gorokh@im.bas-net.by

REFERENCES

1.  Raikov D.A. Vector Spaces. Groningen: Noordhoff, 1965, 190 p. Original Russian text published in Raikov D.A. Vektornye prostranstva, Moscow: Fizmatgiz Publ., 1962, 212 p.

2.   Klee V. Separation and support properties of convex sets. A survey. In: Control Theory and the Calculus of Variations, A.V. Balakrishnan (ed), N Y: Acad. Press, 1969, pp. 235–303. ISBN: 0120769530 .

3.   Kakutani S. Ein Beweis des Satzen von M. Eidelheit Јuber konvexe Mengen. Proc. Imp. Acad. Tokio, 1938, vol. 14, pp. 93–94. doi: 10.3792/pia/1195579980 

4.   Tukey J.W. Some notes on the separation of convex sets. Portugaliae Math., 1942, vol. 3, no. 2, pp. 95–102.

5.   Hille E., Phillips R.S. Functional analysis and semi-groups. Coll. Publ., vol. 31, Providence: AMS, 1957, 810 p. ISBN: 0821810316 . Translated to Russian under the title Funktsional’nyi analiz i polugruppy. Moscow: I L Publ., 1962, 830 p.

6.   Martinez-Legaz J.-E., Singer I. The structure of hemispaces in $\mathbb{R}^n$. Linear Algebra Appl., 1988, vol. 110, pp. 117–179. doi: 10.1016/0024-3795(83)90135-0 

7.   Gorokhovik V.V. Minimality and quasiminimality in ordered vector spaces. Dokl. Akad. Nauk BSSR, 1981, vol. 25, no. 8, pp. 685–688 (in Russian) .

8.   Gorokhovik V.V. Vypuklye i negladkie zadachi vektornoi optimizatsii [Convex and nonsmooth problems of vector optimization]. Minsk: Navuka i Tekhnika Publ., 1990, 240 p. ISBN: 5-4343-00519-5 .

9.   Gorokhovik V.V., Semenkova E.A. Step-linear functions in finite-dimensional vector spaces. Definition, properties and their relation to half-spaces. Dokl. Akad. Nauk Belarusi, 1997, vol. 41, no. 5, pp. 10–14 (in Russian) .

10.   Gorokhovik V.V., Semenkova E.A. Classification of semispaces according to their types in infinite-dimensional vector spaces. Math. Notes, 1998, vol. 64, no. 2, pp. 164–169. doi: 10.1007/BF02310300 

11.   Gorokhovik V.V., Shinkevich E.A. Theorems on the separation of convex sets by step-linear functions and their applications to convex optimization problems. In: Nonlinear analysis and applications, Tr. Inst. Mat. Nats. Akad. Nauk Belarusi, vol. 1. Minsk: Natl. Akad. Nauk Belarusi, 1998, pp. 58–85 (in Russian) .

12.   Gorokhovik V.V., Shinkevich E.A. Analytic representation of infinite-dimensional half-spaces by step-affine functions. In: Nonlinear analysis and related problems, Tr. Inst. Mat. Nats. Akad. Nauk Belarusi, vol. 2. , Minsk: Natl. Akad. Nauk Belarusi, 1999, pp. 63–72 (in Russian) 

13.   Gorokhovik V.V., Shinkevich E.A. Geometric structure and classification of infinite-dimensional halfspaces. In: Algebraic Analysis and Related Topics. Banach Center Publications, vol. 53. Warsaw: Institute of Mathematics PAN, 2000, pp. 121–138.

14.   Martinez-Legaz J.-E., Vicente-Perez J. Lexicographical representation of convex sets. J. Convex Analysis, 2012, vol. 19, no. 2, pp. 485–496.

15.   Kucuk M., Soyertem M., Kucuk Ya. On constructing total orders and solving vector optimization problems with total orders. J. Global Optim., 2011, vol. 50, no. 2, pp. 235–247. doi: 10.1007/s10898-010-9576-y 

16.   Kucuk M., Soyertem M., Kucuk Ya. The generalization of total ordering cones and vectorization to separable Hilbert spaces. J. Math. Anal. Appl., 2012, vol. 389, no. 2, pp. 1344–1351. doi: 10.1016/j.jmaa.2012.01.017 

17.   Klee V. The structure of semispaces. Math. Scand., 1956, vol. 4, pp. 54–64. doi: 10.7146/math.scand.a-10455 

18.   Klee V. Maximal separation theorems for convex sets. Trans. Amer. Math. Soc., 1968, vol. 134, no. 1, pp. 133–147. doi: 10.1090/S0002-9947-1968-0235457-9 

19.   Leichtweiss K. Konvexe Mengen. Berlin: Springer, 1980, 330 p. ISBN: 978-3-540-09071-7 . Translated to Russian under the title Vypuklye mnozhestva. Moscow: Nauka Publ., 1985, 335 p.

20.   Semenkova E.A. On analytical representation of half-spaces in finite-dimensional vector spaces. Izv. Akad. Nauk Belarusi, Ser. Fiz.-Mat. Nauk, 1996, no. 2, pp. 35–40 (in Russian) .

21.   Hammer P.C. Maximal convex sets. Duke Math. J., 1955, vol. 22, no. 1, pp. 103–106. doi: 10.1215/S0012-7094-55-02209-2 

22.   Lassak M. Convex half-spaces. Fund. Math., 1984, vol. 120, no. 1, pp. 7–13. doi: 10.4064/fm-120-1-7-13 .

23.   Lassak M.A., Proszyński A. Translate-inclusive sets, orderings and convex halfspaces. Bull. Polish Acad. Sci. Math., 1986, vol. 34, no. 3–4, pp. 195–201.

24.   Martinez-Legaz J.-E., Singer I. Lexicographical separation in $\mathbb {R}^n$. Linear Algebra Appl., 1987, vol. 90, pp. 147–163. doi: 10.1016/0024-3795(87)90312-0 

25.   Alexandroff P.S. Einfuhrung in die Mengenlehre und in die allgemeine Topologie. (Introduction to set theory and to general topology). Berlin: VEB Deutscher Verlag der Wissenschaften, 1984, 336 p. Original Russian text published in Aleksandrov P.S., Vvedenie v teoriyu mnozhestv i obshchuyu topologiyu, Moscow: Nauka Publ., 1977, 368 p.

26.   Kolmogorov A.N., Fomin S.V. Elements of the theory of functions and functional analysis. USA: Martino Fine Books, 2012, 280 p. ISBN: 1614273049 . Original Russian text published in Kolmogorov A.N., Fomin S.V., Elementy teorii funktsii i funktsional’nogo analiza, Moscow: Nauka Publ., 1981, 544 p.

Cite this article as: V.V. Gorokhovik. Step-affine functions, half-spaces, and separation of convex sets with applications to convex optimization problems, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2020, vol. 26, no. 1, pp. 51–70; Proceedings of the Steklov Institute of Mathematics (Suppl.), 2021, Vol. 313, Suppl. 1, pp. S83–S99.