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

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

Лектор: Кропотов Дмитрий Александрович. Лекции проходят по вторникам в ауд. 622 с 13:40 до 15:00.

Семинаристы:

Группа	Семинарист	Расписание	Инвайт для anytask
151 (МОП)	Родоманов Антон Олегович	вторник, 15:10 – 16:30, ауд. 503	91aHb6E
152 (МОП)	Дойков Никита Владимирович	вторник, 15:10 – 16:30, ауд. 618	tHxrPO6
155 (РС)	Шаповалов Никита Анатольевич	вторник, 15:10 – 16:30, ауд. 301	xtdRi1f
156 (ТИ)	Тюрин Александр Игоревич	вторник, 18:10 – 19:30, ауд. 306	j2OlXCE

Группа в Telegram для вопросов по курсу: https://t.me/joinchat/CzWHMFEeRHIDcNVdHfWTug.

Таблица с оценками по курсу: https://docs.google.com/spreadsheets/d/1i744zsMejvdS_xjtJSQIXccX9g0ywrklNRIURG23K0M/edit?usp=sharing.

Список вопросов к экзамену: https://yadi.sk/i/TN2h4SEm3TV2VT.

Внимание! Консультация к экзамену состоится в ближайшую субботу, 24 марта, в ауд. 509. Начало в 14-00.

Система выставления оценок по курсу

1. В рамках курса предполагается три практических задания, некоторое количество проверочных работ на семинарах и экзамен. Каждое задание и экзамен оцениваются по десятибалльной шкале.
2. В оценке за курс 60% составляет накопленная оценка за модуль и 40% - оценка за экзамен. Для получения финального результата (0–10) оценка округляется в большую сторону.
3. В накопленной оценке 50% составляют баллы за практические задания и 50% - баллы за проверочные работы на семинарах.

Практические задания

Практическое задание 1.

Практическое задание 2.

Практическое задание 3.

Правила сдачи заданий

В рамках курса предполагается сдача нескольких практических заданий. Практические задания сдаются в систему anytask. Эти задания могут быть присланы после срока сдачи, но с задержкой не более одной недели. При этом начисляется штраф из расчёта 0.2 балла в день.

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

Лекции

№ п/п	Дата	Занятие	Материалы
1	9 января 2018	Введение в курс. Классы функций для оптимизации. Скорости сходимости итерационных процессов.
2	16 января 2018	Точная одномерная оптимизация.
3	23 января 2018	Неточная одномерная оптимизация. Метод градиентного спуска.
4	30 января 2018	Матричные разложения и их использование для решения СЛАУ. Метод Ньютона для выпуклых и невыпуклых задач.
5	6 февраля 2018	Метод сопряжённых градиентов для решения СЛАУ.
6	13 февраля 2018	Неточный метод Ньютона. Разностные производные.
7	20 февраля 2018	Квазиньютоновские методы. Метод L-BFGS.
8	27 февраля 2018	Задачи условной оптимизации: условия ККТ.
9	6 марта 2018	Выпуклые задачи оптимизации. Двойственность. Метод барьеров.
10	13 марта 2018	Негладкая безусловная оптимизация. Субградиентный метод. Проксимальные методы.
11	20 марта 2018	Стохастическая оптимизация.

Семинары

№ п/п	Дата	Занятие	Материалы
1	9 января 2018	Скорости сходимости. Матричные вычисления.	Конспект Домашнее задание
2	16 января 2018	Матрично-векторное дифференцирование (часть 1)	Конспект Домашнее задание
3	23 января 2018	Матрично-векторное дифференцирование (часть 2). Градиентный спуск.	Презентация Домашнее задание
4	30 января 2018	Выпуклые множества	Конспект Домашнее задание
5	6 февраля 2018	Выпуклые функции	Конспект Домашнее задание
6	13 февраля 2018	Стандартные классы выпуклых задач. Эквивалентные преобразования.	Конспект Домашнее задание
7	20 февраля 2018	Квазиньютоновские методы	Конспект Домашнее задание
8	27 февраля 2018	Условия Каруша--Куна--Таккера.	Конспект Домашнее задание
9	6 марта 2018	Двойственность. Сопряженные функции.	Конспект Домашнее задание
10	13 марта 2018	Субдифференциалы	Конспект Домашнее задание
11	20 марта 2018	Вычисление проекций и проксимальных отображений

Литература

1. J. Nocedal, S. Wright. Numerical Optimization, Springer, 2006.
2. A. Ben-Tal, A. Nemirovski. Optimization III. Lecture Notes, 2013.
3. Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course, Springer, 2003.
4. Ю.Е. Нестеров. Методы выпуклой оптимизации, МЦНМО, 2010
5. S. Boyd, L. Vandenberghe. Convex Optimization, Cambridge University Press, 2004.
6. D. Bertsekas. Convex Analysis and Optimization, Athena Scientific, 2003.
7. Б.Т. Поляк. Введение в оптимизацию, Наука, 1983.
8. J. Duchi. Introductory Lectures on Stochastic Optimization, Graduate Summer School Lectures, 2016.
9. S. Sra et al.. Optimization for Machine Learning, MIT Press, 2011.