• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 2019/2020

Непрерывная оптимизация

Статус: Курс обязательный (Прикладная математика и информатика)
Направление: 01.03.02. Прикладная математика и информатика
Когда читается: 3-й курс, 3, 4 модуль
Формат изучения: без онлайн-курса
Язык: русский
Кредиты: 6

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

Аннотация

В курсе «Непрерывная оптимизация» изучаются основные математические концепции и алгоритмы в области непрерывной оптимизации. Методы оптимизации лежат в основе решения многих задач компьютерных наук. Например, в машинном обучении задачу оптимизации необходимо решать каждый раз при настройке какой-то модели алгоритмов по данным, причём от эффективности решения соответствующей задачи оптимизации зависит практическая применимость самого метода машинного обучения. Данный курс посвящен изучению классических и современных методов решения задач непрерывной оптимизации (в том числе невыпуклых), а также особенностям применения этих методов в задачах оптимизации, возникающих в машинном обучении. Основной акцент в изложении делается на практические аспекты реализации и использования методов. Целью курса является выработка у слушателей навыков по подбору подходящего метода для своей задачи, наиболее полно учитывающего её особенности.
Цель освоения дисциплины

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

  • Освоение классических и современных численных методов решения задач непрерывной оптимизации
  • Освоение основных математических результатов из теории непрерывной оптимизации
  • Выработка практических навыков реализации численных методов оптимизации
Содержание учебной дисциплины

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

  • Понятие о численных методах оптимизации
    Понятие о численных методах оптимизации. Метод градиентного спуска. Сложность задач оптимизации. Сильно выпуклые задачи, выпуклые (вырожденные) задачи, невыпуклые задачи. Гладкие, негладкие задачи. Регуляризация и рестарты. О возможности вычислять градиент и автоматическом дифференцировании. Приложение к задаче оптимального управления.
  • Невыпуклая оптимизация
    Невыпуклая оптимизация. Условие Поляка-Лоясиевича (ПЛ) и глобальная сходимость градиентного спуска. Пример: сведение решение системы нелинейных уравнений к задаче оптимизации с условием ПЛ. Сходимость градиентного спуска к локальному экстремуму. Принцип множителей Лагранжа и теорема о неявной функции. Выпуклая оптимизация. Принцип множителей Лагранжа и теорема об отделимости точки от выпуклого множества гиперплоскостью (без доказательства).
  • Унимодальные функции одной переменной
    Унимодальные функции одной переменной. Методы одномерной минимизации (метод дихотомии, метод золотого сечения, метод Фибоначчи). Задача о распределении ресурсов. Методы маломерной оптимизации: метод центров тяжести, метод эллипсоидов.
  • Слабая и сильная двойственность для задач выпуклой оптимизации
    Двойственная задача. Слабая и сильная двойственность для задач выпуклой оптимизации. Теорема о минмаксе (Фон Неймана, Сион-Какутани) (без доказательства). Седловые задачи. Коническая двойственность. Теоремы об альтернативах (Фаркаш) и их следствия (основная теорема финансовой математики об отсутствии арбитража; робастная оптимизация). Понятие о прямо-двойственных методах на примере решение задачи минимизации выпуклого сепарабельного функционала с аффинными ограничениями с помощью перехода к двойственной задаче и ее решения методом градиентного спуска.
  • Задачи оптимизации на множествах простой структуры
    Задачи оптимизации на множествах простой структуры. Дивергенция Брэгмана. Метод проекции (суб-)градиента, метод зеркального спуска. Метод условного градиента (Франк-Вульфа). Пример задачи минимизации квадратичной формы с разреженной положительно определенной матрицей на единичном симплексе.
  • Способы выбора шага в методах
    Способы выбора шага в методах. Наискорейший спуск. Правило Армихо и правило Голдстейна. Адаптивный способ выбора шага. Сопряженные направления. Метод сопряженных градиентов для минимизации квадратичных функций. Метод сопряженных градиентов для решения задач выпуклой оптимизации. Метод тяжелого шарика Поляка. Ускоренный градиентный метод (в разных вариантах: линейный каплинг, метод подобных треугольников). Новый ускоренный градиентный метод (на базе метода линейного каплинга) с одномерными минимизациями.
  • Концепция (неточной) модели функции
    Концепция (неточной) модели функции. Композитная оптимизация. Универсальный градиентный спуск и его ускоренный вариант. Проксимальный градиентный спуск. Ускоренный проксимальный метод (в варианте Монтейро-Свайтера). Каталист - общий способ ускорения различных неускоренных методов.
  • Метод Ньютона
    Метод Ньютона. Квазиньютоновские методы (LBFGS). Метод Ньютона с кубической регуляризацией. Тензорные методы. Ускоренные тензорные методы.
  • Стохастическая оптимизация
    Стохастическая оптимизация. Минибатчинг и распараллеливание. Рандомизированные методы на примере покомпонентных и безградиентных методов. Задача минимизации суммы функций.
  • Общая схема метода штрафных функций
    Общая схема метода штрафных функций. Метод модифицированной функции Лагранжа. Методы внутренней точки. Понятие самосогласованного барьера. Методы параметризации целевых функций. Методы отслеживания центральной траектории.
  • Распределенная оптимизация
    Распределенная оптимизация на примере решения задач выпуклой оптимизации функционалов вида суммы функций.
Элементы контроля

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

  • неблокирующий Самостоятельные работы
    СР
  • неблокирующий Домашние задания
    ДЗ
  • неблокирующий Экзамен
    Письменный экзамен (Э) на 90 минут.
  • неблокирующий Контрольная работа
    КР
  • неблокирующий Проект
    ПР
Промежуточная аттестация

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

  • Промежуточная аттестация (4 модуль)
    Формула для специализаций АДИС, АПР, РС, ТИ: Итог = MIN{Округление(0.25 * ДЗ + 0.3 * Э + 0.4 * ПР + 0.15 * СР), 10}. Формула для специализации МОП: Округление_вверх(0.7*<Оценка_за_семестр> + 0.3*<Оценка_за_экзамен>). <Оценка_за_семестр> = min(10, <Суммарная_оценка_за_задания>*10 / <Максимальная_суммарная_оценка_за_задания_без_бонусов>). Итоговая оценка за курс совпадает с общей оценкой при соблюдении следующих дополнительных условий: Итоговая оценка >=8, если сданы все задания, кроме одного теоретического задания (на оценку >=4), экзамен сдан на оценку >= 6; Итоговая оценка >=6, если сданы все задания, кроме трех (на оценку >=4), экзамен сдан на оценку >= 4; Итоговая оценка >=4, если сданы все задания, кроме пяти (на оценку >=4), экзамен сдан на оценку >= 4.
Список литературы

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

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

  • Nocedal, J., & Wright, S. J. (1999). Numerical Optimization. New York: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=104566
  • Optimization for Machine Learning Lecture 1: Introduction to Convexity. (2011). Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.9CAA7B97

Рекомендуемая дополнительная литература

  • Bubeck, S. (2014). Convex Optimization: Algorithms and Complexity. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.E3D5E1AB
  • Luethi, H.-J. (2005). Convex Optimization: Stephen Boyd and Lieven Vandenberghe. Journal of the American Statistical Association, 1097. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsrep&AN=edsrep.a.bes.jnlasa.v100y2005p1097.1097