Том 26, номер 3, 2019 г., Стр. 88-114

УДК 519.85
Стонякин Ф. С., Алкуса М., Степанов А. Н., Титов А. А.
Адаптивные алгоритмы зеркального спуска для задач выпуклой и сильно выпуклой оптимизации с функциональными ограничениями

Аннотация:
Рассмотрены некоторые адаптивные алгоритмы зеркального спуска для задач минимизации выпуклого целевого функционала при наличии нескольких выпуклых липшицевых (вообще говоря, негладких) функциональных ограничений. Показано, что методы применимы к целевым функционалам различного уровня гладкости: выполнено условие Липшица либо для самого функционала, либо для его градиента или гессиана (при этом функционал может не удовлетворять свойству Липшица). Главная идея — адаптивная настройка метода на константу Липшица целевого функционала (градиента либо гессиана), а также ограничения. При этом рассмотрено два типа методов: адаптивный (не требует знания констант Липшица ни для целевого функционала, ни для ограничения) и частично адаптивный (требует знания константы Липшица для ограничения). С использованием техники рестартов (перезапусков) методов для задач выпуклой оптимизации предложены методы для задач сильно выпуклой минимизации. Получены оценки скорости сходимости всех рассматриваемых алгоритмов в зависимости от уровня гладкости целевого функционала. Приводятся численные эксперименты, иллюстрирующие для некоторых примеров преимущества предложенных методов.
Табл. 3, библиогр. 22.

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

DOI: 10.33048/daio.2019.26.636

Стонякин Фёдор Сергеевич ^1,2
Алкуса Мохаммад ²
Степанов Алексей Николаевич ¹
Титов Александр Александрович ²
1. Крымский федеральный университет им. В. И. Вернадского,
пр. Акад. Вернадского, 4, 295007 Симферополь, Россия
2. Московский физико-технический институт (гос. университет),
Институтский пер., 9, 141701 Долгопрудный, Россия
е-mail: fedyor@mail.ru, mohammad.alkousa@phystech.edu, stepanov.student@gmail.com, a.a.titov@phystech.edu

Статья поступила 17 октября 2018 г.
После доработки — 24 февраля 2019 г.
Принята к публикации 27 февраля 2019 г.

Литература

[1] Ben-Tal A., Nemirovski A. Robust truss topology design via semidefinite programming // SIAM J. Optim. 1997. Vol. 7, No. 4. P. 991–1016.

[2] Nesterov Yu., Shpirko S. Primal-dual subgradient methods for huge-scale linear conic problem // SIAM J. Optim. 2014. Vol. 24, No. 3. P. 1444–1457.

[3] Nesterov Yu. Introductory lectures on convex optimization: A basic course. Dordrecht: Kluwer Acad. Publ., 2004 (Appl. Optim.; Vol. 87).

[4] Васильев Ф. П. Методы оптимизации. Кн. 1. М.: МЦНМО, 2011. 624 с.

[5] Васильев Ф. П. Методы оптимизации. Кн. 2. М.: МЦНМО, 2011. 434 с.

[6] Lan G. Gradient sliding for composite optimization // Math. Program. 2016. Vol. 159, No. 1–2. P. 201–235.

[7] Beck A., Teboulle M. Mirror descent and nonlinear projected subgradient methods for convex optimization // Oper. Res. Lett. 2003. Vol. 31, No. 3. P. 167–175.

[8] Немировский А. С., Юдин Д. Б. Эффективные методы решения задач выпуклого программирования большой размерности // Экономика и мат. методы. 1979. № 2. С. 135–152.

[9] Немировский А. С., Юдин Д. Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979. 384 с.

[10] Шор Н. З. Применение обобщённого градиентного спуска в блочном программировании // Кибернетика. 1967. № 3. С. 53–55.

[11] Polyak B. T. A general method of solving extremum problems // Sov. Math. Dokl. 1967. Vol. 8, No. 3. P. 593–597.

[12] Beck A., Ben-Tal A., Guttmann-Beck N., Tetruashvili L. The CoMirror algorithm for solving nonsmooth constrained convex problems // Oper. Res. Lett. 2010. Vol. 38, No. 6. P. 493–498.

[13] Ben-Tal A., Nemirovski A. Lectures on modern convex optimization. Philadelphia, PA: SIAM, 2001.

[14] 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. Cham: Springer, 2018. P. 181–213 (Lect. Notes Math.; Vol. 2227).

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

[16] Titov A. A., Stonyakin F. S., Gasnikov A. V., Alkousa M. S. Mirror descent and constrained online optimization problems // Optimization and Applications : Rev. Sel. Pap. 9th Int. Conf. OPTIMA-2018 (Petrovac, Montenegro, Oct. 1–5, 2018). Cham: Springer, 2019. P. 64–78 (Commun. Comput. Inform. Sci.; Vol. 974).

[17] Nesterov Yu. Subgradient methods for convex functions with nonstandard growth properties. 2016. Available at http://mathnet.ru/PresentFiles/16179/growthbm_nesterov.pdf.

[18] Stonyakin F. S., Titov A. A. One mirror descent algorithm for convex constrained optimization problems with non-standard growth properties // Proc. School-Seminar on Optimization Problems and Their Applications (Omsk, Russia, July 8–14, 2018). Aachen: RWTH Aachen Univ., 2018. P. 372–384 (CEUR Workshop Proc., Vol. 2098). Available at http://ceur-ws.org/Vol-2098.

[19] Nesterov Yu. A method of solving a convex programming problem with convergence rate $O(1/k^2)$ // Sov. Math. Dokl. 1983. Vol. 27, No. 2. P. 372–376.

[20] Juditsky A., Nemirovski A. First order methods for non-smooth convex large-scale optimization, I: General purpose methods // Optimization for machine learning. Cambridge, MA: MIT Press, 2012. P. 121–148.

[21] Баяндина А. С., Гасников А. В., Гасникова Е. В., Мациевский С. В. Прямо-двойственный метод зеркального спуска для условных задач стохастической оптимизации // Журн. вычисл. математики и мат. физики 2018. Т. 58, № 11. С. 1728–1736.

[22] Meng X., Chen H. Accelerating Nesterov’s method for strongly convex functions with Lipschitz gradient. 2011 (Cornell Univ. Libr. e-Print Archive; arXiv: 1109.6058).