УДК 519.85
MSC: 90C25, 90С06, 49J52
DOI: 10.21538/0134-4889-2018-24-2-266-279
Полная версия статьи
Исследование Ф. С. Стонякина (доказательство теоремы 2) выполнено при поддержке Российского фонда фундаментальных исследований, проект 18-31-00219. Исследование Ф .С. Стонякина и А. Н. Степанова в части доказательства следствий 1 и 2, проведения численных экспериментов и заключительных замечаний выполнены при частичной поддержке гранта Президента Российской Федерации для государственной поддержки молодых российских ученых — кандидатов наук, код МК-176.2017.1 .
Работа посвящена новым модификациям недавно предложенных адаптивных методов зеркального спуска для задач выпуклой минимизации в случае нескольких выпуклых функциональных ограничений. Предложены адаптивные методы зеркального спуска для задач двух типов. Первый тип — задачи с липшицевым (вообще говоря, негладким) целевым функционалом. Второй тип — задачи с липшицевым градиентом целевого функционала. Рассматривается также случай негладкого целевого функционала, равного максимуму гладких функционалов с липшицевым градиентом. Во всех случаях функциональные ограничения считаются выпуклыми, липшицевыми и, вообще говоря, негладкими. Предлагаемые методы позволяют сэкономить время работы алгоритма за счет рассмотрения не всех функциональных ограничений на непродуктивных шагах. Получены оценки на скорость сходимости рассматриваемых методов. Эти оценки демонстрируют оптимальность методов с точки зрения нижних оракульных оценок. Приведены результаты численных экспериментов, иллюстрирующие преимущества предлагаемой методики для некоторых примеров.
Ключевые слова: адаптивный метод зеркального спуска, липшицев функционал, липшицев градиент, продуктивный шаг, непродуктивный шаг.
СПИСОК ЛИТЕРАТУРЫ
1. Ben-Tal A. and Nemirovski A. Robust truss topology design via semidefinite programming // SIAM J. Optim. 1997. Vol. 7, no. 4, pp. 991–1016. doi: 10.1137/S1052623495291951 .
2. Shpirko S., Nesterov Yu. Primal-dual subgradient methods for huge-scale linear conic problem // SIAM J. Optim. 2014. Vol. 24, no. 3, pp. 1444–1457. doi: 10.1137/130929345 .
3. Beck A., Teboulle M. Mirror descent and nonlinear projected subgradient methods for convex optimization // Operations Research Letters. 2003. Vol. 31, no. 3, pp. 167–175. doi: 10.1016/S0167-6377(02)00231-6 .
4. Nemirovsky A., Yudin D. Problem complexity and method efficiency. N Y: Wiley & Sons, 1983. 404 p. ISBN: 978-0471103455 .
5. Поляк Б. Т. Один общий метод решения экстремальных задач // Докл. АН СССР. 1967. Т. 8, № 3. С. 593–597.
6. Шор Н. 3. Применение обобщенного градиентного спуска в блочном программировании // Кибернетика. 1967. № 3. С. 53–55.
7. Немировский А. С., Юдин Д. Б. Эффективные методы решения задач выпуклого программирования большой размерности // Экономика и математические методы. 1979. № 2. С. 135–152.
8. The comirror algorithm for solving nonsmooth constrained convex problems / A. Beck, A. Ben-Tal, N. Guttmann-Beck, L. Tetruashvili // Operations Research Letters. 2010. Vol. 38, no. 6. P. 493–498. doi: 10.1016/j.orl.2010.08.005 .
9. Ben-Tal A., Nemirovski A. Lectures on modern convex optimization. Philadelphia: Society for Industrial and Appl. Math., 2001. 590 p. ISBN: 0-89871-491-5 .
10. Mirror descent and convex optimization problems with non-smooth inequality constraints [e-resource] / A. Bayandina, P. Dvurechensky, A. Gasnikov, F. Stonyakin, A. Titov. 2018. 30 p. URL: arxiv.org/abs/1710.06612 .
11. Nesterov Y. Introductory lectures on convex optimization: a basic course. Boston: Kluwer Acad. Publ., 2004. 236 p. doi: 10.1007/978-1-4419-8853-9 .
12. Nesterov Y. Subgradient methods for convex functions with nonstandard growth properties [e-resource, slides]. URL: www.mathnet.ru:8080/PresentFiles/16179/growthbm_nesterov.pdf [Online; accessed 30-March-2018].
13. CPython [site]. URL: https://www.python.org/ .
Поступила 30.03.2018
Стонякин Федор Сергеевич
канд. физ.-мат. наук, доцент
Крымский федеральный университет им. В.И.Вернадского,
г. Симферополь
e-mail: fedyor@mail.ru
Mohammad S. Alkousa
аспирант
Московский физико-технический институт (государственный университет),
г. Москва
e-mail: mohammad.alkousa@phystech.edu
Степанов Алексей Николаевич
соисполнитель работ по гранту Президента РФ
для молодых кандидатов наук, код МК-176.2017.1
Крымский федеральный университет им. В.И.Вернадского,
г. Симферополь
Баринов Максим Александрович
студент
Крымский федеральный университет им. В.И.Вернадского
г. Симферополь
e-mail: ice8scream@gmail.com
English
F.S. Stonyakin, M.S. Alkousa, A.N. Stepanov, M.A. Barinov. Adaptive mirror descent algorithms in convex programming problems with Lipschitz constraints.
The paper is devoted to new modifications of recently proposed adaptive Mirror Descent methods for convex minimization problems in the case of several convex functional constraints. Methods for problems of two types are considered. In problems of the first type, the objective functional is Lipschitz (generally, nonsmooth). In problems of the second type, the gradient of the objective functional is Lipschitz. We also consider the case of a nonsmooth objective functional equal to the maximum of smooth functionals with Lipschitz gradient. In all the cases, the functional constraints are assumed to be Lipschitz and, generally, nonsmooth. The proposed modifications make it possible to reduce the running time of the algorithm due to skipping some of the functional constraints at nonproductive steps. We derive bounds for the convergence rate, which show that the methods under consideration are optimal from the viewpoint of lower oracle estimates. The results of numerical experiments illustrating the advantages of the proposed procedure for some examples are presented.
Keywords: adaptive Mirror Descent, Lipschitz functional, Lipschitz gradient, productive step, nonproductive step.
The paper was received by the Editorial Office on March 30, 2018.
Funding Agency:
1) Russian Foundation for Basic Research (Grant Number 18-31-00219);
2) Ministry of Education and Science of the Russian Federation ((Grant Number МК-176.2017.1).
Fedor Sergeevich Stonyakin, Cand. Sci. (Phys.-Math.), V.I. Vernadsky Crimean Federal University, Simferopol, Republic of Crimea, 295007 Russia, e-mail: fedyor@mail.ru.
Mohammad S. Alkousa, doctoral student, Moscow Institute of Physics and Technologies, Moscow, 141701 Russia, e-mail: mohammad.alkousa@phystech.edu.
Aleksei Nikolaevich Stepanov, co-executor of research work by grant the President of Russian Federation for young candidates of sciences, project no. MK-176.2017.1, V.I. Vernadsky Crimean Federal University, Simferopol, Republic of Crimea, 295007 Russia, e-mail: stepanov.student@gmail.com.
Maksim Aleksandrovich Barinov, undergraduate student, V.I. Vernadsky Crimean Federal University, Simferopol, Republic of Crimea, 295007 Russia, e-mail: ice8scream@gmail.com.
[References on the English button bottom right]
