🎢
Методы оптимизации. 2021

🎥 Zoom, ✉ Telegram

Московский Физико - Технический Институт

Лекции: в зуме по пятницам 12.20 - 13.45

О курсе

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

профессор МФТИ, д.ф.-м.н. Александр Владимирович Гасников

профессор университета Гренобль-Альпы, PhD, Роланд Хильдебранд

Материалы курса

Все материалы курса будут выкладываться по мере готовности на этот сайт. Для ознакомления доступны лекции Гасникова А.В. в Кавказском Математическом Центре.

Лекции прошлого года доступны по ссылке. А позапрошлого года по этой ссылке.

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

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

📎 gasnikov_book.pdf

Прошедшие лекции

  1. Введение в численные методы выпуклой оптимизации. Градиентный спуск, ускоренный градиентный спуск, метод Чебышёва, метод сопряженных градиентов.

    • Ссылки: [1], п. 2.4

  2. Градиентный спуск для задач невыпуклой оптимизации. Условие Поляка-Лоясиевича. Нижние оценки для градиентных методов на классе гладких выпуклых задач.

    • Ссылки: см. [2], параграф 1, упражнение 1.3
    • Видео: 📽

  3. Методы решения малоразмерных задач выпуклой оптимизации. Метод центров тяжести, эллипсоидов.

    • Ссылки: см. [2] упражнение 1.4 и [1], п. 2.2
    • Видео: 📽

  4. Негладкая оптимизация. Субградиентный метод. Неточный оракул.

    • Ссылки: см. [2] первая половина параграфа 2, упражнения 2.1, 2.2, 2.6
    • Видео: 📽

  5. Методы проекции градиента. Композитная оптимизация. Введение стохастическую оптимизацию. Минимизация квадратичной формы на симплексе рандомизированным методом.

    • Ссылки: см. [2] вторая половина параграфа 2, параграф 3 в части композитной оптимизации и замечание 5.2
    • Видео: 📽

  6. Стохастический градиентый спуск. Сходимость в условиях интерполируемости.

  7. Оптимальные методы решения гладких и негладких выпуклых и сильно выпуклых задач оптимизации. Метод рестартов и регуляризации. Приводятся таблички, резюмирующие основные результаты, полученные в предыдущих лекциях.

  8. Метод условного градиента, универсальный градиентный метод.

  9. Решения задач оптимизации с ограничениями. Принцип множителей Лагранжа, двойственная задача, теорема Сиона-Какутани, формула Демьянова-Данскина, регуляризация двойственной задачи. Метод штрафных функций.

    • Ссылки: см. [2] все до примера 4.1(не включительно)). Также упражнения 4.1, 4.2, 4.4 и замечание 4.3
    • Видео: 📽

    • Материалы:

      📎 Заметка_2_апр.2021_г.(2).pdf

  10. Рандомизированные методы. Метод рандомизации суммы, метод редукции дисперсии, покомпонентные методы. Метод Ньютона и окрестность квадратичной сходимости

  11. Полуопределенное программирование. Методы внутренней точки.

  12. Полуопределенное программирование. Приложения.

  13. Полуопределенное программирование.

Экзаменационная программа

В скобках указано, где можно прочитать о том, что входит в билет; однако настоятельно рекомендуем использовать материалы лекций, в которых по многим билетам содержится более точная информация:

  1. Понятие о численных методах оптимизации. Сильно выпуклые задачи, выпуклые (вырожденные) задачи, невыпуклые задачи. Гладкие, негладкие задачи. ([1] п. 2.1 - таблица 2.1 и ее обоснование, п. 2.4)
  2. Регуляризация и рестарты. Привести примеры! ([1] пп. 2.1, 2.10.8)
  3. Метод градиентного спуска. Выпуклые задачи. Невыпуклые задачи (сходимость к локальному экстремуму). ([2] параграф 1)
  4. Невыпуклая оптимизация. Примеры трудных задач невыпуклой оптимизации. ([2] параграф 1)
  5. Условие Поляка-Лоясиевича (ПЛ) и глобальная сходимость градиентного спуска для невыпуклых задач, целевая функция которых удовлетворяет условию (ПЛ). Как изменятся оценки скорости сходимости, если градиент доступен с аддитивным шумом в концепции относительной точности? Сведение решение системы нелинейных уравнений к задаче оптимизации с условием (ПЛ). ([2] параграф 1; [1] п. 2.11.1)
  6. Двойственная задача. Слабая и сильная двойственность для задач выпуклой оптимизации. Теорема о минмаксе (Фон Неймана, Сион-Какутани) (без доказательства). Понятие о прямо-двойственных методах на примере решение задачи минимизации выпуклого сепарабельного функционала с аффинными ограничениями с помощью перехода к двойственной задаче и ее решения методом градиентного спуска. ([2] параграф 4 (на лекции было изложение в варианте с регуляризацией - см. упражнение 4.4); [1] п. 1.9)
  7. Унимодальные функции одной переменной. Методы одномерной минимизации (метод дихотомии, метод золотого сечения). Задача о распределении ресурсов. ([1] п. 2.2.1; [1] упражнение 4.7)
  8. Методы маломерной оптимизации: метод центров тяжести, метод эллипсоидов. ([1] пп. 2.2.2, 2.2.3; [2] упражнение 1.4)
  9. Способы выбора шага в методах. Наискорейший спуск. Адаптивный способ выбора шага. ([2] замечание 1.4, стр. 58-60, упражнение 2.6)
  10. Сопряженные направления. Метод сопряженных градиентов для минимизации квадратичных функций. Метод сопряженных градиентов для решения задач выпуклой оптимизации. ([1], п. 2.4; [2] замечание 1.6)
  11. Метод тяжелого шарика Поляка. Метод Чебышева. Ускоренный градиентный метод (метод подобных треугольников). ([1], п. 2.4)
  12. Задачи оптимизации на множествах простой структуры. Дивергенция Брэгмана. Метод проекции (суб-)градиента, метод зеркального спуска. ([2], параграф 2; [1] п. 2.10)
  13. Метод условного градиента (Франк-Вульфа). Пример задачи минимизации квадратичной формы с разреженной положительно определенной матрицей на единичном симплексе. ([2] упражнение 1.6; [1] пп. 2.6, 3.5)
  14. Композитная оптимизация. Пример Tomogravity model. ([2] п. 2.10.8; [1] параграфы 3 и 5)
  15. Универсальный градиентный спуск. ([2] параграф 5)
  16. (билет только для досрочного экзамена, появляется при согласии студента) Проксимальный градиентный спуск. Ускоренный проксимальный метод. Каталист - общий способ ускорения различных неускоренных методов. ([2] параграф 3 и Приложение; [1] п. 2.7)
  17. (билет только для досрочного экзамена, появляется при согласии студента) Базовые представления о распределенной оптимизации (децентрализованной). ([2] Пример 4.1, упражнение 4.8 и текст после него)
  18. Метод Ньютона. Окрестность квадратичной скорости сходимости. Понятие о квазиньютоновских методах (LBFGS). ([2] Приложение)
  19. Стохастическая оптимизация. Минибатчинг и распараллеливание. ([2] Приложение; https://arxiv.org/pdf/1907.04232.pdf)
  20. Рандомизированные методы. Минимизация квадратичной формы на симплексе. Покомпонентные методы. ([2] замечание 5.2 и Приложение)

  21. Задача минимизации суммы функций. Метод рандомизации суммы. Метод редукции дисперсии. ([2] замечание 1 Приложения и цитированная там литература)

    📎 09226504.pdf

  22. Конические программы (задачи). Симметрические конуса. Самосогласованные барьеры. Коническая двойственность. Центральный путь. Прямой метод отслеживания центрального пути. Точки шкалировки. Прямо-двойственные методы. ([1], пп. 1.14.1, 1.14.8, 2.9.1--3, 2.9.7)

  23. Конично-квадратичные и полу-определённые ограничения. Максимальный и минимальный эллипсоиды для политопа. Оптимизация топологии фермы. Поиск функции Ляпунова. Робастное линейное программирование. ([1], пп. 1.14.3, 1.15.1--2, 3.3.1)
  24. Задача нахождения максимального разреза. $ \pi/2 $-теорема Нестерова. Задача о максимальной клике. Полиномиальная задача оптимизации. Конуса неотрицательных полиномов и сумм квадратов. Релаксации типа сумм квадратов. Точность аппроксимации суммами квадратов. ([1], пп. 1.14.7, 3.2.2--3)

👨‍🔬 Research group page

💎 fmin.xyz