О курсе
Курс охватывает выпуклый анализ, математическое программирование, являясь, в основном, глубоким теоретическим введением в мир оптимизации. Весенний семестр ориентируется на алгоритмы и предполагает плотную практическую работу.
27 и 28 мая будут экзамены у основной части потока, у 101 группы экзамен запланирован 18 июня. Детали см. тут.
Ведущие курса
Александр Гасников
Роланд Хильдебранд
Материалы курса
Литература
[2] Гасников А.В. Универсальный градиентный спуск. М.: МЦНМО, 2020
Книга по стохастической оптимизации. Также видеолекция по стохастической оптимизации от Александра Гасникова.
Материал, который по-простому поясняет суть методов одномерной оптимизации: Поиск наивкуснейшей шоколадки.
Лекция 1. Классификация задач. Сложность алгоритма и класса задач. Одномерный поиск. Субградиентный метод.
Лекция 2. Градиентный спуск и окрестности.
Система обыкновенных дифференциальных уравнений Коши, порождающая по схеме Эйлера градиентный спуск. Функции Ляпунова системы Коши в общем случае, в выпуклом случае. Геометрическая интерпретация градиентного спуска и способ выбора шага (введение константы Липшица градиента L) — шаг градиентного спуска понимается как переход к минимуму мажорирующего параболлоида вращения в текущей точке.
Сходимость градиентного спуска в невыпуклом случае по критерию нормы градиента. Доказательство оценки скорости сходимости. Пример функции Нестерова—Скокова унимодальной функции, для которой сходимость по норму градиента хорошая, а по сходимость по функции при этом очень медленная.
Сходимость градиентного спуска в выпуклом случае. Доказательство оценки скорости сходимости.
Наискорейший спуск. Формулировка результата (без доказательства) о том, что в теории наискорейший спуск (по худшему случаю) сходится не быстрее обычного градиентного спуска.
Сходимость градиентного спуска в сильно выпуклом случае. Понятие о числе обусловленности. Геометрия сходимости метода на примере множества уровней и антиградиентного векторного поля для функции f(x_1,x_2) = \mu/2 x_1^2 + L/2 x_2^2. Условие градиентного доминирования Поляка—Лоясиевича (как следствие условия сильной выпуклости). Доказательство теоремы (точнее схема доказательства) о скорости сходимости градиентного спуска в условии градиентного доминирования с помощью техники рестартов.
Условие Поляка—Лоясиевича и решение систем нелинейных уравнений с Якобианом полного ранга.
[1] Гасников А.В. Универсальный градиентный спуск. Параграф 1. М.: МЦНМО, 2021.
Лекция 3. Метод Ньютона для самосогласованных функций и метод Ньютона с кубической регуляризацией.
Лекция 4. Локальная сверхлинейная сходимость метода Ньютона. Понятия о тензорных методах, учебное пособие Гасникова А.В. Современные численные методы оптимизации. Метод универсального градиентного спуска, стр. 222 (локальная сходимость метода Ньютона). В книге употреблено неправильное слово (окрестность квадратичной скорости сходимости не «содержит», а содержится в открытом шаре. А если еще точнее, то не окрестность квадратичной скорости сходимости, а множество, задаваемое условием на норму градиента).
Про тензорные методы (в частности, рестарты для тензорных методов) написано на стр. 222-223 (но для лучшего понимания стоит прочитать несколько предыдущих страниц). Также в дополнение видеолекция Александра Гасникова для журнала «За науку»: От Ньютона до Ковалева.
Лекция 5. Метод тяжёлого шарика и ускоренный градиентный спуск Нестерова.
Лекция 6. Метод условного градиента, метод центров тяжести и метод эллипсоидов.
Лекция 7. Метод сопряжённых градиентов.
Лекция 8. Скорость сходимости для метода сопряжённых градиентов и градиентный спуск с проекцией.
Лекция 9. Условия ККТ и методы штрафных функций и барьеров.
Лекция 12. Вычислимая нижняя граница. Двойственная задача.
Лекция 13. Оптимальное управление.
Лекция 14. Градиентный спуск на примере обратной задачи, а также автоматическое дифференцирование.
Экзаменационная программа
Билеты
1. Понятие о численных методах оптимизации. Классы задач оптимизации. Сложность алгоритмов на классах задач. Сопротивляющийся оракул. (лекция 1)
2. Сильно выпуклые задачи, выпуклые (вырожденные) задачи, невыпуклые задачи. Гладкие, негладкие задачи. ([1] п. 2.1 - таблица 2.1 и ее обоснование, п. 2.4)
3. Метод градиентного спуска. Способ выбора шага. Сходимость в выпуклом и сильно выпуклом случае. Наискорейший спуск. ([2] параграф 1)
4. Сходимость градиентного спуска в невыпуклом случае по критерию нормы градиента (сходимость к локальному экстремуму). Пример функции Нестерова—Скокова. ([2] параграф 1)
5. Невыпуклая оптимизация. Примеры трудных задач невыпуклой оптимизации. Условие Поляка-Лоясиевича (ПЛ), глобальная сходимость градиентного спуска для невыпуклых задач. ([2] параграф 1)
6. Прямо-двойственные методы. Переход от обусловленной задаче к двойственной задаче. Уменьшение размерности задачи в случае выпуклости и сепарабельности функционала. ([2] параграф 4; [1] п. 1.9; лекция 12)
7. Гладкость двойственного функционала цены. Эффект регуляризации. ([2] параграф 4; [1] п. 1.9; лекция 12)
8. Метод тяжёлого шарика. Физическая интерпретация. Скорость сходимости по аргументу. ([1], п. 2.4; лекция 5)
9. Ускоренный метод Нестерова. Скорость сходимости по функционалу. ([1], п. 2.4; лекция 5)
10. Унимодальные функции одной переменной. Методы одномерной минимизации (метод дихотомии, метод золотого сечения). Скорость сходимости. ([1] п. 2.2.1; [2] упражнение 4.7; лекция 1)
11. Метод эллипсоидов. Отделяющий оракул. Скорость уменьшения объёма множества, в котором находится решение. ([1] п. 2.2.3; [2] упражнение 1.4; лекция 6)
12. Метод центров тяжести, скорость сходимости по функционалу. ([1] п. 2.2.2; [2] упражнение 1.4; лекция 6). Способы выбора шага в методах. Наискорейший спуск. Адаптивный способ выбора шага. ([2] замечание 1.4, стр. 58-60, упражнение 2.6)
14. Метод сопряжённых градиентов. Случай квадратичной функции. Применение к общему случаю, формулы Флетчера-Рива и др. Скорость сходимости в разных режимах (лекции 7,8)
15. Метод проекции (суб-)градиента. Скорость сходимости по функционалу в случае выпуклых C^1 функций. (лекция 8)
16. Метод проекции (суб-)градиента. Скорость сходимости по функционалу в случае выпуклых функций с липшицевым градиентом. Нижняя граница в методе градиента с проекцией. (лекции 8, 12)
17. Метод условного градиента (Франк-Вульфа). Примеры множеств, на которых легко минимизировать линейный функционал. Скорость сходимости по функционалу. Разреженность представления генерируемых точек. (лекция 6)
18. Метод Ньютона. Аффинная инвариантность. Самосогласованные функции. Ньютоновский декремент. Квадратичная скорость сходимости. ([2] Приложение; лекция 3)
19. Метод Ньютона с кубической регуляризацией. Избегание методом седловых точек. ([2] Приложение; лекция 3)
20. Метод множителей Лагранжа, условия ККТ, условие Слейтера. (лекция 9)
21. Штрафные функции. Барьеры. Примеры. Теоремы сходимости. (лекция 9)
22. Стохастическая оптимизация. Минибатчинг и распараллеливание. ([2] Приложение)
23. Рандомизированные методы. Рандомизация суммы. ([2] замечание 5.2 и Приложение)
24. *Оптимальное управление и принцип максимума. Принцип динамического программирования. Интерпретация сопряжённых переменных как градиент функционала цены. Особые режимы. (лекция 13)
25. *Решение обратных задач методом градиентного спуска. Учёт ограничений с помощью ввода множителей Лагранжа. (лекция 14)
26. *Принцип автоматического дифференцирования. Два разных способа расчёта производной. (лекция 14)
Билеты * по выбору, то есть если их вытянуть, можно отказаться их отвечать и перетянуть. Но можно согласиться и сдавать Роланду Хильдебранду.