Методы оптимизации

Материалы семинаров по курсу методов оптимизации для 3 курса ФУПМ МФТИ.

Каждый семинар состоит из краткого обзора необходимой теории, примеров решения типовых задач и недельного домашнего задания, которое необходимо выполнить в LaTeX или Jupyter Notebook и прислать к указанному в задании сроку.

Самый минимум к экзамену и сдаче заданий по материалам осеннего семестра

Самый минимум к экзамену и сдаче заданий по материалам весеннего семестра

Ссылки на материалы семинаров

Осенний семестр

1. Введение

2. Выпуклые множества

3. Проекция точки на множество, отделимость, опорная гиперплоскость

4. Сопряжённые множества. Лемма Фаркаша

5. Векторное дифференцирование

6. Выпуклые функции

7. Субдифференциал

8. Конус возможных направлений, касательный конус, острый экстремум

9. Сопряжённые функции

10. Условия оптимальности

11. Двойственная задача

Весенний семестр

1. Численные методы оптимизации: введение, скорости сходимости, классификация методов, модель чёрного ящика, одномерная минимизация

2. Задача безусловной минимизации

   • Градиентный спуск
   • Метод Ньютона. Квазиньютоновские методы
   • Метод сопряжённых градиентов

3. Линейное программирование

   • Симплекс-метод
   • Прямой метод внутренней точки

4. Задача условной минимизации

   • Метод проекции градиента и условного градиента
   • Методы внутренней точки
   • Метод модифицированой функции Лагранжа и внешних штрафов

5. Другие темы

   • Задача наименьших квадратов
   • Последовательное квадратичное программирование
   • Оптимальные методы и нижние оценки (теория)
   • Зеркальный спуск и ускорения Нестерова
   • Стохастические методы: Adagrad, SAG, etc
   • Методы для задач с разреженностью
   • Проксимальные методы
   • Оптимизация на Римановых многообразиях
   • Оптимизация субмодулярных функций
   • ...

Список дополнительных материалов

1. Stephen Boyd, Lieven Vandenberghe. Convex Optimization

2. Курс по выпуклой оптимизации в Stanford'e

3. Курс по оптимизации и выпуклому анализу в MIT

4. Ю.Е. Нестеров. Методы выпуклой оптимизации

5. Б.Т. Поляк. Введение в оптимизацию

6. Лекции А. Юдицкого в Grenoble UJF

7. Matrix Cookbook

8. Видео лекций S. Boyd'a по курсу Convex Optimization в Stanford'е

9. Миникурс по выпуклой оптимизации от S. Boyd'a

Список ссылок на материалы по оптимизации

1. Convex Optimization: Algorithms and Complexity by S. Bubeck

2. Blog by S. Bubeck

3. Numerical Optimization by J. Nocedal & S. J. Wright

4. Lectures on Modern Convex Optimization by A. Nemirovski

5. Review of Stochactic Optimization Algorithms

6. Semidefinite Optimization by M. Laurent & F. Vallentin