Просмотр кода страницы Непрерывная оптимизация (МОП)/2020

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

'''Преподаватели''': Кропотов Дмитрий Александрович, Гадецкий Артём, Шаповалов Никита, Таскынов Ануар, Гринберг Вадим, Бобров Евгений.

{| class="wikitable"
 ! Группа !! Расписание !! Ссылка на zoom !! Инвайт для anytask
 |-
 | 171 || понедельник, лекция в 18:10, семинар в 19:40 || align="center"|https://zoom.us/j/531942418 || align="center"|gQHw1vz
 |-
 | 172 || понедельник, лекция в 18:10, семинар в 19:40 || align="center"|https://zoom.us/j/531942418 || align="center"|0iPflMg
 |}

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

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

Записи занятий в zoom: [https://www.youtube.com/playlist?list=PLEwK9wdS5g0pRd8haE1NGph34yBUUHvUV ссылка]

== Экзамен ==

Процедура экзамена, а также список билетов/вопросов находится [https://drive.google.com/file/d/1zsRsu0-czj7MYGOGCI-oNEkQAEhy0Huz/view?usp=sharing здесь].

Примеры заданий что могут быть выданы на экзамене: [https://drive.google.com/file/d/1QnOEtC0LgqV5xrAYRxCsSXyPfp-IqF5p/view?usp=sharing link].

Распределение студентов по времени сдачи экзамена: [https://docs.google.com/spreadsheets/d/1U_uxwr1s_aCWFBkulwKKz8sSkrhFVrsoqChd8i8clZ8/edit?usp=sharing ссылка].

Консультация к экзамену, а также проверка технической готовности состоится 25 июня в 14-00. [https://youtu.be/s95mGMfxXQY видео]

== Система выставления оценок по курсу ==
В рамках курса предполагается некоторое количество теоретических и практических домашних заданий, а также устный экзамен в конце курса. Каждое задание и экзамен оцениваются исходя из 10-ти баллов. За задания можно получить дополнительные баллы за выполнение бонусных пунктов.
Общая оценка за курс вычисляется по правилу Округление_вверх(0.7*<Оценка_за_семестр> + 0.3*<Оценка_за_экзамен>). <Оценка_за_семестр> = min(10, <Суммарная_оценка_за_задания>*10 / <Максимальная_суммарная_оценка_за_задания_без_бонусов>). Итоговая оценка за курс совпадает с общей оценкой при соблюдении следующих дополнительных условий: 
{| class="wikitable"
 ! Итоговая оценка !! Условия 
 |-
 |align="center"|>=8 || Сданы все задания, кроме одного теоретического задания (на оценку >=4), экзамен сдан на оценку >= 6
 |-
 |align="center"|>=6 || Сданы все задания, кроме двух (на оценку >=4), экзамен сдан на оценку >= 4
 |-
 |align="center"|>=4 || Сданы все задания, кроме трех (на оценку >=4), экзамен сдан на оценку >= 4
 |-
 |}

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

Теоретические задания сдаются в anytask в виде сканов или набранных в TeX pdf-файлов. '''ВАЖНО!''' Присылаемые сканы должны быть высокого качества, присылаться одним файлом, в котором все листы идут в правильном порядке. В случае плохого качества сканов или же сдачи в формате, отличном от pdf, проверяющий имеет право поставить за работу 0, не проверяя.

== Теоретические ДЗ == 

Задание 1. [https://drive.google.com/open?id=1wmwhCqFBjIfeMSS6VJJYHfDMBC_NGNzh Выпуклые множества и функции]. Срок сдачи - 14 марта (суббота), 23:59.

Задание 2. [https://drive.google.com/open?id=1VAJA_no969xvp5x7CkoZ9JXmg6u9W-jD Условия Каруша--Куна--Таккера. Двойственность.] Срок сдачи - 20 мая (среда), 23.59.

Дополнительное задание. [https://drive.google.com/file/d/1je4tv40idB3FqjcIU6QlwaXV7GGki6KR/view?usp=sharing Сопряжённые функции, субдифференциалы, проксимальные операторы]. Срок сдачи (мягкий=жёсткий) 23 июня (вторник), 23:59

== Практические ДЗ ==

Задание 1. [https://github.com/JeanPaulShapo/hse20-opt-course/blob/d16d202bfa7b97ea82bcc44fe7d08464f2ad23ed/task1/practice1.pdf Методы градиентного спуска и Ньютона]. Срок сдачи - 3 марта (вторник), 23:59.

Задание 2. [https://github.com/JeanPaulShapo/hse20-opt-course/blob/016c3ee13b87c0178323272148e0cb2d4812e4b0/task2/practice2.pdf Продвинутые методы безусловной оптимизации]. Срок сдачи - 27 марта (пятница), 23:59.

Задание 3. [https://github.com/JeanPaulShapo/hse20-opt-course/blob/c50d4e4bfdd8b53648b26ef49956ee31b0bf718a/task3/practice3.pdf Метод барьеров]. Срок сдачи - 23 мая (суббота), 23:59.

Задание 4. [https://github.com/JeanPaulShapo/hse20-opt-course/blob/6d6ecdc59641113455d58068c56b49d3f4779371/task4/practice4.pdf Композитная оптимизация]. Срок сдачи - 9 июня (вторник) 23:59.

== Лекции ==
{| class = "wikitable"  
|+
! № п/п
! Дата
! Занятие
! Материалы
|-
| align="center"|1
| 15&nbsp;января&nbsp;2020
| Введение в курс. Скорости сходимости итерационных процессов. || [https://drive.google.com/file/d/1MXENV3Ryy8SgK3_q_lKB5gBG39qcl8_M/view?usp=sharing Конспект]
|-
| align="center"|2
| 20&nbsp;января&nbsp;2020
| Одномерная оптимизация. || [http://www.machinelearning.ru/wiki/images/4/4d/MOMO16_min1d.pdf Конспект]
|-
| align="center"|3
| 27&nbsp;января&nbsp;2020
| Метод градиентного спуска. || 
|-
| align="center"|4
| 3&nbsp;февраля&nbsp;2020
| Матричные разложения. Метод Ньютона. || 
|-
| align="center"|5
| 10&nbsp;февраля&nbsp;2020
| Метод сопряжённых градиентов для решения СЛАУ. || 
|-
| align="center"|6
| 17&nbsp;февраля&nbsp;2020
| Безгессианный метод Ньютона. Разностное дифференцирование. || 
|-
| align="center"|7
| 2&nbsp;марта&nbsp;2020
| Квазиньютоновские методы оптимизации || 
|-
| align="center"|8
| 16&nbsp;марта&nbsp;2020
| Условия Каруша-Куна-Таккера для условной оптимизации || 
|-
| align="center"|9
| 6&nbsp;апреля&nbsp;2020
| Двойственные задачи, симплекс-метод для линейного программирования || [https://youtu.be/J3ZFXVX0st4 видео]
|-
| align="center"|10
| 13&nbsp;апреля&nbsp;2020
| Метод Ньютона и логарифмических барьеров для выпуклых задач условной оптимизации || [https://youtu.be/1NyS4b61nQo видео]
|-
| align="center"|11
| 20&nbsp;апреля&nbsp;2020
| Негладкая оптимизация. Субградиентный метод. || [https://youtu.be/uxGcpOhLvpM видео]
|-
| align="center"|12
| 27&nbsp;апреля&nbsp;2020
| Проксимальный градиентный метод || [https://youtu.be/O6X46icwVUI видео]
|-
| align="center"|13
| 18&nbsp;мая&nbsp;2020
| Стохастическая оптимизация || [https://youtu.be/dTa55W-kgjc видео 1] [https://youtu.be/RmYcby79V3s видео 2]
|-
| align="center"|14
| 25&nbsp;мая&nbsp;2020
| Риманова оптимизация || [https://youtu.be/nT4FruWbjRI видео]
|-
| align="center"|15
| 01&nbsp;июня&nbsp;2020
| Решение задач оптимизации с помощью нейронных сетей || [https://youtu.be/x1BVFRZrs58 видео]<br> [https://arxiv.org/abs/1606.04474 Статья 1]<br> [https://arxiv.org/abs/1803.08475 Статья 2]
|-
|}

== Семинары ==
{| class = "wikitable"  
|+
! № п/п
! Дата
! Занятие
! Материалы
|-
| align="center"|1
| 15&nbsp;января&nbsp;2020
| Матрично-векторное дифференцирование. || [https://drive.google.com/file/d/1bNWF262guJHTphptCTYARAsUKRPC9QmS/view?usp=sharing Конспект]
|-
| align="center"|2
| 20&nbsp;января&nbsp;2020
| Неточная одномерная оптимизация. Классы функций для оптимизации. || 
|-
| align="center"|3
| 27&nbsp;января&nbsp;2020
| Метод градиентного спуска. || [https://drive.google.com/file/d/12kSbD8LsQ00BgpNcvCa8eGzcrB4MdaC-/view?usp=sharing ipynb]
|-
| align="center"|4
| 3&nbsp;февраля&nbsp;2020
| Выпуклые множества. || [https://drive.google.com/file/d/1IvXdLMTsV3EvwAAr9r4En4PKW5kR3rzi/view?usp=sharing Конспект]
|-
| align="center"|5
| 10&nbsp;февраля&nbsp;2020
| Нелинейный метод сопряжённых градиентов. || [https://drive.google.com/file/d/1G3yQx8VzUgylQZgPiuNWtYML7l0cRow_/view?usp=sharing Презентация]
|-
| align="center"|6
| 17&nbsp;февраля&nbsp;2020
| Выпуклые функции. || [https://drive.google.com/file/d/1m0IIMRwO-sIe-nhmys0B47ZjLHfIxZ98/view?usp=sharing Конспект]
|-
| align="center"|7
| 2&nbsp;марта&nbsp;2020
| Матричные преобразования в квазиньютоновских методах || [https://drive.google.com/file/d/1zlqaDmb84kfZ67BmiMinOKfYCeq68VKO/view?usp=sharing Конспект]
|-
| align="center"|8
| 16&nbsp;марта&nbsp;2020
| Задачи условной оптимизации || [https://yadi.sk/d/Op-nmGrl02lLnQ Конспекты] 
|-
| align="center"|9
| 6&nbsp;апреля&nbsp;2020
| Двойственные задачи, эквивалентные преобразования задач || [https://youtu.be/lRaWpJ8bTok видео] [https://drive.google.com/file/d/1GXgex6RrwWv_wGBh4oYLpUcWD5-Yc3UM/view?usp=sharing Конспект]
|-
| align="center"|10
| 13&nbsp;апреля&nbsp;2020
| Преобразование задач к стандартному виду || [https://youtu.be/F0eOsHLqDAU видео] [https://drive.google.com/file/d/1GXgex6RrwWv_wGBh4oYLpUcWD5-Yc3UM/view?usp=sharing Конспект]
|-
| align="center"|11
| 20&nbsp;апреля&nbsp;2020
| Субдифференциальное исчисление || [https://youtu.be/vl2qJw5E95U видео] [https://drive.google.com/file/d/175GWh8qsMg6rVO_xkjDvWbmRG_ALzIbm/view?usp=sharing Конспект]
|-
| align="center"|12
| 27&nbsp;апреля&nbsp;2020
| Проекции и проксимальные операторы || [https://youtu.be/LDUj7gq8Ty0 видео] [https://drive.google.com/file/d/1U7HbVIoK4KlrZSlioERfJ1g8rvAGSxhS/view?usp=sharing Заметки с семинара]
|-
| align="center"|13
| 18&nbsp;мая&nbsp;2020
| Сопряженные функции и нормы || [https://youtu.be/LxsJxOt6xYk видео] [http://www.machinelearning.ru/wiki/images/c/cb/MOMO20_Conjugate.pdf Конспект]
|-
| align="center"|14
| 1&nbsp;июня&nbsp;2020
| Решение задач дискретной оптимизации непрерывными методами || [https://youtu.be/lCCdoEla_7s видео] <br>[https://drive.google.com/file/d/1iEXeHGZ-3gdCT7hcHreOGlBAc1tTZgE8/view?usp=sharing Презентация]
|-
|}

== Дополнительный материал ==
* [https://www.dropbox.com/s/hxympqr7t4yuqqi/extra_1.pdf?dl=0 Конспект] по матрично-векторным скалярным произведениям и нормам.

== Литература ==
# J. Nocedal, S. Wright. [http://www.apmath.spbu.ru/cnsa/pdf/monograf/Numerical_Optimization2006.pdf Numerical Optimization], Springer, 2006.
# A. Ben-Tal, A. Nemirovski. [http://www2.isye.gatech.edu/~nemirovs/OPTIII_LectureNotes2015.pdf Optimization III. Lecture Notes], 2013.
# Y. Nesterov. [http://libgen.io/book/index.php?md5=049F85DF4693D7C3DC27DDDD0720A096 Introductory Lectures on Convex Optimization: A Basic Course], Springer, 2003.
# Ю.Е. Нестеров. [https://mipt.ru/dcam/upload/abb/nesterovfinal-arpgzk47dcy.pdf Методы выпуклой оптимизации], МЦНМО, 2010
# S. Boyd, L. Vandenberghe. [http://www.stanford.edu/~boyd/cvxbook/ Convex Optimization], Cambridge University Press, 2004.
# D. Bertsekas. [http://libgen.io/book/index.php?md5=D0DDDF4CF756D16AE5AA77C87ECDEDDA Convex Analysis and Optimization], Athena Scientific, 2003.
# Б.Т. Поляк. [http://premolab.ru/sites/default/files/polyak-optimizationintro.djvu Введение в оптимизацию], Наука, 1983.
# J. Duchi. [https://stanford.edu/~jduchi/PCMIConvex/Duchi16.pdf Introductory Lectures on Stochastic Optimization], Graduate Summer School Lectures, 2016.
# S. Sra et al.. [http://libgen.io/book/index.php?md5=9799B67D2A9C45DCAC9D323252054DAF Optimization for Machine Learning], MIT Press, 2011.
# Y. Nesterov. [https://www.dropbox.com/s/93eq4g8nukveb11/Nesterov.2018.Lectures.on.Convex.Optimization.pdf?dl=0 Lectures on convex optimization], Springer, 2018.