Отправить статью по E-mail О достижимости оптимальных оценок скорости сходимости численных методов выпуклой оптимизации высоких порядков
- Авторы: Гасников А.В.1,2, Горбунов Э.А.1, Ковалев Д.А.1, Мохаммед А.1, Черноусова Е.О.1
-
Учреждения:
- Московский физико-технический институт (национальный исследовательский университет)
- Институт проблем передачи информации им. А.А. Харкевича Российской академии наук
- Выпуск: Том 484, № 6 (2019)
- Страницы: 667-671
- Раздел: Математика
- URL: https://journals.eco-vector.com/0869-5652/article/view/12813
- DOI: https://doi.org/10.31857/S0869-56524846667-671
- ID: 12813
Цитировать
Полный текст
Аннотация
Рассматривается проксимальный быстрый градиентный метод Монтейро-Свайтера (2013 г.), в котором используется один шаг метода Ньютона для приближённого решения вспомогательной задачи на каждой итерации проксимального метода. Метод Монтейро-Свайтера является оптимальным (по числу вычислений градиента и гессиана оптимизируемой функции) для достаточно гладких задач выпуклой оптимизации в классе методов, использующих только градиент и гессиан оптимизируемой функции. За счёт замены шага метода Ньютона на шаг недавно предложенного тензорного метода Ю.Е. Нестерова (2018 г.), а также за счёт специального обобщения условия подбора шага в проксимальном внешнем быстром градиентном методе удалось предложить оптимальный тензорный метод, использующий старшие производные. В частности, такой тензорный метод, использующий производные до третьего порядка включительно, оказался достаточно практичным ввиду сложности итерации, сопоставимой со сложностью итерации метода Ньютона. Таким образом, получено конструктивное решение задачи, поставленной Ю.Е. Нестеровым в 2018 г., об устранении зазора в точных нижних и завышенных верхних оценках скорости сходимости для имеющихся на данный момент тензорных методов порядка p ≥ 3.
Ключевые слова
Полный текст
accelerated proximal method; tensor method; Newton method; lower bounds
Об авторах
А. В. Гасников
Московский физико-технический институт (национальный исследовательский университет); Институт проблем передачи информации им. А.А. Харкевича Российской академии наук
Автор, ответственный за переписку.
Email: gasnikov@yandex.ru
Россия, 141701, Московская обл., г. Долгопрудный, Институтский пер., д.9; 127994, Москва, ГСП-4, пер. Большой Каретный, д.19, стр. 1
Э. А. Горбунов
Московский физико-технический институт (национальный исследовательский университет)
Email: gasnikov@yandex.ru
Россия, 141701, Московская обл., г. Долгопрудный, Институтский пер., д.9
Д. А. Ковалев
Московский физико-технический институт (национальный исследовательский университет)
Email: gasnikov@yandex.ru
Россия, 141701, Московская обл., г. Долгопрудный, Институтский пер., д.9
А. А. М. Мохаммед
Московский физико-технический институт (национальный исследовательский университет)
Email: gasnikov@yandex.ru
Россия, 141701, Московская обл., г. Долгопрудный, Институтский пер., д.9
Е. О. Черноусова
Московский физико-технический институт (национальный исследовательский университет)
Email: gasnikov@yandex.ru
Россия, 141701, Московская обл., г. Долгопрудный, Институтский пер., д.9
Список литературы
- Arjevani Y., Shamir O., Shiff R. Oracle Complexity of Second-Order Methods for Smooth Convex Optimization // Math. Programming. 2017. P. 1-34.
- Nesterov Yu. Implementable Tensor Methods in Unconstrained Convex Optimization. Prepr. Univ. catholique de Louvain; Center for Operations Res. and Econometrics (CORE). 2018. № 2018005.
- Гасников А.В., Ковалев Д.А. Гипотеза об оптимальных оценках скорости сходимости численных методов выпуклой оптимизации высоких порядков // Компьют. исслед. и моделирование. 2018. Т. 10. № 3. С. 305-314.
- Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979.
- Monteiro R., Svaiter B. An Accelerated Hybrid Proximal Extragradient Method for Convex Optimization and its Implications to Second-Order Methods // SIAM J. Optim. 2013. V. 23. № 2. P. 1092-1125.
- Nesterov Yu. Introductory Lectures on Convex Optimization: A Basic Course. B.: Springer Science & Business Media, 2013. 87 p.
- Нестеров Ю.Е. Введение в выпуклую оптимизацию. М.: МЦНМО, 2010.
- Lin H., Mairal J., Harchaoui Z. Catalyst Acceleration for First-Order Convex Optimization: from Theory to Practice // J. Machine Learning Res. 2018. V. 18. № 212. С. 1-54.
- Nesterov Yu., Polyak B. Cubic Regularization of Newton Method and Its Global Performance // Math. Program. 2006. V. 108. № 1. P. 177-205.
- Гасников А.В. Современные численные методы оптимизации. Метод универсального градиентного спуска. М.: МФТИ, 2018. 166 с.
- Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы. Построение и анализ. М.: Изд. дом “Вильямс”, 2009.
Дополнительные файлы
