В.В. Гороховик. Ступенчато-аффинные функции, полупространства и отделимость выпуклых множеств с приложениями к выпуклым задачам оптимизации ... C. 51-70

УДК 517.982.252+519.858+519.853.3

MSC: 52A05, 52A41, 49K27, 90C25

DOI: 10.21538/0134-4889-2020-26-1-51-70

Работа выполнена в рамках Государственной программы научных исследований Республики Беларусь на 2016– 2020 годы “Конвергенция-2020” (проект 1.4.01).

Полный текст статьи (Full text)

Статья переведена: ISSN 0081-5438 

Proceedings of the Steklov Institute of Mathematics, 2021, Vol. 313, Suppl. 1, pp. S83–S99. (Abstract)

В статье приводится определение ступенчато-аффинных функций, определенных на вещественном векторном пространстве, и устанавливается их двойственность полупространствам — выпуклым множествам, дополнения которых также выпуклы. С использованием этой двойственности доказывается, что два выпуклых подмножества вещественного векторного пространства не пересекаются тогда и только тогда, когда они отделимы некоторой ступенчато-аффинной функцией. Фактически данный критерий непересекаемости выпуклых множеств является аналитическим вариантом критерия Какутани — Тьюки об отделимости непересекающихся выпуклых множеств полупространствами. В качестве приложений получены критерий минимальности решений для выпуклых задач векторной оптимизации, рассматриваемых в вещественных векторных пространствах без топологии, и критерий оптимальности допустимых точек в классических задачах выпуклого программирования, не удовлетворяющих условию регулярности Слейтера.

Ключевые слова: ступенчато-аффинные функции, полупространства, отделимость выпуклых множеств, выпуклые задачи векторной оптимизации, выпуклое программирование

СПИСОК ЛИТЕРАТУРЫ

1.   Райков Д.Ф. Векторные пространства. М.: Физматгиз, 1962. 212 с.

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

3.   Kakutani S. Ein Beweis des Satzen von M. Eidelheit Јuber konvexe Mengen // Proc. Imp. Acad. Tokio. 1938. Vol. 14. P. 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. P. 95–102.

5.   Хилле Э., Филлипс Р. Функциональный анализ и полугруппы. М.: ИЛ, 1962. 830 с.

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

7.   Гороховик В.В. Минимальность и квазиминимальность в упорядоченных векторных пространствах // Докл. АН БССР. 1981. Т. 25, № 8. С. 685–688.

8.   Гороховик В.В. Выпуклые и негладкие задачи векторной оптимизации. Минск: Наука и Техника, 1990. 240 с.

9.   Гороховик В.В., Семенкова Е.А. Ступенчато–линейные функции в конечномерных векторных пространствах. Определение, свойства и их связь с полупространствами // Докл. АН Беларуси. 1997. Т. 41, № 5. С. 10–14.

10.   Гороховик В.В., Семенкова Е.А. Классификация полупространств по типам в бесконечномерных векторных пространствах // Мат. заметки. 1998. Т. 64, вып. 2. С. 191–198.

11.   Гороховик В.В., Шинкевич Е.А. Теоремы об отделимости выпуклых множеств ступенчато–линейными функциями и их приложения к выпуклым задачам оптимизации // Нелинейный анализ и приложения / Национальная Академия наук Беларуси. Труды Института математики. 1998. Т. 1. С. 58–85.

12.   Гороховик В.В., Шинкевич Е.А. Аналитическое представление бесконечномерных полупространств ступенчато–аффинными функциями // Нелинейный анализ и смежные вопросы / Национальная Академия наук Беларуси. Труды Института математики. 1999. Т. 2. С. 63–72.

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

14.   Martinez-Legaz J.-E., Vicente-Perez J. Lexicographical representation of convex sets // J. Convex Analysis. 2012. Vol. 19, no. 2. P. 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. P. 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. P. 1344–1351. doi: 10.1016/j.jmaa.2012.01.017 

17.   Klee V. The structure of semispaces // Math. Scand. 1956. Vol. 4. P. 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. P. 133–147. doi: 10.1090/S0002-9947-1968-0235457-9 

19.   Лейхтвейс К.М. Выпуклые множества. М.: Наука, 1985. 336 c.

20.   Семенкова Е.А. Об аналитическом представлении полупространств в конечномерных векторных пространствах // Изв. АН Беларуси. Сер. физ.-мат. наук. 1996. № 2. С. 35–40.

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

22.   Lassak M. Convex half-spaces // Fund. Math. 1984. Vol. 120, no. 1. P. 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. P. 195–201.

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

25.   Александров П.С. Введение в теорию множеств и общую топологию. М.: Наука, 1977. 368 c.

26.   Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. М.: Наука, 1981. 544 с.

Поступила 11.11.2019

После доработки 10.01.2020

Принята к публикации 14.01.2020

Гороховик Валентин Викентьевич
д-р физ.-мат. наук, профессор
чл.-корр. НАН Беларуси
зав. отделом
Институт математики НАН Беларуси, г. Минск
e-mail: gorokh@im.bas-net.by

Ссылка на статью: В.В. Гороховик. Ступенчато-аффинные функции, полупространства и отделимость выпуклых множеств с приложениями к выпуклым задачам оптимизации // Тр. Ин-та математики и механики УрО РАН. 2020. Т.26, № 1. C. 51-70.

English

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

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

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.