О курсе
Курс охватывает выпуклый анализ, математическое программирование, являясь, в основном, глубоким теоретическим введением в мир оптимизации. Весенний семестр ориентируется на алгоритмы и предполагает плотную практическую работу.
Ведущие курса
Александр Гасников
Роланд Хильдебранд
Материалы курса
Материалы за 2022 и 2021 годы доступны по ссылкам.
Материалы 2023 года:
Лекция 1. Сложность задач оптимизации (классы задач, понятие минимаксно оптимальный алгоритм на классе задач). Бинарный поиск. Субградиентный метод.
Сегодня мы говорили про сложность задач оптимизации. В частности, говорили, что выпуклые задачи - хорошие. Невыпуклые — плохие в плане поиска глобального минимума. Была приведена нижняя оценка из Теоремы 1.1.2 книги Нестерова Ю.Е. для невыпуклых задач (проклятие размерности). Далее говорили о выпуклых задач (M-Липшицевой целевой функцией). Рассмотрели метод деления отрезка пополам пп. 2.2.1 (поговорили о его обобщении на полупрямую - возникает, например, в методе насикорейшего спуска замечание 1.4, который тоже упомянули). Получили его оракульную сложность (число вычислений производной). Сформулировали результат о том, что полученная оценка минимаксно оптимальна (с точностбю до мультиплиативного множителя) на рассматриваемом классе задач (унимодальных и липшицевых) — без доказательства (детали см. в классической книге Немировского-Юдина).
Далее ушли от одномерной оптимизации в пространство большой размерности и привели субградиентный метод. Поговорили о его скорости сходимости, о том, что он генерирует ограниченную последовательность точек (последовательность лежит в шаре B_{\sqrt{2R}}(x^0)). Поговорили о том, что можно выбирать шаг из соображений размерности (\Pi-теорема теории размерностей была сформулирована и адаптивно — детали см.в упражнении 2.6 и п. 2.3. Также упомянули про почти оптимальность классического градиентного метода (он не оптимален на множитель всего лишь \sqrt{2} — см. упражнение 2.1 — на лекции обоснования не было, но очень рекомендуем внимательно разобрать это упражнение!
Семинар
Нижние оценки и способы их получения
Упражнения 1.3 и 2.1 — ускоренные методы и субградиентные
3 Methods with linear convergence, II
Лекция 2. Численные методы оптимизации и примеры.
*Квадратичная задача с реальными данными международного Банка.
*Статья с визуализацией про метод тяжелого шарика.
*Наглядная визуализация простых методов оптимизации.
*Пример Вульфа. Влияние негладкости на поведение градиентного метода.
Семинар
Попробовать рассказать про некоторые современные подходы к построению методов оптимизации и изучению скорости из сходимости
Пакет PEPit (Также материал для ознакомления)
Лекция 3. Субградиентные методы. Градиентный спуск (выпуклый и невыпуклый случай). Условия Поляка-Лоясиевича.
Метод проекции субградиента пп. 2.3 (тут приведена даже немного более общая версия — с переключением).
Метод градиентного спуска параграф 1 (до замечания 1.2)
По поводу условия Поляка-Лоясиевича и рестартов, см. также вот тут
Семинар
Рассказать субградиентный метод для разреженных задач большой размерности
Рассказать субградиентный метод с переключениями и на его примере рассказать задачу Truss Topology design 2.3, 3.3.2.
Примечательно, что тут попутно показывается прямо-двойственность субградиентных методов.
Лекция 4. Вокруг градиентного спуска.
Обсуждалась связь градиентного спуска и субградиентного спуска (для задач безусловной оптимизации, но это, на самом деле, не важно, для оптимизации на множествах простой структуры все будет точно также) — разница с выбором шага. Был рассмотрен единый подход, позволяющий погрузить задачу негладкую в гладкую (параграф 2). Также вокруг этой темы обсуждалась идея универсального метода — настройка на гладкость задачи (параграф 5) и модельная общность в части композитной оптимизации параграф 3, см. также параграф 5 и цитированную там литературу (задача LASSO). В конце лекции разбирались квазивыпуклая неглакдкая оптимизация по упражнению 2.7
Семинар
Пояснить, почему метод тяжелого шарика сходится ускоренным образом в окрестности решения — см. книгу Б.Т. Поляка Введение в оптимизацию. Тем самым, будет продемонстрирован локальный анализ скорости сходимости методов с помощью первого метода Ляпунова. Также как пример градиентного или ускоренного градиентного метода в бесконечномерном пространстве можно рассказать раздел 2.11.2
Лекция 5. Вокруг метода зеркального спуска.
Прокс-функция, дивергенция Брэгмана, энтропия, дивергенция Кульбака-Ляйблера, экспоненциальное взвешивание, ускоренный метод Нестерова
Стр. 85-89, 98-103 (для более полного знакомства см. параграф 3, в том числе упр. 3.7 и параграф 2.10 в части описания ускоренного метода с общим проксом — это все дополнительные материалы).
Семинар
Разобрать конкретную задачу — минимизации квадратичной формы на симплексе с помощью ускоренного метода. Показать, что энтропия 1 — сильно выпуклая в 1 норме на единичном симплексе. Показать, как выбирать прокс-функцию на шаре в 1-норме. Исследовать вопрос, как «проектироваться» согласно такой функции, в 5 главе довольно много про все это. В частности, полезно рассмотреть задачу о том, как задавать прокс-сетап на прямом произведении симплексов.
Лекция 6. Ускоренные градиентные методы. Регуляризация и рестарты.
Простейшая форма записи ускоренного метода и метода тяжелого шарика стр. 41-43 (рекомендуется также посмотреть все упражнение 1.3, а не только эти страницы; также рекомендуется посмотреть раздел 2.4). Метод сопряженных градиентов Замечание 1.6.
Регуляризация и рестарты раздел 2.1 (более подробно в разделе 2.10.8)
Семинар
Рассказать упр. 2.3 (рестарты для субградиентного метода; на лекции рассказывались рестарты для ускоренного метода).
Лекция 7. Метод условного градиента
Описание и доказательство оценки скорости сходимости метода условного градиента 2.6 (Франк-Вульфа-Левитина-Поляка). В качестве примера разбиралась задача из упр. 1.6 (см. также раздел 3). Более подробно о методах условного градиента см. в книге.
Семинар
Пример из книги раздел 3.3. Яркий пример (с физической интерпретацией метода условного градиента есть вот тут в пункте 2.1.2, только тут неправильно метод назван: вместо «метод Франка-Вульфа» правильно «метод Франк-Вульфа-Левитина-Поляка».
Также можно взять пример из этой статьи (но тут долго разбираться). Также можно взять какие-то примеры вот отсюда
Лекция 8. Методы маломерной оптимизации
Метод центров тяжести. Метод эллипсоидов. (Б.Т. Поляк Введение в оптимизацию. Глава 5, параграф 4).
Также немного рассказывались окрестности (полиномиальная сложность в битовой арифметике задачи ЛП — стр. 63-70, метод Hit and Run.
Также обо всем об этом можно прочитать вот тут в разделах 2.2.2, 2.2.3
Семинар
Упр. 4.7 и раздел 2.10.8 (Tomogravity model) + раздел 3.7
Лекция 9. Задачи с ограничениями непростой структуры. Метод Ньютона
Минимизация сепарабельного функционала при аффинных ограничениях. Децентрализованная оптимизация. Прямо-двойственность метода первая часть параграфа 4 и пример 4.1. Условие Слейтера упр. 4.1. Метод штрафных функций замечание 4.3. Метод Ньютона стр. 221-222.
Семинар
Методы распределенной оптимизации — прямой и двойственный подходы, пример 4.1. Более подробно вот тут
Лекция 10. Стохастическая оптимизация
Стохастический градиентный спуск (выпуклый и сильно выпуклый случай) в евклидовом прокс сетапе (с проектирование). Стохастический метод зеркального спуска (без доказательства). Пример оптимизации квадратичной формы рандомизированным методом на симплексе. AdaGrad (без доказательства). Стохастический градиентный спуск в условиях гладкости, батчирование. Приложение. Возможность ускорения. Перепараметризация (неускоренный случай) и (ускоренный) без доказательства.
Семинар
Пример решения задачи минимизации квадратичной формы на симплексе с помощью стохастического зеркального спуска. Пример нащупывания равновесия в антагонистической матричной игре.
Лекция 11. Рандомизированные методы
Ускоренные и неускоренные покомпонентные методы и п. 6.4. Безградиентные методы (l_2-сглаживание и теорема Стокса). Методы с редукцией дисперсии См. также приложение пособия.
Также упоминался прием О.Н. Граничина — см. стр. 205 (23. (Задача об обнаружении сигнала на фоне не случайных помех, Фишер–Граничин–Поляк)
Семинар
Мотивировочные примеры есть в исходной статье.
Лекция 12. Вариационное исчисление
Предметом вариационного исчисления является оптимизация в бесконечномерных пространствах, а именно, в пространствах дважды непрерывно или кусочно-непрерывно дифференцируемых функций. Минимизируется функционал цены, задающийся интегралом от выражения, зависящего от искомой функции и её первой производной. Минимизация происходит при краевых условиях, которые налагаются на концы интервала интегрирования и значения функции в них. Будет выведен ряд необходимых условий оптимальности: уравнения Эйлера (-Лагранжа), условие Лежандра, условия трансверсальности, условие отсутствия фокальных точек. Эти условия необходимы для локального минимума в норме C^1. В точках разрыва производной должно быть выполнено условие Вейерштрасса-Эрдмана. Достаточным условием является условие Гамильтона-Якоби. В качестве примеров рассмотрим задачу о брахистохроне и о поверхности минимальной площади при условии инвариантности относительно вращений.
Лекция 13. Оптимальное управление
На предыдущей лекции проходились необходимые условия для локального минимума в норме C^1. Для локального минимума в норме C^0, т.е., в большей окрестности, к ним добавляется условие Вейерштрасса. Оно является прототипом принципа максимума Понтрягина, центрального метода для решения задач оптимального управления динамическими системами. В этих задачах производная искомой функции не может принимать произвольные значения, а принадлежит фиксированному множеству управлений. Принцип максимума строит гамильтонову систему с разрывной правой частью, траекториями которой обязаны быть решения проблемы. Негладкость приводит к существованию особых режимов, которые полностью лежат на подмногообразии разрыва. Мы решим несколько типовых задач с помощью этого принципа, и на этих примерах покажем, какие бывают разные типы оптимального синтеза, т.е., зависимости функции управления от состояния динамической системы.
Экзаменационная программа
1. Понятие о численных методах оптимизации. Метод градиентного спуска. Сложность задач оптимизации. Сильно выпуклые задачи, выпуклые (вырожденные) задачи, невыпуклые задачи. Гладкие, негладкие задачи.
2. Регуляризация и рестарты.
3. Способы выбора шага в методах. Наискорейший спуск. Адаптивный способ выбора шага. Метод сопряженных градиентов для минимизации квадратичных функций. Метод тяжелого шарика Поляка. Ускоренный градиентный метод (в разных вариантах).
4. Задачи оптимизации на множествах простой структуры. Дивергенция Брэгмана. Метод проекции (суб-)градиента, метод зеркального спуска.
5. Метод условного градиента (Франк–Вульфа–Левитина–Поляка). Пример задачи минимизации разреженной квадратичной формы на единичном симплексе.
6. Невыпуклая оптимизация. Условие Поляка-Лоясиевича (ПЛ) и глобальная сходимость градиентного спуска. Пример: сведение решения системы нелинейных уравнений к задаче оптимизации с условием ПЛ. Сходимость градиентного спуска к локальному экстремуму.
7. Унимодальные функции одной переменной. Методы одномерной минимизации (метод дихотомии, метод золотого сечения, метод Фибоначчи).
8. Методы маломерной оптимизации: метод центров тяжести, метод эллипсоидов
9. Двойственная задача. Слабая и сильная двойственность для задач выпуклой оптимизации. Понятие о (прямо-)двойственных методах на примере решение задачи минимизации выпуклого сепарабельного функционала с аффинными ограничениями с помощью перехода к двойственной задаче и ее решения методом (ускоренного) градиентного спуска.
10. Общая схема метода штрафных функций.
11. Метод Ньютона
12. Стохастическая оптимизация. Минибатчинг и распараллеливание.
13. Рандомизированные методы на примере покомпонентных и безградиентных методов.
14. Задача минимизации суммы функций.
15.* Вариационное исчисление и уравнение Эйлера–Лагранжа. Лагранжева и гамильтонова формы уравнения. Необходимые условия оптимальности, достаточные условия оптимальности.
16.* Оптимальное управление и принцип максимума. Условие Вейерштрасса для сильных минимумов. Принцип максимума. Особые режимы. Стыковка неособых с особыми траекториями.