Численные методы оптимизации

Программа

1. Понятие о численных методах оптимизации. Метод градиентного спуска. Сложность задач оптимизации. Сильно выпуклые задачи, выпуклые (вырожденные) задачи, невыпуклые задачи. Гладкие, негладкие задачи. Регуляризация и рестарты. О возможности вычислять градиент и автоматическом дифференцировании. Приложение к задаче оптимального управления.
2. Невыпуклая оптимизация. Условие Поляка-Лоясиевича (ПЛ) и глобальная сходимость градиентного спуска. Пример: сведение решение системы нелинейных уравнений к задаче оптимизации с условием ПЛ. Сходимость градиентного спуска к локальному экстремуму. Принцип множителей Лагранжа и теорема о неявной функции. Выпуклая оптимизация (напоминание основных фактов из прошлого семестра). Принцип множителей Лагранжа и теорема об отделимости точки от выпуклого множества гиперплоскостью (без доказательства).
3. Двойственная задача. Слабая и сильная двойственность для задач выпуклой оптимизации. Теорема о минмаксе (Фон Неймана, Сион-Какутани) (без доказательства). Седловые задачи. Коническая двойственность. Теоремы об альтернативах (Фаркаш) и их следствия (основная теорема финансовой математики об отсутствии арбитража; робастная оптимизация). Понятие о прямо-двойственных методах на примере решение задачи минимизации выпуклого сепарабельного функционала с аффинными ограничениями с помощью перехода к двойственной задаче и ее решения методом градиентного спуска.
4. Унимодальные функции одной переменной. Методы одномерной минимизации (метод дихотомии, метод золотого сечения, метод Фибоначчи). Задача о распределении ресурсов. Методы маломерной оптимизации: метод центров тяжести, метод эллипсоидов.
5. Способы выбора шага в методах. Наискорейший спуск. Адаптивный способ выбора шага. Сопряженные направления. Метод сопряженных градиентов для минимизации квадратичных функций. Метод сопряженных градиентов для решения задач выпуклой оптимизации. Метод тяжелого шарика Поляка. Ускоренный градиентный метод (метод подобных треугольников). Новый ускоренный градиентный метод с одномерными минимизациями.
6. Задачи оптимизации на множествах простой структуры. Дивергенция Брэгмана. Метод проекции (суб-)градиента, метод зеркального спуска. Метод условного градиента (Франк-Вульфа). Пример задачи минимизации квадратичной формы с разреженной положительно определенной матрицей на единичном симплексе.
7. Концепция (неточной) модели функции. Композитная оптимизация. Универсальный градиентный спуск и его ускоренный вариант. Проксимальный градиентный спуск. Ускоренный проксимальный метод (в варианте Монтейро-Свайтера). Каталист - общий способ ускорения различных неускоренных методов.
8. Метод Ньютона. Квазиньютоновские методы (LBFGS). Метод Ньютона с кубической регуляризацией. Тензорные методы.
9. Стохастическая оптимизация. Минибатчинг и распараллеливание. Рандомизированные методы на примере покомпонентных методов. Задача минимизации суммы функций.
10. Общая схема метода штрафных функций. Метод модифицированной функции Лагранжа. Методы внутренней точки. Понятие самосогласованного барьера. Методы параметризации целевых функций. Методы отслеживания центральной траектории.

Основная литература

1. Гасников А.В. Современные численные методы оптимизации. Метод универсального градиентного спуска. – М.: МФТИ, 2018. - 258 с. 2-е изд.: https://arxiv.org/ftp/arxiv/papers/1711/1711.00394.pdf
2. Презентации к некоторым частям курса доступны по ссылке (наиболее важными являются презентации 1-4)
3. Поляк Б.Т. Введение в оптимизацию. Изд. 2-ое, испр. и доп. – М.: ЛЕНАНД, 2014.
4. Boyd S., Vandenberghe L. Convex optimization. – Cambridge University Press, 2004.
5. Bubeck S. Convex optimization: algorithms and complexity // Foundations and Trends in Machine Learning. – 2015. – V. 8, N 3–4. – P. 231–357.
6. Nemirovski A. Advanced Nonlinear Programming // Lectures, ISyE 7683 Spring 2019. – URL: https://www2.isye.gatech.edu/~nemirovs/Trans_ModConvOpt.pdf