Step-Affine Functions, Halfspaces, and Separation of Convex Sets with Applications to Convex Optimization Problems

V. V. Gorokhovik

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 26 (2020) no. 1, pp. 51-70

Résumé

We introduce the class of step-affine functions defined on a real vector space and establish the duality between step-affine functions and halfspaces, 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 halfspaces. 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.

Détail

Keywords: step-affine functions, halfspaces, separation of convex sets, convex vector optimization problems, convex programming.

Bibliographie

[1] Raikov D.F., Vektornye prostranstva, Fizmatgiz, M., 1962, 212 pp.

[2] Klee V., “Separation and support properties of convex sets. A survey”, Control Theory and the Calculus of Variations, ed. A.V. Balakrishnan, Acad. Press, N Y, 1969, 235–303

[3] Kakutani S., “Ein Beweis des Satzen von M. Eidelheit uber konvexe Mengen”, Proc. Imp. Acad. Tokio, 14 (1938), 93–94 | DOI | MR

[4] Tukey J.W., “Some notes on the separation of convex sets”, Portugaliae Math., 3:2 (1942), 95–102 | MR

[5] Khille E., Fillips R., Funktsionalnyi analiz i polugruppy, IL, M., 1962, 830 pp.

[6] Martinez-Legaz J.-E., Singer I., “The structure of hemispaces in $\mathbb {R}^n$”, Linear Algebra Appl., 110 (1988), 117–179 | DOI | MR | Zbl

[7] Gorokhovik V.V., “Minimalnost i kvaziminimalnost v uporyadochennykh vektornykh prostranstvakh”, Dokl. AN BSSR, 25:8 (1981), 685–688 | MR | Zbl

[8] Gorokhovik V.V., Vypuklye i negladkie zadachi vektornoi optimizatsii, Nauka i Tekhnika, Minsk, 1990, 240 pp.

[9] Gorokhovik V.V., Semenkova E.A., “Stupenchato-lineinye funktsii v konechnomernykh vektornykh prostranstvakh. Opredelenie, svoistva i ikh svyaz s poluprostranstvami”, Dokl. AN Belarusi, 41:5 (1997), 10–14 | MR | Zbl

[10] Gorokhovik V.V., Semenkova E.A., “Klassifikatsiya poluprostranstv po tipam v beskonechnomernykh vektornykh prostranstvakh”, Mat. zametki, 64:2 (1998), 191–198 | DOI | Zbl

[11] Gorokhovik V.V., Shinkevich E.A., “Teoremy ob otdelimosti vypuklykh mnozhestv stupenchato-lineinymi funktsiyami i ikh prilozheniya k vypuklym zadacham optimizatsii”, Nelineinyi analiz i prilozheniya, Trudy Instituta matematiki, 1, Natsionalnaya Akademiya nauk Belarusi, 1998, 58–85 | MR | Zbl

[12] Gorokhovik V.V., Shinkevich E.A., “Analiticheskoe predstavlenie beskonechnomernykh poluprostranstv stupenchato-affinnymi funktsiyami”, Nelineinyi analiz i smezhnye voprosy, Trudy Instituta matematiki, 2, Natsionalnaya Akademiya nauk Belarusi, 1999, 63–72 | MR

[13] Gorokhovik V.V., Shinkevich E.A., “Geometric structure and classification of infinite-dimensional halfspaces”, Algebraic Analysis and Related Topics, Banach Center Publications, 53, Institute of Mathematics PAN, Warsaw, 2000, 121–138 | MR | Zbl

[14] Martinez-Legaz J.-E., Vicente-Perez J., “Lexicographical representation of convex sets”, J. Convex Analysis, 19:2 (2012), 485–496 | MR | Zbl

[15] Kucuk M., Soyertem M., Kucuk Ya., “On constructing total orders and solving vector optimization problems with total orders”, J. Global Optim., 50:2 (2011), 235–247 | DOI | MR | Zbl

[16] Kucuk M., Soyertem M., Kucuk Ya., “The generalization of total ordering cones and vectorization to separable Hilbert spaces”, J. Math. Anal. Appl., 389:2 (2012), 1344–1351 | DOI | MR | Zbl

[17] Klee V., “The structure of semispaces”, Math. Scand., 4 (1956), 54–64 | DOI | MR | Zbl

[18] Klee V., “Maximal separation theorems for convex sets”, Trans. Amer. Math. Soc., 134:1 (1968), 133–147 | DOI | MR | Zbl

[19] Leikhtveis K.M., Vypuklye mnozhestva, Nauka, M., 1985, 336 pp. | MR

[20] Semenkova E.A., “Ob analiticheskom predstavlenii poluprostranstv v konechnomernykh vektornykh prostranstvakh”, Izv. AN Belarusi. Ser. fiz.-mat. nauk, 1996, no. 2, 35–40 | MR | Zbl

[21] Hammer P.C., “Maximal convex sets”, Duke Math. J., 22 (1955), 103–106 | DOI | MR | Zbl

[22] Lassak M., “Convex half-spaces”, Fund. Math., 120:1 (1984), 7–13 | DOI | MR | Zbl

[23] Lassak M.A., Proszynski A., “Translate-inclusive sets, orderings and convex halfspaces”, Bull. Polish Acad. Sci. Math., 34:3–4 (1986), 195–201 | MR | Zbl

[24] Martinez-Legaz J.-E., Singer I., “Lexicographical separation in $\mathbb {R}^n$”, Linear Algebra Appl., 90 (1987), 147–163 | DOI | MR | Zbl

[25] Aleksandrov P.S., Vvedenie v teoriyu mnozhestv i obschuyu topologiyu, Nauka, M., 1977, 368 pp.

[26] Kolmogorov A.N., Fomin S.V., Elementy teorii funktsii i funktsionalnogo analiza, Nauka, M., 1981, 544 pp.