Адаптивные градиентные методы для некоторых классов задач негладкой оптимизации
Автор: Стонякин Ф. С.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Информатика и управление
Статья в выпуске: 1 (45) т.12, 2020 года.
Бесплатный доступ
Предложено несколько адаптивных алгоритмических методов, применимых к задачам негладкой выпуклой оптимизации. Первый из них основан на введении специальной искусственной неточности, и для его реализации предложен соответствующий аналог концепции абстрактной неточной модели целевой функции. Для этой концепции предложены аналоги градиентного метода, а также быстрого градиентного метода с адаптивной настройкой некоторых параметров неточной модели, и получена оценка качества найденного решения. Показано, что для негладких задач возможно модифицировать предложенные методы так, чтобы гарантированно выполнялась сходимость по функции со скоростью, близкой к оптимальной. Введена аналогичная концепция неточной модели для оператора поля вариационного неравенства, а также для седловой задачи и приведена оценка скорости сходимости соответствующего адаптивного варианта проксимального зеркального метода. Предложены аналоги субградиентных схем с переключениями для задач выпуклой оптимизации с ограничениями. При этом рассмотрены предположения, связанные с недавно предложенным условием относительной липшицевости. Это позволило выписать оценку качества решения с относительной точностью для задачи минимизации однородного выпуклого функционала при достаточно общих предположениях.
Градиентный метод, быстрый градиентный метод, адаптивный метод, липшицев градиент, негладкая оптимизация, зеркальный спуск, относительная липшицевость, относительная точность
Короткий адрес: https://sciup.org/142223094
IDR: 142223094
Список литературы Адаптивные градиентные методы для некоторых классов задач негладкой оптимизации
- Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. Москва: Наука, 1979. 384 с.
- Nesterov Yu. Universal gradient methods for convex optimization problems // Math. Program. Ser. A. 2015. V. 152, N 1-2. P. 381-404.
- Стонякин Ф.С. Аналог квадратичной интерполяции для специального класса негладких функционалов и одно его приложение к адаптивному методу зеркального спуска // Динамические системы. 2019. Т. 9(37), № 1. С. 3-16.
- Стонякин Ф.С. Адаптация к погрешности для некоторых методов градиентного типа // Труды ИММ УрО РАН. 2019. Т. 25, № 4. С. 210-225.
- Devolder O., Glineur F., Nesterov Yu. First-order methods of smooth convex optimization with inexact oracle // Math. Program. 2014. V. 146, N 1-2. n P. 37-75.
- Devolder O. Exactness, Inexactness and Stochasticity in First-Order Methods for Large- Scale Convex Optimization // PhD thesis, 2013. 309 p.
- Tyurin A.I., Gasnikov A.V. Fast gradient descent method for convex optimization problems with an oracle that generates a (d, L)-model of a function in a requested point // Computational Mathematics and Mathematical Physics. 2019. V.59, N 7. P. 1137-1150.
- Stonyakin F.S., Dvinskikh D., Dvurechensky P., Kroshnin A., Kuznetsova O., Agafonov A., Gasnikov A., Tyurin A., Uribe C.A., Pasechnyuk D., Artamonov S. Gradient Methods for Problems with Inexact Model of the Objective // In: Khachay M., Kochetov Y., Pardalos P. (eds) Mathematical Optimization Theory and Operations Research. MOTOR 2019. Lecture Notes in Computer Science. 2019. V. 11548. P. 97-114.
- Bauschke H.H., Bolte J., Teboulle M. A Descent Lemma Beyond Lipschitz Gradient Continuity: First-Order Methods Revisited and Applications // Mathematics of Operations Research. 2017. V. 42, N 2. P. 330-348.
- Necoara I., Nesterov Y. Glineur F. Linear convergence of first order methods for nonstrongly convex optimization // Math. Program. 2019. V. 175. P. 69-107.
- Lu H., Freund R.M., Nesterov Y. Relatively smooth convex optimization by Firstorder methods, and applications // SIAM Journal on Optimization. 2018. V. 28, N 1. P. 333-354.
- Lu H. "Relative-Continuity"for Non-Lipschitz Non-Smooth Convex Optimization using Stochastic (or Deterministic) Mirror Descent // Arxiv preprint. 2018. 22 p. Available at: https://arxiv.org/abs/1710.04718v3.
- Stonyakin F., Stepanov A., Titov A., Gasnikov A. Mirror Descent for Constrained Optimization Problems with Large Subgradient Values // Copmuter Research and Modelling. 2020. V. 12, N 2. 23 p. Available at: https://arxiv.org/abs/1908.00218v4.
- Lan G. Gradient sliding for composite optimization // Math. Program. 2016. V. 159, N 1-2. P. 201-235.
- Нестеров Ю.Е. Метод минимизации выпуклых функций со скоростью сходимости O(1/k2) // Доклады АН СССР. 1983. Т. 269, № 3. С. 543-547.
- Stonyakin F., Vorontsova E., Alkousa M. New Version of Mirror Prox for Variational Inequalities with Adaptation to Inexactness // Communications on Computer and Information Sciences. 2020. V. 1145. P. 427-442.
- Стонякин Ф.С. Об адаптивном проксимальном методе для некоторого класса вариационных неравенств и смежных задач // Труды ИММ УрО РАН. 2019. Т. 25, № 2. С. 185-197.
- Поляк Б.Т. Один общий метод решения экстремальных задач // Докл. АН СССР. 1967. Т. 174, № 1. С. 33-36.
- Шор Н.З. Применение обобщённого градиентного спуска в блочном программировании // Кибернетика. 1967. № 3. С. 53-55.
- 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. Lecture Notes in Math. 2018. V. 2227. P. 181-213.
- Ivanova A., Stonyakin F., Pasechnyuk D., Vorontsova E., Gasnikov A. Adaptive Mirror Descent for the Network Utility Maximization Problem // Arxiv preprint. 2019. 7 p. Available at: https://arxiv.org/abs/1911.07354v2.
- Stonyakin F.S. An analogue of the Hahn-Banach theorem for functionals on abstract convex cones // Eurasian Math. J. 2016. V.7, N 3. P. 89-99.
- Стонякин Ф.С. Сублинейный аналог теоремы Банаха-Мазура в отделимых выпуклых конусах с нормой // Матем. заметки. 2018. Т. 104, № 1. С. 118-130.
- Stonyakin F.S. Hahn-Banach type theorems on functional separation for convex ordered normed cones // Eurasian Math. J. 2019. V. 10, N 1. P. 59-79.
- Нестеров Ю.Е. Алгоритмическая выпуклая оптимизация / Дисс.. докт. физ.-мат. наук. Москва: МФТИ, 2013. 367 c.
- Dragomir R.-A., Taylor A., dA'spremont A., Bolte J. Optimal Complexity and Certification of Bregman First-Order Methods. Arxiv preprint. 2019. 32 p. Available at: https://arxiv.org/abs/1911.08510.
- Dvurechensky P., Gasnikov A., Nurminsky E. and Stonyakin F. Advances in Low-Memory Subgradient Optimization. A.M. Bagirov et al. (eds.), Numerical Nonsmooth Optimization, Springer Nature Switzerland AG. 2020. 36 p. Available at: https://arxiv.org/abs/1902.01572v1.
- Stonyakin F.S., Alkousa M.S., Titov A.A., Piskunova V.V. On Some Methods for Strongly Convex Optimization Problems with One Functional Constraint. M. Khachay et al. (eds.). Mathematical Optimization Theory and Operations Research. MOTOR 2019. Lecture Notes in Computer Science. 2019. V. 11548. P. 82-96.
- Пасечнюк Д.А., Стонякин Ф.С. Об одном методе минимизации выпуклой липшицевой функции двух переменных на квадрате // Компьютерные исследования и моделирование. 2019. Т. 11, № 3. С. 379-395.
