О достижимости оптимальных оценок скорости сходимости численных методов выпуклой оптимизации высоких порядков

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Рассматривается проксимальный быстрый градиентный метод Монтейро-Свайтера (2013 г.), в котором используется один шаг метода Ньютона для приближённого решения вспомогательной задачи на каждой итерации проксимального метода. Метод Монтейро-Свайтера является оптимальным (по числу вычислений градиента и гессиана оптимизируемой функции) для достаточно гладких задач выпуклой оптимизации в классе методов, использующих только градиент и гессиан оптимизируемой функции. За счёт замены шага метода Ньютона на шаг недавно предложенного тензорного метода Ю.Е. Нестерова (2018 г.), а также за счёт специального обобщения условия подбора шага в проксимальном внешнем быстром градиентном методе удалось предложить оптимальный тензорный метод, использующий старшие производные. В частности, такой тензорный метод, использующий производные до третьего порядка включительно, оказался достаточно практичным ввиду сложности итерации, сопоставимой со сложностью итерации метода Ньютона. Таким образом, получено конструктивное решение задачи, поставленной Ю.Е. Нестеровым в 2018 г., об устранении зазора в точных нижних и завышенных верхних оценках скорости сходимости для имеющихся на данный момент тензорных методов порядка p ≥ 3.

Полный текст

Доступ закрыт

Об авторах

А. В. Гасников

Московский физико-технический институт (национальный исследовательский университет); Институт проблем передачи информации им. А.А. Харкевича Российской академии наук

Автор, ответственный за переписку.
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

Список литературы

  1. Arjevani Y., Shamir O., Shiff R. Oracle Complexity of Second-Order Methods for Smooth Convex Optimization // Math. Programming. 2017. P. 1-34.
  2. Nesterov Yu. Implementable Tensor Methods in Unconstrained Convex Optimization. Prepr. Univ. catholique de Louvain; Center for Operations Res. and Econometrics (CORE). 2018. № 2018005.
  3. Гасников А.В., Ковалев Д.А. Гипотеза об оптимальных оценках скорости сходимости численных методов выпуклой оптимизации высоких порядков // Компьют. исслед. и моделирование. 2018. Т. 10. № 3. С. 305-314.
  4. Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979.
  5. 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.
  6. Nesterov Yu. Introductory Lectures on Convex Optimization: A Basic Course. B.: Springer Science & Business Media, 2013. 87 p.
  7. Нестеров Ю.Е. Введение в выпуклую оптимизацию. М.: МЦНМО, 2010.
  8. 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.
  9. Nesterov Yu., Polyak B. Cubic Regularization of Newton Method and Its Global Performance // Math. Program. 2006. V. 108. № 1. P. 177-205.
  10. Гасников А.В. Современные численные методы оптимизации. Метод универсального градиентного спуска. М.: МФТИ, 2018. 166 с.
  11. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы. Построение и анализ. М.: Изд. дом “Вильямс”, 2009.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2019