С.С. Аблаев, Ф.С. Стонякин, М.С. Алкуса, А.В. Гасников. Адаптивные субградиентные методы для задач математического программирования с квазивыпуклыми функциями ... С. 7-25

УДК 519.85

MSC: 90C25, 90С06, 49J52

DOI: 10.21538/0134-4889-2023-29-3-7-25

Исследования Ф.С. Стонякина в разд. 2 и 5 выполнены при поддержке программы стратегического академического лидерства “Приоритет-2030” (соглашение № 075-02-2021-1316 от 30.09.2021). Исследования А.В. Гасникова в разд. 4 в рамках выполнения государственного задания Министерства науки и высшего образования Российской Федерации (проект № 0714-2020-0005).

Работа посвящена субградиентным методам с переключениями по продуктивным и непродуктивным шагам для задач минимизации квазивыпуклых функций при наличии функциональных ограничений-неравенств. Для задачи минимизации выпуклой функции с квазивыпуклыми ограничениями-неравенствами получен результат о сходимости субградиентного метода с адаптивным правилом остановки. Далее, на базе аналога острого минимума для нелинейных задач с ограничениями-неравенствами получен результат о сходимости со скоростью геометрической прогрессии рестартованных версий субградиентных методов. Отдельно рассмотрены такие результаты в случае выпуклой целевой функции и квазивыпуклых ограничений, а также в случае квазивыпуклой целевой функции и выпуклых ограничений-неравенств. Выпуклость может позволять дополнительно предлагать адаптивные правила остановки вспомогательных методов, гарантирующие достижение приемлемого качества решения. Приведены результаты вычислительных экспериментов, показывающие преимущества использования таких правил остановки.

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

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

1.   Поляк Б.Т. Один общий метод решения экстремальных задач // Докл. АН СССР. 1967. Т. 174, № 1. С. 33–36.

2.   Huang Y., Lin Q. Single-loop switching subgradient methods for non-smooth weakly convex optimization with non-smooth convex constraints [e-resource]. 2023. 49 p. URL: https://arxiv.org/pdf/2301.13314.pdf 

3.   Bayandina A., Dvurechensky P., Gasnikov A., Stonyakin F., Titov A. Mirror descent and convex optimization problems with non-smooth inequality constraints // Large-Scale and Distributed Optimization / eds. Pontus Giselsson and Anders Rantzer. 2018. P. 181–213. (Ser. Lecture Notes in Math. 2018; vol. 2227. ) doi: 10.1007/978-3-319-97478-1_8

4.   Lagae S. New efficient techniques to solve sparse structured linear systems, with applications to truss topology optimization // Ecole polytechnique de Louvain. Université catholique de Louvain, 2017. URL: https://dial.uclouvain.be/memoire/ucl/object/thesis:12934 

5.   Nesterov Yu. Subgradient methods for huge-scale optimization problems // Math. Prog. 2015. Vol. 146, no. 1–2. P. 275–297. doi: 10.1007/s10107-013-0686-4

6.   Стонякин Ф.С., Алкуса М.С., Степанов А.Н., Баринов М.А. Адаптивные алгоритмы зеркального спуска в задачах выпуклого программирования с липшицевыми ограниченями // Тр. Ин-та математики и механики УрО РАН. 2018. Т. 24, № 2. С. 266–279. doi: 10.21538/0134-4889-2018-24-2-266-279

7.   Stonyakin F.S., Stepanov A.N., Gasnikov A.V., Titov A.A. Mirror descent for constrained optimization problems with large subgradient values of functional constraints // Computer Research and Modeling. 2020. Vol. 12, no. 2. P. 301–317. doi: 10.20537/2076-7633-2020-12-2-301-317

8.   Lin Q., Ma R., Nadarajah S., Soheili N. A Parameter-free and projection-free restarting level set method for adaptive constrained conver optimization under the error bound condition [e-resource]. 2022. 29 p. URL: https://arxiv.org/pdf/2010.15267.pdf .

9.   Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983. 384 с.

10.   Нестеров Ю.Е. Эффективные методы нелинейного программирования. М.: Радио и связь, 1989. 301 с.

11.   Кларк Ф. Оптимизация и негладкий анализ: пер. с англ. / под ред. В. И. Благодатских. М.: Наука, 1988. 280 с. ISBN 5-02-013781-2 .

12.   Поляк Б.Т. Минимизация негладких функционалов // Жyрн. вычисл. математики и мат. физ. 1969. Т. 9, № 3. С. 509–521.

13.   Boyd S.P., Vandenberghe L. Convex optimization. Cambridge: Cambridge Univ. Press., 2004. 716 p. ISBN: 9780521833783

Поступила 14.05.2023

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

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

Аблаев Сейдамет Серверович
аспирант
Крымский федеральный университет им. В.И. Вернадского
г. Симферополь;
Московский физико-технический институт (национальный исследовательский университет)
г. Долгопрудный
e-mail: seydamet.ablaev@yandex.ru

Стонякин Федор Сергеевич
д-р физ.-мат. наук, ведущий науч. сотрудник
Московский физико-технический институт (национальный исследовательский университет)
г. Долгопрудный;
профессор
Крымский федеральный университет им. В.И. Вернадского
г. Симферополь
e-mail: fedyor@mail.ru

Алкуса Мохаммад
канд. физ.-мат. наук
Московский физико-технический институт (национальный исследовательский университет)
г. Долгопрудный
e-mail: mohammad.alkousa@phystech.edu

Гасников Александр Владимирович
д-р физ.-мат. наук, профессор
Московский физико-технический институт (национальный исследовательский университет)
г. Долгопрудный;
Институт проблем передачи информации им. А.А. Харкевича
г. Москва;
Кавказский математический центр Адыгейского государственного университета
г. Майкоп
e-mail: gasnikov@yandex.ru

Ссылка на статью: С.С. Аблаев, Ф.С. Стонякин, М.С. Алкуса, А.В. Гасников. Адаптивные субградиентные методы для задач математического программирования с квазивыпуклыми функциями // Тр. Ин-та математики и механики УрО РАН. 2023. Т. 29, № 3. С. 7-25

English

S.S. Ablaev, F.S. Stonyakin, M.S. Alkousa, A.V. Gasnikov. Adaptive subgradient methods for mathematical programming problems with quasi-convex functions

The paper is devoted to subgradient methods with switching over productive and non-productive steps for problems of minimization of quasi-convex functions with functional inequality constraints. For the problem of minimizing a convex function with quasi-convex inequality constraints, result is obtained on the convergence of the subgradient method with an adaptive stopping rule. Further, on the basis of an analogue of a sharp minimum for nonlinear problems with inequality constraints, results are obtained on the convergence with the rate of a geometric progression of restarted versions of subgradient methods. Such results are considered separately in the case of a convex objective function and quasi-convex inequality constraints, as well as in the case of a quasi-convex objective function and convex inequality constraints. The convexity may allow to additionally suggest adaptive stopping rules for auxiliary methods, which guarantee that an acceptable solution quality is achieved. The results of computational experiments are presented, showing the advantages of using such stopping rules.

Keywords: subgradient method, quasi-convex function, sharp minimum, restarts, adaptive method

Received May 14, 2023

Revised July 4, 2023

Accepted July 10, 2023

Funding Agency: The research of F.S.Stonyakin in Sections 2 and 5 was supported by the Strategic Academic Leadership Program “Priority 2030” (agreement no. 075-02-2021-1316 of September 30, 2021). The research of A.V.Gasnikov in Section 4 was carried out under a state task of the Ministry of Science and Higher Education of the Russian Federation (project no. 0714-2020-0005).

Seydamet Serverovich Ablaev, doctoral student, V.I.Vernadsky Crimean Federal University, Simferopol, Republic of Crimea, Russia 295007, e-mail: seydamet.ablaev@yandex.ru

Fedor Sergeevich Stonyakin, Dr. Phys.-Math. Sci., Prof., Moscow Institute of Physics and Technologies, Dolgoprudny, Moscow Region, 141701 Russia; V.I.Vernadsky Crimean Federal University, Simferopol, Republic of Crimea, 295007 Russia, e-mail: fedyor@mail.ru

Mohammad S. Alkousa, Cand. Phys.-Math. Sci., Moscow Institute of Physics and Technology (National Research University); Dolgoprudny, Moscow Region, 141701 Russia, e-mail: mohammad.alkousa@phystech.edu

Aleksandr Vladimirovich Gasnikov, Dr. Phys.-Math. Sci., Prof., Moscow Institute of Physics and Technology (National Research University); Dolgoprudny, Moscow Region, 141701 Russia; Caucasus Mathematical Center, Adyghe State University, Maikop, 385000 Russia; Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute), Moscow, 127051 Russia, e-mail: gasnikov@yandex.ru

Cite this article as: S.S. Ablaev, F.S. Stonyakin, M.S. Alkousa, A.V. Gasnikov. Adaptive subgradient methods for mathematical programming problems with quasi-convex functions. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2023, vol. 29, no. 3, pp. 7–25.

[References -> on the "English" button bottom right]