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
Книга по стохастической оптимизации. Также видеолекция по стохастической оптимизации от Александра Гасникова.
Материал, который по-простому поясняет суть методов одномерной оптимизации: Поиск наивкуснейшей шоколадки.