Магистратура
2020/2021
Выпуклый анализ и оптимизация
Статус:
Курс по выбору (Науки о данных)
Направление:
01.04.02. Прикладная математика и информатика
Кто читает:
Базовая кафедра Яндекс
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Преподаватели:
Дорн Юрий Владимирович
Прогр. обучения:
Науки о данных
Язык:
русский
Кредиты:
4
Контактные часы:
48
Программа дисциплины
Аннотация
Оптимизация является одной из основных рабочих лошадок, используемых в машинном обучении. Наш курс состоит из трех частей: Вводная часть о выпуклых множествах и выпуклых функциях, условиях оптимальности в задачах оптимизации, теории двойственности; Часть, посвященная алгоритмам для численного решения оптимизационных задач. В этой части мы попытаемся проиллюстрировать основные идеи, используемые при разработке методов оптимизации. В этой части мы будем не столько разбирать известные методы, сколько на их примере рассматривать основные концепты; Часть, посвященная задачам оптимизации с неопределенностью. Эта часть интересна сама по себе. Задачи оптимизации с неопределенностью встречаются повсеместно, при этом этой неопределенности может быть самый разный. В стандартных курсах по оптимизации обычно эти вопросы или не затрагиваются вовсе, или же затрагиваются лишь частично. Мы попытались в нашем курсе уделить задачам с неопределенностью больше внимания (конечно, в пределах временных рамок курса).
Планируемые результаты обучения
- Знать определение выпуклой и вогнутой функции
- Уметь решать задачу нахождения оптимума
- Знать необходимые условия оптимальности и двойственности
- Уметь применять теорема о слабой и сильной двойственности
- Владеть навыками практической реализации градиентного спуска
- Уметь анализ скорость сходимости градиентного спуска для различных функций
- Знать методы сглаживания негладкого функционала
- Уметь выбирать проксимальные функции.
- Знать внутренние и внешние штрафные функции
- Знать берьерный метод и уметь использовать его при решении практических задач
- Уметь реализовать ADMM и применять при решении практических задач
- Уметь вычислять скорость сходимости ADMM
- Знать методы зеркального спуска
- Знать метод Ньютона и BFGS.
- Знать концепция робастного решения
- Уметь построить робастную аппроксимацию
- Владеть методами решения для задачи стохастической оптимизации
- Знать концепцию и свойства Recourse Function
- Уметь реализовать стохастические градиентные спуск на языке программирования Python
- Владеть методом Approx и применять в решении практических задач оптимизации
- Знать концепцию многорукого бандита.
- Иметь представление о задаче онлайн-оптимизации
Содержание учебной дисциплины
- Выпуклые функции и множестваОпределение и основные свойства аффинных, конических и выпуклых множеств. Преобразования, сохраняющие выпуклость множеств. Сопряженные множества: определение и свойства.Определение, примеры и основные свойства выпуклых функций. Преобразования, сохраняющие выпуклость. Сопряженные функции и их свойства. Субградиенты и субдифференциалы.
- Условия оптимальности и двойственность"Условия оптимальности для задач безусловной оптимизации гладкой функции (FOOC). Условия оптимальности для негладких задач безусловной оптимизации. Условия оптимальности для задач с ограничениями. Условие оптимальности Каруша-Куна-Таккера. Двойственные задачи: построение и анализ. Двойственная задача для ЛП. Теорема о слабой и сильной двойственности. Коническая двойственность. "
- Введение в методы оптимизацииОбщая структура методов оптимизации. Оракулы. Градиентные спуски. Анализ скорости сходимости градиентного спуска.
- Сложность для классов выпуклых гладких и выпуклых негладких задачПолучение нижних оценок для методов градиентного класса на классе гладких выпуклых задач безусловной оптимизации. Оптимальные методы для задач выпуклой оптимизации. Введение в проксимальные алгоритмы: построение, анализ скорости сходимости и примеры.
- Техника сглаживанияСглаживание негладкого функционала вида максимума из линейных функций с помощью гладкого функционала. Проксимальные функции и их выбор.
- Штрафные функции. Барьерный метод. Метод модифицированной функции ЛагранжаВнутренние штрафные функции Внешние штрафные функции Барьерный метод. Применения метода функции Лагранжа в практических задачах.
- ADMMПостроение ADMM. Связь ADMM с ММФЛ. Примеры работы ADMM. Сведение задач к виду, допускающему использование ADMM. Скорость сходимости ADMM.
- Введение в методы зеркального спускаNewton method and quasi-Newton methods. BFGS. Метод Ньютона - построение и анализ. Квази-Ньютоновские методы. BFGS - построение и анализ.
- Введение в робастную оптимизацию"Концепция робастного решения Построение робастной аппроксимации линейного ограничения с неопределенностью Ограничения вероятностного типа и их робастные апроксимации. "
- Введение в стохастическую оптимизацию"Концепции решения для задачи стохастической оптимизации Введение мягких штрафов Recourse Function и ее свойства. "
- Рандомизированные алгоритмы оптимизации"Стохастические градиентные спуски и их свойства Рандомизация по батчам и параллелизация (методы типа Approx) "
- Введение в онлайн-оптимизацию"Постановка задачи онлайн-оптимизации Многорукие бандиты. The Multiplicative Weights Update Method: его свойства и применение. "
Промежуточная аттестация
- Промежуточная аттестация (2 модуль)0.3 * Домашняя работа + 0.3 * Домашняя работа + 0.4 * Экзамен
Список литературы
Рекомендуемая основная литература
- Arkadi Nemirovski. (2001). Lectures on modern convex optimization. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.5E080C05
- Ruud, A. (2019). Convex Optimization: Theory, Methods and Applications. Hauppauge, New York: Nova. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=2043454
Рекомендуемая дополнительная литература
- Gorbunov, E., Dvinskikh, D., & Gasnikov, A. (2019). Optimal Decentralized Distributed Algorithms for Stochastic Convex Optimization. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsarx&AN=edsarx.1911.07363
- Stephen Boyd, Lieven Vandenberghe, & Lieven V. (2015). Additional Exercises for Convex Optimization. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.E7445CE1