Главная Лекции Семинары Задания Stepik Glip Проекты

Московский физико - технический институт

Семинары: Вторник 17:05, 532 ГК; Лекции: среда 12:20, 239 НК

Лектор: Гасников Александр Владимирович

Семинарист: Даня Меркулов - писать можно в любое время, могу ответить не сразу (если долго не отвечаю - смело пишите еще раз!)

grade

Справка

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

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

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

Лекции читаются по пособию, актуальная версия которого находится на архиве.

Экзаменационная программа доступна для скачивания и представлена ниже:

  1. Понятие о численных методах оптимизации. Сильно выпуклые задачи, выпуклые (вырожденные) задачи, невыпуклые задачи. Гладкие, негладкие задачи.
  2. Регуляризация и рестарты. Привести примеры!
  3. Принцип множителей Лагранжа и теорема о неявной функции. О сложности вычисления градиента и автоматическом дифференцировании. Приложение к задаче оптимального управления.
  4. Метод градиентного спуска. Выпуклые задачи. Невыпуклые задачи (сходимость к локальному экстремуму).
  5. Невыпуклая оптимизация. Примеры трудных задач невыпуклой оптимизации. Пример метода (второго порядка), сходящегося к локальному минимуму.
  6. Условие Поляка-Лоясиевича (ПЛ) и глобальная сходимость градиентного спуска для невыпуклых задач, целевая функция которых удовлетворяет условию (ПЛ). Как изменятся оценки скорости сходимости, если градиент доступен с аддитивным шумом в концепции относительной точности? Сведение решение системы нелинейных уравнений к задаче оптимизации с условием (ПЛ).
  7. Двойственная задача. Слабая и сильная двойственность для задач выпуклой оптимизации. Теорема о минмаксе (Фон Неймана, Сион-Какутани) (без доказательства). Седловые задачи. Коническая двойственность. Теоремы об альтернативах (Фаркаш) и их следствия (основная теорема финансовой математики об отсутствии арбитража; робастная оптимизация).
  8. Понятие о прямо-двойственных методах на примере решение задачи минимизации выпуклого сепарабельного функционала с аффинными ограничениями с помощью перехода к двойственной задаче и ее решения методом градиентного спуска.
  9. Унимодальные функции одной переменной. Методы одномерной минимизации (метод дихотомии, метод золотого сечения). Задача о распределении ресурсов.
  10. Методы маломерной оптимизации: метод центров тяжести, метод эллипсоидов.
  11. Способы выбора шага в методах. Наискорейший спуск. Правило Армихо и правило Голдстейна (факультативно). Адаптивный способ выбора шага.
  12. Сопряженные направления. Метод сопряженных градиентов для минимизации квадратичных функций. Метод сопряженных градиентов для решения задач выпуклой оптимизации.
  13. Метод тяжелого шарика Поляка. Ускоренный градиентный метод (метод подобных треугольников).  
  14. Задачи оптимизации на множествах простой структуры. Дивергенция Брэгмана. Метод проекции (суб-)градиента, метод зеркального спуска.
  15. Метод условного градиента (Франк-Вульфа). Пример задачи минимизации квадратичной формы с разреженной положительно определенной матрицей на единичном симплексе.
  16. Концепция (неточной) модели функции. Композитная оптимизация.
  17. Универсальный градиентный спуск и его ускоренный вариант.
  18. Проксимальный градиентный спуск. Ускоренный проксимальный метод. Каталист - общий способ ускорения различных неускоренных методов.
  19. Метод Ньютона. Окрестность квадратичной скорости сходимости. Понятие о квазиньютоновских методах (LBFGS).
  20. Стохастическая оптимизация. Минибатчинг и распараллеливание.
  21. Рандомизированные методы. Минимизация квадратичной формы на симплексе. Покомпонентные методы.
  22. Задача минимизации суммы функций.
  23. Общая схема метода штрафных функций. Метод модифицированной функции Лагранжа. Методы внутренней точки.
  24. Понятие самосогласованного барьера. Методы параметризации целевых функций. Методы отслеживания центральной траектории.
  25. Численные методы оптимизации на службе статистики и машинного обучения. Принцип максимального правдоподобия.

Домашние задания

Будут так же выкладываться на сайте по мере появления. Их сдача происходит через платформу stepik. Домашнее задание выкладывается по материалам семинара, через неделю после выкладывания его стоимость начинает линейно убывать до 0 к моменту жесткого дедлайна (3 недели после выкладывания). Если у Вас возникли какие - то адекватные проблемы со сроками сдачи дз - пишите мне.

Система выставления оценки

grade