Course description
Курс охватывает выпуклый анализ, математическое программирование, являясь, в основном, глубоким теоретическим введением в мир оптимизации.
Instructors
Александр Гасников
Роланд Хильдебранд
Course materials
Лекция 1: Классификация задач, Сложность алгоритма и класса задач, Метод градиентного спуска
Лекция 2: Градиентный спуск и его окрестности, по пособию «Современные численные методы оптимизации»
1. Сходимость градиентного спуска к экстремальной точке по критерию нормы градиента для задач гладкой (Липшицев градиент), но, вообще говоря, не выпуклой оптимизации (в начале параграфа 1).
2. Оптимальность градиентного метода в негладком выпуклом случае и в гладком в условиях градиентного доминирования (Поляка-Лоясиевича). Без доказательств. Неоптимальность градиентного спуска в выпуклом гладком случае. Квадратичная оптимизация и метод сопряженных градиентов, конспективно (замечание 1.6, для общего развития очень рекомендуется и замечание 1.5 посмотреть заодно — это уже не для квадратичной оптимизации). Метод тяжелого шарика Б.Т. Поляка и ускоренный метод Ю.Е. Нестерова для гладких задач выпуклой и сильно выпуклой оптимизации (все без доказательств и для задач безусловной оптимизации), формулы (1.38) — (1.40).
3. Табличка негладкий/гладкий (столбцы) и выпуклый/сильно выпуклый случаи. Заполнение таблички оценками оракульной сложности для (суб)градиентного спуска (так называют градиентный спуск в негладком случае, подразумевая, что вместо градиента можно ставить любой вектор из субдифференциала в рассматриваемой точке) и ускоренного метода.
4. Рестарты/регуляризация. Переход по таблице (в негладком случае рестарты см. упражнение 2.3, п. 2). Но главный источник — п. 2.1 приложенной далее книги (Хильдебранд и др.). Она и далее нам будет полезна. В частности, к первым трем лекциям нужно еще прочитать пп. 2.3, 2.4 этой книги, чтобы картина была полной (как раз тут можно найти и соображения из теории размерностей по выбору шага субградиентного метода, было на лекции 2 и спектральный аппарат анализа квадратичных задач с лекции 1 и современные ускоренные методы и их связь с методом тяжелого шарика из лекции 3).
Дополнительная литература: «Выпуклая оптимизация»
Обзорно стохастическая оптимизация изложена тут
Лекция 7: Стоимость итерации
1. Покомпонентные методы
Бубек С. 6.4 Random Coordinate Descent и «Современные численные методы оптимизации», Замечание 2 в Приложении
Литература
[2] Гасников А.В. Универсальный градиентный спуск. М.: МЦНМО, 2020
Книга по стохастической оптимизации. Также видеолекция по стохастической оптимизации от Александра Гасникова.
Материал, который по-простому поясняет суть методов одномерной оптимизации: Поиск наивкуснейшей шоколадки.
Для подготовки к экзамену по части стохастической оптимизации, вот здесь кратко описана простая мотивация.
Exam program
1. Понятие о численных методах оптимизации. Классы задач оптимизации ([2] п. 1.13). Сложность алгоритмов на классах задач. Сопротивляющийся оракул. (лекция 1)
2. Метод зеркального спуска ([1] параграф 2 в конце -- после замечания 2.1). Композитная оптимизация ([1] параграф 3, пример 3.1 и [2] п. 2.13.8, лекция 4)
3. (\delta,L)-оракул и связь между негладкой и гладкой оптимизацией ([1] параграф 2 и упражнение 2.1 , лекция 4
4. Метод градиентного спуска. Способ выбора шага. Случай квадратичной функции ([2] пп. 2.3, 2.4, лекция 1). Сходимость в выпуклом и сильно выпуклом случае. Наискорейший спуск. ([1] параграф 1, лекция 2
5. Невыпуклая оптимизация. Примеры трудных задач невыпуклой оптимизации. Условие Поляка-Лоясиевича (ПЛ), глобальная сходимость градиентного спуска дляневыпуклых задач. ([1] параграф 1, лекция 2)
6. Переход к двойственной задаче. Уменьшение размерности задачи в случае выпуклости и сепарабельности функционала. ([1] параграф 4; [2] п. 1.9; лекция 12)
7. Сглаживание двойственного функционала цены регуляризацией. ([1] параграф 4; [2] п. 1.9; лекция 3, лекция 12)
8. Метод тяжёлого шарика. Физическая интерпретация. Скорость сходимости. ([2], п. 2.4; лекция 3)
9. Ускоренный метод Нестерова. Скорость сходимости. ([1], п. 2.4; [2] п. 2.5, лекция 3)
10. Унимодальные функции одной переменной. Методы одномерной минимизации (метод дихотомии, метод золотого сечения). Скорость сходимости. ([2] п. 2.2.1; [1] упражнение 4.7; лекции 1, 7)
11. Метод эллипсоидов. Отделяющий оракул. Скорость сходимости. ([2] п. 2.2.3; [1] упражнение 1.4; лекция 7)
12. Метод центров тяжести, скорость сходимости. ([2] п. 2.2.2; [1] упражнение 1.4; лекция 7)
13. Метод сопряжённых градиентов ([1] замечания 1.5, 1.6, лекция 3)
14. Способы выбора шага в методах. Наискорейший спуск. Адаптивный способ выбора шага. ([1] замечание 1.4, стр. 58-60, упражнение 2.6, лекции 2,3)
15. Метод проекции (суб-)градиента. Скорость сходимости. Нижняя граница в методе градиента с проекцией. (лекция 12)
16. Метод условного градиента (Франк-Вульфа). Примеры множеств, на которых легко минимизировать линейный функционал. Скорость сходимости. Разреженность представления генерируемых точек. ([2], п. 2.6, лекция 7)
17. Покомпонентные методы ([1] Замечанипе 2 в Приложении 2, лекция 7)
18. Метод Ньютона. Аффинная инвариантность. Самосогласованные функции ([2] п. 2.9.1). Ньютоновский декремент. Квадратичная скорость локальной сходимости. ([1] Приложение; лекция 8)
19. Метод Ньютона с кубической регуляризацией. Избегание методом седловых точек. ([1] Приложение; лекция 9)
20. Метод множителей Лагранжа, условия ККТ, условие Слейтера. ([2], пп. 1.9.1., 1.9.5, лекция 11)
21. Штрафные функции. Барьеры. Примеры. Теоремы сходимости. (лекция 10)
22. Стохастическая оптимизация. Минибатчинг и распараллеливание. ([1] Приложение; статья, лекция 6)
23. Решение обратных задач методом градиентного спуска. Учёт ограничений с помощью ввода множителей Лагранжа. ([2], п. 2.11.2, лекция 14)
24. Принцип автоматического дифференцирования. Два разных способа расчёта производной. ([2] п. 3.9.1, лекция 14)