Course description
The course covers convex analysis, mathematical programming, being mainly a deep theoretical introduction to the world of optimization. The spring semester focuses on algorithms and involves intensive practical work.
Instructors
Alexander Gasnikov
Roland Hildebrand
Course materials
Материалы за 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, т.е., в большей окрестности, к ним добавляется условие Вейерштрасса. Оно является прототипом принципа максимума Понтрягина, центрального метода для решения задач оптимального управления динамическими системами. В этих задачах производная искомой функции не может принимать произвольные значения, а принадлежит фиксированному множеству управлений. Принцип максимума строит гамильтонову систему с разрывной правой частью, траекториями которой обязаны быть решения проблемы. Негладкость приводит к существованию особых режимов, которые полностью лежат на подмногообразии разрыва. Мы решим несколько типовых задач с помощью этого принципа, и на этих примерах покажем, какие бывают разные типы оптимального синтеза, т.е., зависимости функции управления от состояния динамической системы.
Exam program
1. The concept of numerical optimization methods. Gradient descent method. Complexity of optimization tasks. Strongly convex problems, convex (degenerate) problems, non-convex problems. Smooth, non-smooth tasks.
2. Regularization and restarts.
3. Ways to select a step in the methods. The fastest descent. Adaptive step selection method. Conjugate gradient method for minimizing quadratic functions. Heavy Polyak ball method. Accelerated gradient method (in different versions).
4. Optimization problems on sets of simple structure. Bragman divergence. The method of projection (sub-)gradient, the method of mirror descent.
5. The method of conditional gradient (Frank–Wolf–Levitin–Polyak). An example of the problem of minimizing a sparse quadratic form on a unit simplex.
6. Non-convex optimization. The Polyak-Loyasievich condition (PL) and global convergence of gradient descent. Example: reducing the solution of a system of nonlinear equations to an optimization problem with the PL condition. Convergence of gradient descent to a local extremum.
7. Unimodal functions of one variable. One-dimensional minimization methods (dichotomy method, golden section method, Fibonacci method).
8. Methods of small-dimensional optimization: the method of centers of gravity, the method of ellipsoids
9. The dual task. Weak and strong duality for convex optimization problems. The concept of (direct-) dual methods on the example of solving the problem of minimizing a convex separable functional with affine constraints by passing to the dual problem and solving it by the method of (accelerated) gradient descent.
10. General scheme of the penalty function method.
11. Newton's Method
12. Stochastic optimization. Minibatching and parallelization.
13. Randomized methods on the example of component-based and gradient-free methods.
14. The task of minimizing the sum of functions.
15.* Calculus of variations and the Euler–Lagrange equation. Lagrangian and Hamiltonian forms of the equation. Necessary optimality conditions, sufficient optimality conditions.
16.* Optimal control and maximum principle. Weierstrass condition for strong minima. The maximum principle. Special modes. Docking of non-singular with special trajectories.