RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Компьютерные исследования и моделирование:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Компьютерные исследования и моделирование, 2018, том 10, выпуск 3, страницы 305–314 (Mi crm253)  

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

СПЕЦИАЛЬНЫЙ ВЫПУСК

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

А. В. Гасниковa, Д. А. Ковалёвb

a Московский физико-технический институт, Россия, 141707, Московская область, г. Долгопрудный, Институтский пер., д. 9
b Институт передачи информации РАН, 127051, Россия, г. Москва, Большой Каретный пер., д. 19

Аннотация: В данной работе приводятся нижние оценки скорости сходимости для класса численных методов выпуклой оптимизации первого порядка и выше, т. е. использующих градиент и старшие производные. Обсуждаются вопросы достижимости данных оценок. Приведенные в статье оценки замыкают известные на данный момент результаты в этой области. Отметим, что замыкание осуществляется без должного обоснования, поэтому в той общности, в которой данные оценки приведены в статье, их стоит понимать как гипотезу. Опишем более точно основной результат работы. Пожалуй, наиболее известным методом второго порядка является метод Ньютона, использующий информацию о градиенте и матрице Гессе оптимизируемой функции. Однако даже для сильно выпуклых функций метод Ньютона сходится лишь локально. Глобальная сходимость метода Ньютона обеспечивается с помощью кубической регуляризации оптимизируемой на каждом шаге квадратичной модели функции [Nesterov, Polyak, 2006]. Сложность решения такой вспомогательной задачи сопоставима со сложностью итерации обычного метода Ньютона, т. е. эквивалентна по порядку сложности обращения матрицы Гессе оптимизируемой функции. В 2008 году Ю. Е. Нестеровым был предложен ускоренный вариант метода Ньютона с кубической регуляризацией [Nesterov, 2008]. В 2013 г. Monteiro–Svaiter сумели улучшить оценку глобальной сходимости ускоренного метода с кубической регуляризацией [Monteiro, Svaiter, 2013]. В 2017 году Arjevani–Shamir–Shiff показали, что оценка Monteiro–Svaiter оптимальна (не может быть улучшена более чем на логарифмический множитель на классе методов 2-го порядка) [Arjevani et al., 2017]. Также удалось получить вид нижних оценок для методов порядка $p\geq2$ для задач выпуклой оптимизации. Отметим, что при этом для сильно выпуклых функций нижние оценки были получены только для методов первого и второго порядка. В 2018 году Ю. Е. Нестеров для выпуклых задач оптимизации предложил методы 3-го порядка, которые имеют сложность итерации сопоставимую со сложностью итерации метода Ньютона и сходятся почти по установленным нижним оценкам [Nesterov, 2018]. Таким образом, было показано, что методы высокого порядка вполне могут быть практичными. В данной работе приводятся нижние оценки для методов высокого порядка $p\geq3$ для сильно выпуклых задач безусловной оптимизации. Работа также может рассматриваться как небольшой обзор современного состояния развития численных методов выпуклой оптимизации высокого порядка.

Ключевые слова: метод Ньютона, матрица Гессе, нижние оценки, чебышёвские методы, сверхлинейная сходимость.

Финансовая поддержка Номер гранта
Российский научный фонд 17-11-01027
Работа поддержана грантомРНФ № 17-11-01027


DOI: https://doi.org/10.20537/2076-7633-2018-10-3-305-314

Полный текст: PDF файл (135 kB)
Полный текст: http://crm.ics.org.ru/.../2685
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.86
Поступила в редакцию: 28.02.2018
Исправленный вариант: 12.05.2018
Принята в печать:24.05.2018

Образец цитирования: А. В. Гасников, Д. А. Ковалёв, “Гипотеза об оптимальных оценках скорости сходимости численных методов выпуклой оптимизации высоких порядков”, Компьютерные исследования и моделирование, 10:3 (2018), 305–314

Цитирование в формате AMSBIB
\RBibitem{GasKov18}
\by А.~В.~Гасников, Д.~А.~Ковалёв
\paper Гипотеза об оптимальных оценках скорости сходимости численных методов выпуклой оптимизации высоких порядков
\jour Компьютерные исследования и моделирование
\yr 2018
\vol 10
\issue 3
\pages 305--314
\mathnet{http://mi.mathnet.ru/crm253}
\crossref{https://doi.org/10.20537/2076-7633-2018-10-3-305-314}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/crm253
  • http://mi.mathnet.ru/rus/crm/v10/i3/p305

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. А. В. Гасников, Э. А. Горбунов, Д. А. Ковалёв, А. А. М. Мохаммед, Е. О. Черноусова, “Обоснование гипотезы об оптимальных оценках скорости сходимости численных методов выпуклой оптимизации высоких порядков”, Компьютерные исследования и моделирование, 10:6 (2018), 737–753  mathnet  crossref
  • Компьютерные исследования и моделирование
    Просмотров:
    Эта страница:306
    Полный текст:118
    Литература:25
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020