Московский Физико - Технический Институт
Лекции: в зуме по пятницам 12.20 - 13.45
О курсе
Осенний семестр охватывает выпуклый анализ, математическое программирование, являясь, в основном, глубоким теоретическим введением в мир оптимизации. Весенний семестр ориентируется на алгоритмы и предполагает плотную практическую работу. Актуальные новости о курсе рассылаются в телеграм чате.
Материалы курса
Все материалы курса будут выкладываться по мере готовности на этот сайт. Для ознакомления доступны лекции Гасникова А.В. в Кавказском Математическом Центре.
Лекции прошлого года доступны по ссылке. А позапрошлого года по этой ссылке.
[1] Воронцова Е.А., Хильдебранд Р., Гасников А.В., Стонякин Ф.С. Современные численные методы оптимизации. Выпуклый анализ. М.: МФТИ, 2021
[2] Гасников А.В. Универсальный градиентный спуск. М.: МЦНМО, 2020
Прошедшие лекции
-
Введение в численные методы выпуклой оптимизации. Градиентный спуск, ускоренный градиентный спуск, метод Чебышёва, метод сопряженных градиентов.
- Ссылки: [1], п. 2.4
-
Градиентный спуск для задач невыпуклой оптимизации. Условие Поляка-Лоясиевича. Нижние оценки для градиентных методов на классе гладких выпуклых задач.
- Ссылки: см. [2], параграф 1, упражнение 1.3
- Видео: 📽
-
Методы решения малоразмерных задач выпуклой оптимизации. Метод центров тяжести, эллипсоидов.
- Ссылки: см. [2] упражнение 1.4 и [1], п. 2.2
- Видео: 📽
-
Негладкая оптимизация. Субградиентный метод. Неточный оракул.
- Ссылки: см. [2] первая половина параграфа 2, упражнения 2.1, 2.2, 2.6
- Видео: 📽
-
Методы проекции градиента. Композитная оптимизация. Введение стохастическую оптимизацию. Минимизация квадратичной формы на симплексе рандомизированным методом.
- Ссылки: см. [2] вторая половина параграфа 2, параграф 3 в части композитной оптимизации и замечание 5.2
- Видео: 📽
-
Стохастический градиентый спуск. Сходимость в условиях интерполируемости.
-
Оптимальные методы решения гладких и негладких выпуклых и сильно выпуклых задач оптимизации. Метод рестартов и регуляризации. Приводятся таблички, резюмирующие основные результаты, полученные в предыдущих лекциях.
- Ссылки: см. [1], п. 2.1 и [1], замечание 4.1, конец параграфа 5 и начало Приложения
- Видео: 📽
-
Материалы:
-
Метод условного градиента, универсальный градиентный метод.
- Ссылки: см. [1], п. 2.6 и [2], параграфы 2, 5
- Видео: 📽
-
Материалы:
-
Решения задач оптимизации с ограничениями. Принцип множителей Лагранжа, двойственная задача, теорема Сиона-Какутани, формула Демьянова-Данскина, регуляризация двойственной задачи. Метод штрафных функций.
- Ссылки: см. [2] все до примера 4.1(не включительно)). Также упражнения 4.1, 4.2, 4.4 и замечание 4.3
- Видео: 📽
-
Материалы:
-
Рандомизированные методы. Метод рандомизации суммы, метод редукции дисперсии, покомпонентные методы. Метод Ньютона и окрестность квадратичной сходимости
-
Полуопределенное программирование. Методы внутренней точки.
- Видео: 📽
-
Материалы:
-
Полуопределенное программирование. Приложения.
- Видео: 📽
-
Материалы:
-
Полуопределенное программирование.
Экзаменационная программа
В скобках указано, где можно прочитать о том, что входит в билет; однако настоятельно рекомендуем использовать материалы лекций, в которых по многим билетам содержится более точная информация:
- Понятие о численных методах оптимизации. Сильно выпуклые задачи, выпуклые (вырожденные) задачи, невыпуклые задачи. Гладкие, негладкие задачи. ([1] п. 2.1 - таблица 2.1 и ее обоснование, п. 2.4)
- Регуляризация и рестарты. Привести примеры! ([1] пп. 2.1, 2.10.8)
- Метод градиентного спуска. Выпуклые задачи. Невыпуклые задачи (сходимость к локальному экстремуму). ([2] параграф 1)
- Невыпуклая оптимизация. Примеры трудных задач невыпуклой оптимизации. ([2] параграф 1)
- Условие Поляка-Лоясиевича (ПЛ) и глобальная сходимость градиентного спуска для невыпуклых задач, целевая функция которых удовлетворяет условию (ПЛ). Как изменятся оценки скорости сходимости, если градиент доступен с аддитивным шумом в концепции относительной точности? Сведение решение системы нелинейных уравнений к задаче оптимизации с условием (ПЛ). ([2] параграф 1; [1] п. 2.11.1)
- Двойственная задача. Слабая и сильная двойственность для задач выпуклой оптимизации. Теорема о минмаксе (Фон Неймана, Сион-Какутани) (без доказательства). Понятие о прямо-двойственных методах на примере решение задачи минимизации выпуклого сепарабельного функционала с аффинными ограничениями с помощью перехода к двойственной задаче и ее решения методом градиентного спуска. ([2] параграф 4 (на лекции было изложение в варианте с регуляризацией - см. упражнение 4.4); [1] п. 1.9)
- Унимодальные функции одной переменной. Методы одномерной минимизации (метод дихотомии, метод золотого сечения). Задача о распределении ресурсов. ([1] п. 2.2.1; [1] упражнение 4.7)
- Методы маломерной оптимизации: метод центров тяжести, метод эллипсоидов. ([1] пп. 2.2.2, 2.2.3; [2] упражнение 1.4)
- Способы выбора шага в методах. Наискорейший спуск. Адаптивный способ выбора шага. ([2] замечание 1.4, стр. 58-60, упражнение 2.6)
- Сопряженные направления. Метод сопряженных градиентов для минимизации квадратичных функций. Метод сопряженных градиентов для решения задач выпуклой оптимизации. ([1], п. 2.4; [2] замечание 1.6)
- Метод тяжелого шарика Поляка. Метод Чебышева. Ускоренный градиентный метод (метод подобных треугольников). ([1], п. 2.4)
- Задачи оптимизации на множествах простой структуры. Дивергенция Брэгмана. Метод проекции (суб-)градиента, метод зеркального спуска. ([2], параграф 2; [1] п. 2.10)
- Метод условного градиента (Франк-Вульфа). Пример задачи минимизации квадратичной формы с разреженной положительно определенной матрицей на единичном симплексе. ([2] упражнение 1.6; [1] пп. 2.6, 3.5)
- Композитная оптимизация. Пример Tomogravity model. ([2] п. 2.10.8; [1] параграфы 3 и 5)
- Универсальный градиентный спуск. ([2] параграф 5)
- (билет только для досрочного экзамена, появляется при согласии студента) Проксимальный градиентный спуск. Ускоренный проксимальный метод. Каталист - общий способ ускорения различных неускоренных методов. ([2] параграф 3 и Приложение; [1] п. 2.7)
- (билет только для досрочного экзамена, появляется при согласии студента) Базовые представления о распределенной оптимизации (децентрализованной). ([2] Пример 4.1, упражнение 4.8 и текст после него)
- Метод Ньютона. Окрестность квадратичной скорости сходимости. Понятие о квазиньютоновских методах (LBFGS). ([2] Приложение)
- Стохастическая оптимизация. Минибатчинг и распараллеливание. ([2] Приложение; https://arxiv.org/pdf/1907.04232.pdf)
- Рандомизированные методы. Минимизация квадратичной формы на симплексе. Покомпонентные методы. ([2] замечание 5.2 и Приложение)
-
Задача минимизации суммы функций. Метод рандомизации суммы. Метод редукции дисперсии. ([2] замечание 1 Приложения и цитированная там литература)
-
Конические программы (задачи). Симметрические конуса. Самосогласованные барьеры. Коническая двойственность. Центральный путь. Прямой метод отслеживания центрального пути. Точки шкалировки. Прямо-двойственные методы. ([1], пп. 1.14.1, 1.14.8, 2.9.1--3, 2.9.7)
- Конично-квадратичные и полу-определённые ограничения. Максимальный и минимальный эллипсоиды для политопа. Оптимизация топологии фермы. Поиск функции Ляпунова. Робастное линейное программирование. ([1], пп. 1.14.3, 1.15.1--2, 3.3.1)
- Задача нахождения максимального разреза. $ \pi/2 $-теорема Нестерова. Задача о максимальной клике. Полиномиальная задача оптимизации. Конуса неотрицательных полиномов и сумм квадратов. Релаксации типа сумм квадратов. Точность аппроксимации суммами квадратов. ([1], пп. 1.14.7, 3.2.2--3)