Отправить статью по E-mail Прямо-двойственный ускоренный градиентный метод с одномерным поиском для выпуклых, невыпуклых и негладких задач оптимизации
- Авторы: Гуминов С.В.1,2, Нестеров Ю.Е.3,4, Двуреченский П.Е.2,5, Гасников А.В.1,2
-
Учреждения:
- Московский физико-технический институт (государственный университет)
- Институт проблем передачи информации Российской Академии наук
- Center for Operations Research and Econometrics (CORE), Catholic University of Louvain
- Национальный исследовательский университет “Высшая школа экономики”
- Weierstrass Institute for Applied Analysis and Stochastics
- Выпуск: Том 485, № 1 (2019)
- Страницы: 15-18
- Раздел: Математика
- URL: https://journals.eco-vector.com/0869-5652/article/view/12803
- DOI: https://doi.org/10.31857/S0869-5652485115-18
- ID: 12803
Цитировать
Полный текст
Аннотация
Представлен новый ускоренный градиентный метод оптимизации. Данный метод не требует никакой априорной информации о целевой функции, использует процедуру одномерного поиска для ускорения сходимости на практике, сходится согласно известным нижним оценкам как для выпуклых, так и невыпуклых целевых функций и обладает свойством прямо-двойственности. Также представлена универсальная версия данного метода.
Об авторах
С. В. Гуминов
Московский физико-технический институт (государственный университет); Институт проблем передачи информации Российской Академии наук
Автор, ответственный за переписку.
Email: sergey.guminov@phystech.edu
Россия, 141701, Московская обл., г. Долгопрудный, Институтский пер., д.9; 127051, г.Москва, Б. Каретный пер., д.19, стр.1
Ю. Е. Нестеров
Center for Operations Research and Econometrics (CORE), Catholic University of Louvain; Национальный исследовательский университет “Высшая школа экономики”
Email: sergey.guminov@phystech.edu
Россия, Belgium; Москва
П. Е. Двуреченский
Институт проблем передачи информации Российской Академии наук; Weierstrass Institute for Applied Analysis and Stochastics
Email: sergey.guminov@phystech.edu
Россия, 127051, г.Москва, Б. Каретный пер., д.19, стр.1; Berlin, Germany
А. В. Гасников
Московский физико-технический институт (государственный университет); Институт проблем передачи информации Российской Академии наук
Email: sergey.guminov@phystech.edu
Россия, 141701, Московская обл., г. Долгопрудный, Институтский пер., д.9; 127051, г.Москва, Б. Каретный пер., д.19, стр.1
Список литературы
- Нестеров Ю.Е. Эффективные методы в нелиней- ном программировании. М.: радио и связь, 1989.
- Waltz R. A., Morales J.L., Nocedal J., Orban D. An Interior Algorithm for Nonlinear Optimization that Combines Line Search and Trust Region Steps //Math. Progr. 2006. V. 107. № 3. P. 391–408.
- Narkiss G., Zibulevsky M. Sequential Subspace Optimization Method for Large-Scale Unconstrained Problems. Tech. Report CCIT № 559. Haifa: EE Dept.Technion, 2005.
- Nesterov Yu. Smooth Minimization of Non-Smooth Functions // Math. Progr. 2005. V. 103. № 1. P. 127–152.
- Nesterov Yu. Primal-Dual Subgradient Methods for Convex Problems // Math. Progr. 2009. V. 120. № 1. P. 221–259.
- Dvurechensky P., Gasnikov A., Kroshnin A. Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn’s Algorithm. Proc. of the 35th International Conference on Machine Learning. Stockholm: PMLR, 2018. P. 1367–1376.
- Dvurechensky P., Gasnikov A., Matsievsky S., Rodomanov A., Usik I. Primal-Dual Method for Searching Equilibrium in Hierarchical Congestion Population Games CEUR-WS // Supplementary Proc. the 9th In- tern. Conf. on Discrete Optimization and Operations Research and Scientific School (DOOR 2016). B.: Springer, 2016. P. 584–595. http://ceurws.org/Vol-1623/
- Chernov A., Dvurechensky P., Gasnikov A. Fast Primal- Dual Gradient Method for Strongly Convex Minimiza- tion Problems with Linear Constraints // Proceeding of the 9th Intern. Conf. on Discrete Optimization and Operations Research (DOOR 2016). B.: Springer, 2016. P. 391–403.
- Нестеров Ю.Е. Метод решения задач выпуклого программирования с трудоемкостью O(1/k2) // ДАН. 1983. Т. 269. № 3. С. 543–547.
- Нестеров Ю.Е. Введение в выпуклую оптимиза- цию. М.: МЦНМО, 2010. 280 с.
- Allen-Zhu Z., Orecchia L. Linear Coupling: An Ulti- mate Unification of Gradient and Mirror Descent. Proc. of the 8th Innovations in Theoretical Computer Science. Saarbrücken: Schloss Dagstuhl, 2017.
- Nesterov Yu. Universal Gradient Methods for Convex Optimization Problems // Math. Progr. 2015. V. 152. № 1/2. P. 381–404.
- Guminov S., Gasnikov A., Anikin A., Gornov A. A Uni- versal Modification of the Linear Coupling Method // Optim. Met. and Soft. 2018. doi: 10.1080/10556788. 2018.1517158.
Дополнительные файлы
