Выпуклый анализ и оптимизация

2021/2022

Учебный год

RUS

Обучение ведется на русском языке

4

Кредиты

Кто читает:

Базовая кафедра Яндекс (Департамент больших данных и информационного поиска)

Статус:

Курс по выбору

Когда читается:

1-й курс, 1, 2 модуль

Преподаватель

Дорн Юрий Владимирович

Программа дисциплины

Аннотация

Оптимизация является одной из основных рабочих лошадок, используемых в машинном обучении. Наш курс состоит из трех частей: Вводная часть о выпуклых множествах и выпуклых функциях, условиях оптимальности в задачах оптимизации, теории двойственности; Часть, посвященная алгоритмам для численного решения оптимизационных задач. В этой части мы попытаемся проиллюстрировать основные идеи, используемые при разработке методов оптимизации. В этой части мы будем не столько разбирать известные методы, сколько на их примере рассматривать основные концепты; Часть, посвященная задачам оптимизации с неопределенностью. Эта часть интересна сама по себе. Задачи оптимизации с неопределенностью встречаются повсеместно, при этом этой неопределенности может быть самый разный. В стандартных курсах по оптимизации обычно эти вопросы или не затрагиваются вовсе, или же затрагиваются лишь частично. Мы попытались в нашем курсе уделить задачам с неопределенностью больше внимания (конечно, в пределах временных рамок курса).

Цель освоения дисциплины

• Получить представление о задачах и методах выпуклой оптимизации

Планируемые результаты обучения

• Владеть методами решения для задачи стохастической оптимизации
• Владеть методом Approx и применять в решении практических задач оптимизации
• Владеть навыками практической реализации градиентного спуска
• Знать берьерный метод и уметь использовать его при решении практических задач
• Знать внутренние и внешние штрафные функции
• Знать концепцию и свойства Recourse Function
• Знать концепцию многорукого бандита.
• Знать концепция робастного решения
• Знать метод Ньютона и BFGS.
• Знать методы зеркального спуска
• Знать методы сглаживания негладкого функционала
• Знать необходимые условия оптимальности и двойственности
• Знать определение выпуклой и вогнутой функции
• Иметь представление о задаче онлайн-оптимизации
• Уметь анализ скорость сходимости градиентного спуска для различных функций
• Уметь выбирать проксимальные функции.
• Уметь вычислять скорость сходимости ADMM
• Уметь построить робастную аппроксимацию
• Уметь применять теорема о слабой и сильной двойственности
• Уметь реализовать ADMM и применять при решении практических задач
• Уметь реализовать стохастические градиентные спуск на языке программирования Python
• Уметь решать задачу нахождения оптимума

Содержание учебной дисциплины

• Выпуклые функции и множества
• Условия оптимальности и двойственность
• Введение в методы оптимизации
• Сложность для классов выпуклых гладких и выпуклых негладких задач
• Техника сглаживания
• Штрафные функции. Барьерный метод. Метод модифицированной функции Лагранжа
• ADMM
• Введение в методы зеркального спуска
• Введение в робастную оптимизацию
• Введение в стохастическую оптимизацию
• Рандомизированные алгоритмы оптимизации
• Введение в онлайн-оптимизацию

Элементы контроля

• Домашняя работа
• Домашняя работа
• Экзамен

Промежуточная аттестация

• 2021/2022 учебный год 2 модуль
  0.3 * Домашняя работа + 0.4 * Экзамен + 0.3 * Домашняя работа

Список литературы

Рекомендуемая основная литература

• 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