Numerical optimization methods of PMF FPMI, spring 2024

Wednesdays at 10:45 a.m.
1.17 GK

Course description

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

Instructors

Александр Гасников

Роланд Хильдебранд

Course materials

Все материалы за 2025 год

Лекция 1Классификация задач, Сложность алгоритма и класса задач, Метод градиентного спуска

Лекция 2: Градиентный спуск и его окрестности, по пособию «Современные численные методы оптимизации»

1. Градиентный спуск — дифференциальная уравнение Коши и функция Ляпунова, геометрический смысл градиентного спуска (принцип разделя и властвуй — замена на каждом шаге минимизации исходной функции более простой задачей — минимизацией касающегося целевой функции в данной точке параболоида вращения), как минимум мажорирующего параболлоида вращения (параграф 1, замечание 1.2 по части геометрической интерпретации).
2. Сходимость градиентного спуска в условиях Липишицевости целевой функции (~ 1 / \sqrt{k} — оптимальная скорость, параграф 2, в том числе упражнения в конце параграфа, упр. 2.6), в условиях Липшицевости градиента (~ 1 / k — неоптимальная скорость, ускоренные методы сходятся быстрее; параграф 3 (тут излишняя общность и может быть сложно читать, поэтому повезло тем, кто был на лекции, там все было без всякой модельной общности и все просто), но можно ограничиться упражнениями в конце параграфа 2, где показано за счет чего получается оценка лучше — упр. 2.6).
3. Сходимость градиентного спуска в условиях градиентного доминирования Поляка-Лоясиевича (как частный случай, сильной выпуклости). Линейная скорость сходимости. Приложение результата к решению системы нелинейных уравнений g(x) = 0 (параграф 1).

Лекция 3: Оптимальные градиентные методы и операции над алгоритмами и задачами, по пособию «Современные численные методы оптимизации»

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).

Дополнительная литература: «Выпуклая оптимизация»

Лекция 4: Метод зеркального спуска. Композитная оптимизация. (\delta,L)-оракул и связь между негладкой и гладкой оптимизацией, по пособию Гасникова «Современные численные методы оптимизации» и Хильдебранда и  др. «Выпуклая оптимизация»
1. Метод зеркального спуска (Гасников, параграф 2 в конце -- после замечания 2.1)
2. Композитная оптимизация (Гасников, параграф 3, пример 3.1 и Хильдебранд 2.13.8 Регуляризация и рестарты, см. также раздел 3.9)
3. \delta,L)-оракул и связь между негладкой и гладкой оптимизацией (Гасников, параграф 2 и упражнение 2.1)

Лекция 5: Стохастическая оптимизация. Первая глава книги Algorithmic Stochastic Convex Optimization
1. Принцип максимума правдоподобия. Пример схемы испытаний Бернулли.
2. Сходимость стохастического градиентного спуска для задач негладкой выпуклой стох. оптимизации.
3. Два подхода к решению задачи стохастической оптимизации: Монте-Карло (оффлайн), Стохастический градиентный спуск (онлайн).
4. Переобучение. Раняя остановка. Регулризация

Лекция 6. Стохастическая оптимизация. Гладкий случай
1. Гладкий случай. Батчирование, стр. 186
Для ускоренных процедур следует смотреть вот тут (но тут без доказательств)

Обзорно стохастическая оптимизация изложена тут

Лекция 7: Стоимость итерации

1. Покомпонентные методы

Бубек С. 6.4 Random Coordinate Descent и «Современные численные методы оптимизации», Замечание 2 в Приложении

2. Методы маломерной оптимизации. Метод центров тяжести и эллипсоидов в «Современные численные методы оптимизации» упр. 1.4 ( более подробно можно посмотреть в книге Бубека С.).
Пример метода золотого сечения (одномерный поиск) и покоординатного метода с одномерным поиском см. тут
3. Метод условного градиента Франк-Вульфа (см. книгу Бубека С. и пример там). С доказательством

Литература

[1] Воронцова Е.А., Хильдебранд Р., Гасников А.В., Стонякин Ф.С. Современные численные методы оптимизации. Выпуклый анализ. М.: МФТИ, 2021

[2] Гасников А.В. Универсальный градиентный спуск. М.: МЦНМО, 2020

Книга по стохастической оптимизации. Также видеолекция по стохастической оптимизации от Александра Гасникова.

Материал, который по-простому поясняет суть методов одномерной оптимизации: Поиск наивкуснейшей шоколадки.

Используя этот сайт, вы соглашаетесь с тем, что мы используем файлы cookie.