• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Магистратура 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