|
|
| Строка 1: |
Строка 1: |
| − | == О курсе ==
| |
| | | | |
| − | Курс читается для студентов 3-го курса [https://cs.hse.ru/ami ПМИ ФКН ВШЭ] в 3-4 модулях.
| |
| − |
| |
| − | '''Лектор:''' [https://www.hse.ru/org/persons/200501657 Кро́потов Дмитрий Александрович]
| |
| − |
| |
| − |
| |
| − | === Полезные ссылки ===
| |
| − |
| |
| − | [https://www.hse.ru/ba/ami/courses/292667735.html Карточка курса и программа]
| |
| − |
| |
| − | <!-- Почта для сдачи домашних заданий (на самом деле задания сдаются в AnyTask, но если он не работает, то присылайте на почту): hse.cs.ml+<номер группы>@gmail.com (например, hse.cs.ml+171@gmail.com) -->
| |
| − |
| |
| − | Канал в telegram для объявлений: https://t.me/optimizationHSE2020
| |
| − |
| |
| − | Чат в telegram для обсуждений (предназначение чата до конца не ясно, вопросы может быть правильнее задавать в чатах групп):
| |
| − |
| |
| − | Ссылка на курс в Anytask:
| |
| − |
| |
| − | Таблица с оценками
| |
| − |
| |
| − | === Семинары ===
| |
| − |
| |
| − | {| class="wikitable"
| |
| − | |-
| |
| − | ! Группа !! Преподаватель !! Учебный ассистент
| |
| − | |-
| |
| − | | 173 (ТИ) || [https://www.hse.ru/org/persons/? Титов Александр Александрович] || [Мохаммад Алкуса]
| |
| − | |-
| |
| − | | 174 (АДИС) || [https://www.hse.ru/org/persons/161002023 Тюрин Александр Игоревич] || [Александр Огальцов]
| |
| − | |-
| |
| − | | 175 (РС) || [https://www.hse.ru/org/persons/320473622 Иванова Анастасия Сергеевна] || [Дмитрий Макаренко]
| |
| − | |-
| |
| − | | 176 (РС) || [https://www.hse.ru/org/persons/320473622 Иванова Анастасия Сергеевна] || [Дмитрий Макаренко]
| |
| − | |-
| |
| − | | 177 || [https://www.hse.ru/org/persons/320473622 Иванова Анастасия Сергеевна] || [Дмитрий Макаренко]
| |
| − | |-
| |
| − | |}
| |
| − |
| |
| − | === Правила выставления оценок ===
| |
| − |
| |
| − | В курсе предусмотрено несколько форм контроля знания:
| |
| − |
| |
| − | * Домашние работы (теоретические и практические)
| |
| − | * Письменная контрольная работа
| |
| − | * Экзамен
| |
| − | * Проект, включающий в себя теоретическую и практическую часть
| |
| − | * Самостоятельные работы на семинарах, проверяющие знание основных фактов с лекций и с ДЗ
| |
| − |
| |
| − | Итоговая оценка вычисляется на основе оценки за работу в семестре и оценки за экзамен:
| |
| − |
| |
| − | Итог = MIN{Округление(0.15 * ДЗ + 0.20 * КР + 0.3 * Э + 0.35 * ПР + 0.1 * СР), 10}
| |
| − |
| |
| − | ДЗ — средняя оценка за домашние работы
| |
| − |
| |
| − | КР — оценка за контрольную работу
| |
| − |
| |
| − | Э — оценка за экзамен
| |
| − |
| |
| − | ПР — оценка за проект
| |
| − |
| |
| − | СР — средняя оценка за самостоятельные работы на семинарах
| |
| − |
| |
| − | Округление вниз.
| |
| − |
| |
| − | === Правила сдачи заданий ===
| |
| − |
| |
| − | За каждый день просрочки после мягкого дедлайна снимается 1 балл. После жёсткого дедлайна работы не принимаются. Даже при опоздании на одну секунду. Сдавайте заранее. Есть исключения, о них написано ниже.
| |
| − |
| |
| − | При обнаружении плагиата оценки за домашнее задание обнуляются всем задействованным в списывании студентам, а также подаётся докладная записка в деканат. Следует помнить, что при повторном списывании деканат имеет право отчислить студента.
| |
| − |
| |
| − | При наличии уважительной причины пропущенную проверочную можно написать позднее, а дедлайн по домашнему заданию может быть перенесён. Дедлайн по домашнему заданию переносится на количество дней, равное продолжительности уважительной причины. Решение о том, является ли причина уважительной, принимает исключительно учебный офис.
| |
| − |
| |
| − | == Программа курса ==
| |
| − | # Понятие о численных методах оптимизации. Метод градиентного спуска. Сложность задач оптимизации. Сильно выпуклые задачи, выпуклые (вырожденные) задачи, невыпуклые задачи. Гладкие, негладкие задачи. Регуляризация и рестарты. О возможности вычислять градиент и автоматическом дифференцировании. Приложение к задаче оптимального управления.
| |
| − | # Невыпуклая оптимизация. Условие Поляка-Лоясиевича (ПЛ) и глобальная сходимость градиентного спуска. Пример: сведение решение системы нелинейных уравнений к задаче оптимизации с условием ПЛ. Сходимость градиентного спуска к локальному экстремуму. Принцип множителей Лагранжа и теорема о неявной функции. Выпуклая оптимизация. Принцип множителей Лагранжа и теорема об отделимости точки от выпуклого множества гиперплоскостью (без доказательства).
| |
| − | # Двойственная задача. Слабая и сильная двойственность для задач выпуклой оптимизации. Теорема о минмаксе (Фон Неймана, Сион-Какутани) (без доказательства). Седловые задачи. Коническая двойственность. Теоремы об альтернативах (Фаркаш) и их следствия (основная теорема финансовой математики об отсутствии арбитража; робастная оптимизация). Понятие о прямо-двойственных методах на примере решение задачи минимизации выпуклого сепарабельного функционала с аффинными ограничениями с помощью перехода к двойственной задаче и ее решения методом градиентного спуска.
| |
| − | # Унимодальные функции одной переменной. Методы одномерной минимизации (метод дихотомии, метод золотого сечения, метод Фибоначчи). Задача о распределении ресурсов. Методы маломерной оптимизации: метод центров тяжести, метод эллипсоидов.
| |
| − | # Способы выбора шага в методах. Наискорейший спуск. Правило Армихо и правило Голдстейна. Адаптивный способ выбора шага. Сопряженные направления. Метод сопряженных градиентов для минимизации квадратичных функций. Метод сопряженных градиентов для решения задач выпуклой оптимизации. Метод тяжелого шарика Поляка. Ускоренный градиентный метод (в разных вариантах: линейный каплинг, метод подобных треугольников). Новый ускоренный градиентный метод (на базе метода линейного каплинга) с одномерными минимизациями.
| |
| − | # Задачи оптимизации на множествах простой структуры. Дивергенция Брэгмана. Метод проекции (суб-)градиента, метод зеркального спуска. Метод условного градиента (Франк-Вульфа). Пример задачи минимизации квадратичной формы с разреженной положительно определенной матрицей на единичном симплексе.
| |
| − | # Концепция (неточной) модели функции. Композитная оптимизация. Универсальный градиентный спуск и его ускоренный вариант. Проксимальный градиентный спуск. Ускоренный проксимальный метод (в варианте Монтейро-Свайтера). Каталист - общий способ ускорения различных неускоренных методов.
| |
| − | # Метод Ньютона. Квазиньютоновские методы (LBFGS). Метод Ньютона с кубической регуляризацией. Тензорные методы. Ускоренные тензорные методы.
| |
| − | # Стохастическая оптимизация. Минибатчинг и распараллеливание. Рандомизированные методы на примере покомпонентных и безградиентных методов. Задача минимизации суммы функций.
| |
| − | # Общая схема метода штрафных функций. Метод модифицированной функции Лагранжа. Методы внутренней точки. Понятие самосогласованного барьера. Методы параметризации целевых функций. Методы отслеживания центральной траектории.
| |
| − | #<nowiki>*</nowiki> Распределенная оптимизация на примере решения задач выпуклой оптимизации функционалов вида суммы функций.
| |
| − | #<nowiki>**</nowiki> Численные методы оптимизации на службе статистики и машинного обучения. Принцип максимального правдоподобия и метод Поляка-Юдицкого, адаптивные методы стохастической оптимизации. (эта лекция не входит в основную программу; она будет рассказан только в случае наличия времени)
| |
| − | == Лекции ==
| |
| − |
| |
| − | {| class="wikitable"
| |
| − | |-
| |
| − | ! Дата !! Преподаватель !! Описание !! Дополнительно
| |
| − | |-
| |
| − | | 10.01.2020 || [https://www.hse.ru/org/persons/320473622 Иванова А. С.] || Зачем нужна оптимизация? Примеры задач невыпуклой оптимизации и нижние оценки сложности их решения. Понятие сопротивляющегося оракула (первый параграф пособия [[https://arxiv.org/ftp/arxiv/papers/1711/1711.00394.pdf 1]]). Введение в выпуклую оптимизацию. Основные понятия. Выпуклые функции, выпуклые множества. Теорема об отделимости. Принцип множителей Лагранжа ||
| |
| − | |-
| |
| − | | 15.01.2020 || [https://www.hse.ru/org/persons/320473622 Иванова А. С.] || Основные вспомогательные факты факты выпуклой оптимизации (формула Демьянова Данскина, двойственная задача и т.д.). Примеры задач ||
| |
| − | |-
| |
| − | | 22.01.2020 || [https://www.hse.ru/org/persons/161002023 Тюрин А. И.]|| Градиентный спуск и его окрестности (все в евклидовой норме). Рассмотреть два случая когда оптимизация на всем пространстве и на выпуклом множестве простом относительно проектирования. Оценка скорости сходимости в выпуклом, сильно выпуклом случаях. В условии Поляка-Лоясиевича. В невыпуклом случае (первый параграф пособия [[https://arxiv.org/ftp/arxiv/papers/1711/1711.00394.pdf 1]]). Первые понятия об универсальных методах (второй и пятый параграф пособия [[https://arxiv.org/ftp/arxiv/papers/1711/1711.00394.pdf 1]]). ||
| |
| − | |-
| |
| − | | 29.01.2020 || [https://www.hse.ru/org/persons/161002023 Тюрин А. И.]|| Быстрый градиентный метод и его окрестности (все в евклидовой норме). Оценка скорости сходимости в выпуклом, сильно выпуклом случаях. Метод рестартов ( [https://arxiv.org/abs/1407.1537 arXiv:1407.1537]). Метод сопряженных градиентов. Понятие о нижних оценках скорости сходимости (первый параграф пособия [[https://arxiv.org/ftp/arxiv/papers/1711/1711.00394.pdf 1]]). ||
| |
| − | |-
| |
| − | | 05.02.2020 || [https://www.hse.ru/org/persons/? Титов А. А.]|| Негладкая выпуклая оптимизация на выпуклых множествах. Понятие прокс-функции. Метод зеркального спуска. Метод зеркального спуска для задач с функциональными ограничениями (второй параграф пособия [[https://arxiv.org/ftp/arxiv/papers/1711/1711.00394.pdf 1]]). ||
| |
| − | |-
| |
| − | | 12.02.2020 || [https://www.hse.ru/org/persons/49503846 Гасников А. В.] || Модельная общность для задач выпуклой оптимизации. Относительная гладкость, Неточность в градиенте и при проектировании. Градиентный спуск и быстрый градиентный метод в модельной общности. Универсальные методы в модельной общности (третий и пятый параграф пособия [[https://arxiv.org/ftp/arxiv/papers/1711/1711.00394.pdf 1]] и [https://arxiv.org/abs/1902.00990 arXiv:1902.00990]) ||
| |
| − | |-
| |
| − | | 19.02.2020 || [https://www.hse.ru/org/persons/? Титов А. А.]|| Примеры выпукло-вогнутых седловых задач (мотивировочные примеры [https://arxiv.org/abs/1410.3118 arXiv:1410.3118,] [https://arxiv.org/abs/1501.02205 arXiv:1501.02205]) и монотонных вариационных неравенств ( конкурентное равновесие Вальраса в модели Эрроу-Дебре - см., например, книги Никайдо и Ашманова). Постановка задачи. Основные алгоритмы. Метод Mirror Prox и его работа в условиях неточно заданного градиента, неточного проектирования (можно по [https://arxiv.org/abs/1902.00990 arXiv:1902.00990]). ||
| |
| − | |-
| |
| − | | 26.02.2020 || [https://www.hse.ru/org/persons/320473622 Иванова А. С.]|| Прямо-двойственные методы. Прямо-двойственность градиентного спуска, быстрого градиентного спуска. Пример решения задачи сильно выпуклой оптимизации при аффинных ограничениях. Сходимость по норме градиента. Восстановление решение прямой задачи по последовательности точек, сгенерированной методом, решающим двойственную задачу (четвертый параграф пособия [[https://arxiv.org/ftp/arxiv/papers/1711/1711.00394.pdf 1]]). ||
| |
| − | |-
| |
| − | | 04.03.2020 || Шпирко|| Регуляризация прямой задачи. Сглаживание прямой задачи, через регуляризацию двойственной (замечание 4.1 пособия [[https://arxiv.org/ftp/arxiv/papers/1711/1711.00394.pdf 1]], см. также [[http://pwp.gatech.edu/guanghui-lan/wp-content/uploads/sites/330/2019/02/LectureOPTML.pdf 8]]). Примеры приложения двойственного сглаживания (задачи вида минимизации функции максимума). Метод штрафных функций (четвертый параграф пособия [[https://arxiv.org/ftp/arxiv/papers/1711/1711.00394.pdf 1]]). ||
| |
| − | |-
| |
| − | | 11.03.2020 || Шпирко|| Решение задач выпуклой оптимизации больших размеров с помощью субградиентных методов и метода условного градиента. Примеры: упражнение 1.6 пособия [[https://arxiv.org/ftp/arxiv/papers/1711/1711.00394.pdf 1]], Truss Topology Design. ||
| |
| − | |-
| |
| − | | 18.03.2020 || Шпирко|| Квазиньютоновские методы BFGS, L-BFGS. Методы второго порядка. Метод Ньютона. Методы внутренней точки (см. [7]) ||
| |
| − | |-
| |
| − | | 25.03.2020 || Шпирко|| Методы внутренней точки (продолжение) (см. [7]) ||
| |
| − | |-
| |
| − | | 01.04.2020 || [https://www.hse.ru/org/persons/320473622 Иванова А. С.]|| Каталист Монтейро-Свайтера [https://arxiv.org/abs/ arXiv:1911.11271]. Слайдинг Лана (упражнение 3.8 пособия [[https://arxiv.org/ftp/arxiv/papers/1711/1711.00394.pdf 1]]). Опимальные тензорные методы (замечание 3.3 и приложение пособия). ||
| |
| − | |-
| |
| − | | 08.04.2020 || [https://www.hse.ru/org/persons/161002023 Тюрин А. И.]|| Стохастический градиентный спуск. Понятие о минибатчинге. Адаптивные процедуры (приложение пособия [[https://arxiv.org/ftp/arxiv/papers/1711/1711.00394.pdf 1]] и [https://arxiv.org/abs/1911.08380 arXiv:1911.08380]). AdaGrad, Adam, метод Баха-Леви [https://arxiv.org/abs/1902.01637 arXiv:1902.01637] - их преимущества и недостатки [https://openreview.net/pdf?id=ryQu7f-RZ On the Convergence of Adam and beyond] ||
| |
| − | |-
| |
| − | | 15.04.2020 || [https://www.hse.ru/org/persons/320473622 Иванова А. С.]|| Примеры приложения каталиста к покомпонентным методам и методам рандомизации суммы. Более подробный рассказ про покомпонентные/безградиентные методы и методы редукции дисперсии (минимизации функций вида суммы) ||
| |
| − | |-
| |
| − | | 22.04.2020 || [https://www.hse.ru/org/persons/49503846 Гасников А. В.]|| Связь оптимизации и анализа данных, статистики https://www.cs.cornell.edu/~sridharan/thesis.pdf ||
| |
| − | |-
| |
| − | | 29.04.2020 || [https://www.hse.ru/org/persons/320473622 Иванова А. С.]|| Введение в распределенную оптимизацию. Централизованная оптимизация на примере задачи о распределении ресурсов [https://arxiv.org/abs/1806.09071 arXiv:1806.09071], [https://arxiv.org/abs/1909.13321 arXiv:1909.13321], [https://arxiv.org/abs/1911.07354 arXiv:1911.07354]. Децентрализованная оптимизация [https://arxiv.org/abs/1904.09015 arXiv:1904.09015], [https://arxiv.org/abs/1911.07363 arXiv:1911.07363]. ||
| |
| − | |-
| |
| − | |}
| |
| − |
| |
| − | == Семинары ==
| |
| − |
| |
| − |
| |
| − |
| |
| − | == Практические задания ==
| |
| − |
| |
| − |
| |
| − |
| |
| − | ==Теоретические домашние задания==
| |
| − |
| |
| − |
| |
| − | == Контрольная работа ==
| |
| − |
| |
| − |
| |
| − | == Экзамен ==
| |
| − |
| |
| − |
| |
| − | == Полезные материалы ==
| |
| − |
| |
| − | ===Книги===
| |
| − |
| |
| − | # [https://arxiv.org/ftp/arxiv/papers/1711/1711.00394.pdf Гасников А. В. Современные численные методы оптимизации. Метод универсального градиентного спуска. – М.: МФТИ, 2018.]
| |
| − | # [https://www.mccme.ru/dubna/2017/courses/gasnikov.html Гасников А. В. Презентации к избранным частям курса] (наиболее важными являются презентации 1-4)
| |
| − | # Поляк Б.Т. Введение в оптимизацию. Изд. 2-ое, испр. и доп. – М.: ЛЕНАНД, 2014.
| |
| − | # [http://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf Boyd S., Vandenberghe L. Convex optimization. – Cambridge University Press, 2004.]
| |
| − | # Bubeck S. Convex optimization: algorithms and complexity. – Foundations and Trends in Machine Learning, 2015. – V. 8, N 3–4. – P. 231–357.
| |
| − | # [https://www2.isye.gatech.edu/~nemirovs/Trans_ModConvOpt.pdf Nemirovski A. Advanced Nonlinear Programming. – Lectures, ISyE 7683 Spring 2019.]
| |
| − | # Nesterov Yu. Lectures on convex optimization. – Springer, 2018.
| |
| − | # [http://pwp.gatech.edu/guanghui-lan/wp-content/uploads/sites/330/2019/02/LectureOPTML.pdf Lan G. Lectures on optimization. Methods for Machine Learning, 2019.]
| |
