Непрерывная оптимизация (ТИ, АДИС, АПР, РС)

О курсе

Курс читается для студентов 3-го курса ПМИ ФКН ВШЭ в 3-4 модулях.

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

Важные ссылки
Карточка курса и программа
Канал в telegram для объявлений: t.me/optimizationHSE2020
Таблица успеваемости

Семинары

Группа	Преподаватель	Учебный ассистент
173 (ТИ)	Титов Александр Александрович	[Мохаммад Алкуса]
174 (АДИС)	Тюрин Александр Игоревич	[Александр Огальцов]
175 (РС)	Иванова Анастасия Сергеевна	[Дмитрий Макаренко]
176 (РС)	Иванова Анастасия Сергеевна	[Дмитрий Макаренко]
177	Иванова Анастасия Сергеевна	[Дмитрий Макаренко]

Правила выставления оценок

В курсе предусмотрено несколько форм контроля знания:

• Домашние работы (теоретические и практические)
• Письменная контрольная работа
• Экзамен
• Проект, включающий в себя теоретическую и практическую часть
• Самостоятельные работы на семинарах, проверяющие знание основных фактов с лекций и с ДЗ

Итоговая оценка вычисляется на основе оценки за работу в семестре и оценки за экзамен:

Итог = MIN{Округление(0.25 * ДЗ + 0.3 * Э + 0.4 * ПР + 0.15 * СР), 10}

ДЗ — средняя оценка за домашние работы

Э — оценка за экзамен

ПР — оценка за проект

СР — средняя оценка за самостоятельные работы на семинарах

Округление вниз.

Правила сдачи заданий

За каждый день просрочки после мягкого дедлайна снимается 1 балл. После жёсткого дедлайна работы не принимаются. Даже при опоздании на одну секунду. Сдавайте заранее. Есть исключения, о них написано ниже.

При обнаружении плагиата оценки за домашнее задание обнуляются всем задействованным в списывании студентам, а также подаётся докладная записка в деканат. Следует помнить, что при повторном списывании деканат имеет право отчислить студента.

При наличии уважительной причины пропущенную проверочную можно написать позднее, а дедлайн по домашнему заданию может быть перенесён. Дедлайн по домашнему заданию переносится на количество дней, равное продолжительности уважительной причины. Решение о том, является ли причина уважительной, принимает исключительно учебный офис.

Программа курса

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

Лекции

Дата	Преподаватель	Описание	Ссылка на лекцию
10.01.2020	Иванова А. С.	Зачем нужна оптимизация? Примеры задач невыпуклой оптимизации и нижние оценки сложности их решения. Понятие сопротивляющегося оракула (первый параграф пособия [1]). Введение в выпуклую оптимизацию. Основные понятия. Выпуклые функции, выпуклые множества. Теорема об отделимости. Принцип множителей Лагранжа	Lecture1.pdf
15.01.2020	Иванова А. С.	Основные вспомогательные факты факты выпуклой оптимизации (формула Демьянова Данскина, двойственная задача и т.д.). Примеры задач
22.01.2020	Тюрин А. И.	Градиентный спуск и его окрестности (все в евклидовой норме). Рассмотреть два случая когда оптимизация на всем пространстве и на выпуклом множестве простом относительно проектирования. Оценка скорости сходимости в выпуклом, сильно выпуклом случаях. В условии Поляка-Лоясиевича. В невыпуклом случае (первый параграф пособия [1]). Первые понятия об универсальных методах (второй и пятый параграф пособия [1]).
29.01.2020	Тюрин А. И.	Быстрый градиентный метод и его окрестности (все в евклидовой норме). Оценка скорости сходимости в выпуклом, сильно выпуклом случаях. Метод рестартов ( arXiv:1407.1537). Метод сопряженных градиентов. Понятие о нижних оценках скорости сходимости (первый параграф пособия [1]).
05.02.2020	Титов А. А.	Негладкая выпуклая оптимизация на выпуклых множествах. Понятие прокс-функции. Метод зеркального спуска. Метод зеркального спуска для задач с функциональными ограничениями (второй параграф пособия [1]).
12.02.2020	Гасников А. В.	Модельная общность для задач выпуклой оптимизации. Относительная гладкость, Неточность в градиенте и при проектировании. Градиентный спуск и быстрый градиентный метод в модельной общности. Универсальные методы в модельной общности (третий и пятый параграф пособия [1] и arXiv:1902.00990)
19.02.2020	Титов А. А.	Примеры выпукло-вогнутых седловых задач (мотивировочные примеры arXiv:1410.3118, arXiv:1501.02205) и монотонных вариационных неравенств ( конкурентное равновесие Вальраса в модели Эрроу-Дебре - см., например, книги Никайдо и Ашманова). Постановка задачи. Основные алгоритмы. Метод Mirror Prox и его работа в условиях неточно заданного градиента, неточного проектирования (можно по arXiv:1902.00990).
26.02.2020	Иванова А. С.	Прямо-двойственные методы. Прямо-двойственность градиентного спуска, быстрого градиентного спуска. Пример решения задачи сильно выпуклой оптимизации при аффинных ограничениях. Сходимость по норме градиента. Восстановление решение прямой задачи по последовательности точек, сгенерированной методом, решающим двойственную задачу (четвертый параграф пособия [1]).
04.03.2020	Шпирко	Регуляризация прямой задачи. Сглаживание прямой задачи, через регуляризацию двойственной (замечание 4.1 пособия [1], см. также [8]). Примеры приложения двойственного сглаживания (задачи вида минимизации функции максимума). Метод штрафных функций (четвертый параграф пособия [1]).
11.03.2020	Шпирко	Решение задач выпуклой оптимизации больших размеров с помощью субградиентных методов и метода условного градиента. Примеры: упражнение 1.6 пособия [1], Truss Topology Design.
18.03.2020	Шпирко	Квазиньютоновские методы BFGS, L-BFGS. Методы второго порядка. Метод Ньютона. Методы внутренней точки (см. [7])
01.04.2020	Шпирко	Методы внутренней точки (продолжение) (см. [7])
08.04.2020	Тюрин А. И.	Стохастический градиентный спуск. Понятие о минибатчинге. Адаптивные процедуры (приложение пособия [1] и arXiv:1911.08380). AdaGrad, Adam, метод Баха-Леви arXiv:1902.01637 - их преимущества и недостатки On the Convergence of Adam and beyond
15.04.2020	Иванова А. С.	Конструкция Каталист. Примеры приложения каталиста к покомпонентным методам и методам рандомизации суммы. Более подробный рассказ про покомпонентные/безградиентные методы и методы редукции дисперсии (минимизации функций вида суммы)
22.04.2020	Гасников А. В.	Связь оптимизации и анализа данных, статистики https://www.cs.cornell.edu/~sridharan/thesis.pdf
29.04.2020	Иванова А. С.	Введение в распределенную оптимизацию. Централизованная оптимизация на примере задачи о распределении ресурсов arXiv:1806.09071, arXiv:1909.13321, arXiv:1911.07354. Децентрализованная оптимизация arXiv:1904.09015, arXiv:1911.07363.

Полезные материалы

Книги

1. Гасников А. В. Современные численные методы оптимизации. Метод универсального градиентного спуска. – М.: МФТИ, 2018.
2. Гасников А. В. Презентации к избранным частям курса (наиболее важными являются презентации 1-4)
3. Поляк Б.Т. Введение в оптимизацию. Изд. 2-ое, испр. и доп. – М.: ЛЕНАНД, 2014.
4. Boyd S., Vandenberghe L. Convex optimization. – Cambridge University Press, 2004.
5. Bubeck S. Convex optimization: algorithms and complexity. – Foundations and Trends in Machine Learning, 2015. – V. 8, N 3–4. – P. 231–357.
6. Nemirovski A. Advanced Nonlinear Programming. – Lectures, ISyE 7683 Spring 2019.
7. Nesterov Yu. Lectures on convex optimization. – Springer, 2018.
8. Lan G. Lectures on optimization. Methods for Machine Learning, 2019.