Непрерывная оптимизация/2019 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Правила сдачи заданий)
 
(не показаны 32 промежуточные версии 2 участников)
Строка 5: Строка 5:
  
 
'''Семинаристы и ассистенты''':
 
'''Семинаристы и ассистенты''':
Гадецкий Артём, Гринберг Вадим, Шаповалов Никита, Таскынов Ануар.
+
Родоманов Антон, Гадецкий Артём, Гринберг Вадим, Шаповалов Никита, Таскынов Ануар.
  
 
{| class="wikitable"
 
{| class="wikitable"
Строка 18: Строка 18:
  
 
Убедительная просьба не флудить, не спамить и просто не безобразничать в чате.
 
Убедительная просьба не флудить, не спамить и просто не безобразничать в чате.
 +
 +
Таблица с оценками по курсу: [https://docs.google.com/spreadsheets/d/1fA_EKOBGMzDzdSkfumA0vvw0sz7q8TuxD96XLjvOCO0/edit?usp=sharing Link]
 +
 +
== Экзамен ==
 +
Экзамен состоится 26 марта в ауд. 402, начало в 10-30. На написание экзамена отводится два часа. При написании экзамена никакими материалами пользоваться нельзя.
 +
 +
Пробный вариант письменного экзамена: [https://www.dropbox.com/s/j9q98uodu0wnxs8/example_exam.pdf?dl=0 Link]
  
 
== Система выставления оценок по курсу ==
 
== Система выставления оценок по курсу ==
Строка 32: Строка 39:
 
В каждом теоретическом задании могут быть предложены несколько необязательных задач, позволяющих получить бонусные баллы. Бонусные баллы могут быть использованы студентом для повышения своих оценок за выбранные теоретические задания. При этом оценка за задание не может превысить максимум в 10 баллов.
 
В каждом теоретическом задании могут быть предложены несколько необязательных задач, позволяющих получить бонусные баллы. Бонусные баллы могут быть использованы студентом для повышения своих оценок за выбранные теоретические задания. При этом оценка за задание не может превысить максимум в 10 баллов.
  
== Лекции (план) ==
+
== Лекции ==
 
{| class = "wikitable"   
 
{| class = "wikitable"   
 
|+
 
|+
Строка 42: Строка 49:
 
| align="center"|1
 
| align="center"|1
 
| 15 января 2019
 
| 15 января 2019
| Введение в курс. Классы функций для оптимизации. Скорости сходимости итерационных процессов. ||  
+
| Введение в курс. Классы функций для оптимизации. Скорости сходимости итерационных процессов. || [10, рз. 1.2, 2.1], [1, с. 617-620]
 
|-
 
|-
 
| align="center"|2
 
| align="center"|2
 
| 22 января 2019
 
| 22 января 2019
| Неточная одномерная оптимизация. Метод градиентного спуска. ||  
+
| Неточная одномерная оптимизация. Метод градиентного спуска. || [10, рз. 2.1.5], [1, рз. 2.2, 3.2. 3.3]
 
|-
 
|-
 
| align="center"|3
 
| align="center"|3
 
| 29 января 2019
 
| 29 января 2019
| Матричные разложения и их использование для решения СЛАУ. Метод Ньютона для выпуклых и невыпуклых задач. ||  
+
| Матричные разложения и их использование для решения СЛАУ. Метод Ньютона для выпуклых и невыпуклых задач. || [1, рз. 2.2, 3.3, 3.4]
 
|-
 
|-
 
| align="center"|4
 
| align="center"|4
 
| 5 февраля 2019
 
| 5 февраля 2019
| Метод сопряжённых градиентов для решения СЛАУ. ||  
+
| Метод сопряжённых градиентов для решения СЛАУ. || [1, рз. 5.1]
 
|-
 
|-
 
| align="center"|5
 
| align="center"|5
 
| 12 февраля 2019
 
| 12 февраля 2019
| Квазиньютоновские методы. Метод L-BFGS. ||  
+
| Квазиньютоновские методы. Метод L-BFGS. || [1, рз. 6.1, 7.2]
 
|-
 
|-
 
| align="center"|6
 
| align="center"|6
 
| 19 февраля 2019
 
| 19 февраля 2019
| Задачи условной оптимизации: условия ККТ. ||  
+
| Задачи условной оптимизации: условия ККТ. || [1, глава 12]
 
|-
 
|-
 
| align="center"|7
 
| align="center"|7
 
| 26 февраля 2019
 
| 26 февраля 2019
| Метод Ньютона и метод барьеров для выпуклых задач условной оптимизации. ||  
+
| Метод Ньютона и метод барьеров для выпуклых задач условной оптимизации. || [5, глава 10]
 
|-
 
|-
 
| align="center"|8
 
| align="center"|8
Строка 78: Строка 85:
 
| align="center"|10
 
| align="center"|10
 
| 19 марта 2019
 
| 19 марта 2019
| Риманова оптимизация. ||  
+
| Ускоренный проксимальный градиентный метод. ||  
 
|-
 
|-
 
|}
 
|}
  
== Семинары (план) ==
+
== Семинары ==
 
{| class = "wikitable"   
 
{| class = "wikitable"   
 
|+
 
|+
Строка 92: Строка 99:
 
| align="center"|1
 
| align="center"|1
 
| 15 января 2019
 
| 15 января 2019
| Матрично-векторное дифференцирование (часть 1). ||  
+
| Матрично-векторное дифференцирование (часть 1). ||[https://www.dropbox.com/s/pjvwfenyvgqw6mq/seminar1.pdf?dl=0 Конспект]
 
|-
 
|-
 
| align="center"|2
 
| align="center"|2
 
| 22 января 2019
 
| 22 января 2019
| Матрично-векторное дифференцирование (часть 2). Скорости сходимости. Условия оптимальности. ||  
+
| Матрично-векторное дифференцирование (часть 2). Скорости сходимости. Условия оптимальности. ||[https://www.dropbox.com/s/lvpcp2xhc7hqbc5/seminar2.pdf?dl=0 Конспект]
 
|-
 
|-
 
| align="center"|3
 
| align="center"|3
 
| 29 января 2019
 
| 29 января 2019
| Разностное дифференцирование. Методы градиентного спуска и Ньютона на практике. ||  
+
| Разностное дифференцирование. Методы градиентного спуска и Ньютона на практике. || [https://www.dropbox.com/s/jjmqy3hb7e7og33/sem3.ipynb?dl=0 Ipynb]
 
|-
 
|-
 
| align="center"|4
 
| align="center"|4
 
| 5 февраля 2019
 
| 5 февраля 2019
| Выпуклые множества и функции ||  
+
| Выпуклые множества и функции || [https://www.dropbox.com/s/998vdipizr0rpwi/seminar4.pdf?dl=0 Конспект]
 
|-
 
|-
 
| align="center"|5
 
| align="center"|5
 
| 12 февраля 2019
 
| 12 февраля 2019
| Нелинейный метод сопряжённых градиентов. Предобуславливание. ||  
+
| Нелинейный метод сопряжённых градиентов. Предобуславливание. || [https://www.dropbox.com/s/ty5sb3dybobss0h/sem5.zip?dl=0 Материалы] [https://www.dropbox.com/s/shsyr4w8gvi07yd/seminar5.pdf?dl=0 Презентация]
 
|-
 
|-
 
| align="center"|6
 
| align="center"|6
 
| 19 февраля 2019
 
| 19 февраля 2019
| Условия ККТ. Эквивалентные преобразования задач. ||  
+
| Условия ККТ. Эквивалентные преобразования задач. || [https://www.dropbox.com/s/8ib9c3pl3u68zol/seminar6.pdf?dl=0 Конспект]
 
|-
 
|-
 
| align="center"|7
 
| align="center"|7
 
| 26 февраля 2019
 
| 26 февраля 2019
| Двойственность. Сопряжённые функции / нормы. ||  
+
| Двойственность. Сопряжённые функции / нормы. || [https://www.dropbox.com/s/ho6blomtbsrj52q/seminar7.pdf?dl=0 Конспект]
 
|-
 
|-
 
| align="center"|8
 
| align="center"|8
 
| 5 марта 2019
 
| 5 марта 2019
| Субдифференциальное исчисление. ||  
+
| Субдифференциальное исчисление. || [https://www.dropbox.com/s/x7e2xzlctzzcbgv/seminar8.pdf?dl=0 Конспект]
 
|-
 
|-
 
| align="center"|9
 
| align="center"|9
 
| 12 марта 2019
 
| 12 марта 2019
 
| Проксимальные операторы. ||  
 
| Проксимальные операторы. ||  
|-
 
| align="center"|10
 
| 19 марта 2019
 
| Ускоренный проксимальный градиентный метод ||
 
 
|-
 
|-
 
|}
 
|}
 +
 +
== Теоретические ДЗ ==
 +
* [https://www.dropbox.com/s/w2whrha8nwi804s/homework1.pdf?dl=0 Теория №1], дэдлайн — 29 января (23:59).
 +
* [https://www.dropbox.com/s/m1qv14ox3jbj46m/homework2.pdf?dl=0 Теория №2], дэдлайн — 19 февраля (23:59).
 +
* [https://www.dropbox.com/s/8hpqlaziys21eqn/homework3.pdf?dl=0 Теория №3], дэдлайн — 9 марта (23:59).
 +
* [https://www.dropbox.com/s/1qneo8eedr4qk77/homework4.pdf?dl=0 Теория №4], дэдлайн — 21 марта (23:59).
 +
 +
== Практические ДЗ ==
 +
* [https://www.dropbox.com/s/tizsurwk8c5h537/practice1.pdf?dl=0 Практика №1], дэдлайны — мягкий: 12 февраля (23:59), жёсткий: 20 февраля (23:59).
 +
* [https://www.dropbox.com/s/jgybp5tux3rhljs/practice2.pdf?dl=0 Практика №2], дэдлайны — мягкий: 2 марта (23:59), жёсткий: 10 марта (23:59).
 +
* [https://www.dropbox.com/s/jna58nrkrr87vop/practice3.pdf?dl=0 Практика №3], дэдлайны — мягкий: 14 марта (23:59), жёсткий: 22 марта (23:59).
 +
 +
== Дополнительный материал ==
 +
* [https://www.dropbox.com/s/hxympqr7t4yuqqi/extra_1.pdf?dl=0 Конспект] по матрично-векторным скалярным произведениям и нормам.
  
 
== Литература ==
 
== Литература ==
# J. Nocedal, S. Wright. [http://libgen.io/book/index.php?md5=7016B74CFE6DC64C75864322EE4AA081 Numerical Optimization], Springer, 2006.
+
# 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.
 
# 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.
 
# Y. Nesterov. [http://libgen.io/book/index.php?md5=049F85DF4693D7C3DC27DDDD0720A096 Introductory Lectures on Convex Optimization: A Basic Course], Springer, 2003.
Строка 142: Строка 159:
 
# J. Duchi. [https://stanford.edu/~jduchi/PCMIConvex/Duchi16.pdf Introductory Lectures on Stochastic Optimization], Graduate Summer School Lectures, 2016.
 
# 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.
 
# 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.

Текущая версия на 16:59, 21 марта 2019

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

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

Семинаристы и ассистенты: Родоманов Антон, Гадецкий Артём, Гринберг Вадим, Шаповалов Никита, Таскынов Ануар.

Группа Расписание Инвайт для anytask
161 вторник, 15:10 – 16:30, ауд. 503 ohYkZaV
162 вторник, 15:10 – 16:30, ауд. 505 5VhbMSK

Группа в Telegram для вопросов по курсу: Link

Убедительная просьба не флудить, не спамить и просто не безобразничать в чате.

Таблица с оценками по курсу: Link

Экзамен

Экзамен состоится 26 марта в ауд. 402, начало в 10-30. На написание экзамена отводится два часа. При написании экзамена никакими материалами пользоваться нельзя.

Пробный вариант письменного экзамена: Link

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

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

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

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

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

В каждом теоретическом задании могут быть предложены несколько необязательных задач, позволяющих получить бонусные баллы. Бонусные баллы могут быть использованы студентом для повышения своих оценок за выбранные теоретические задания. При этом оценка за задание не может превысить максимум в 10 баллов.

Лекции

№ п/п Дата Занятие Материалы
1 15 января 2019 Введение в курс. Классы функций для оптимизации. Скорости сходимости итерационных процессов. [10, рз. 1.2, 2.1], [1, с. 617-620]
2 22 января 2019 Неточная одномерная оптимизация. Метод градиентного спуска. [10, рз. 2.1.5], [1, рз. 2.2, 3.2. 3.3]
3 29 января 2019 Матричные разложения и их использование для решения СЛАУ. Метод Ньютона для выпуклых и невыпуклых задач. [1, рз. 2.2, 3.3, 3.4]
4 5 февраля 2019 Метод сопряжённых градиентов для решения СЛАУ. [1, рз. 5.1]
5 12 февраля 2019 Квазиньютоновские методы. Метод L-BFGS. [1, рз. 6.1, 7.2]
6 19 февраля 2019 Задачи условной оптимизации: условия ККТ. [1, глава 12]
7 26 февраля 2019 Метод Ньютона и метод барьеров для выпуклых задач условной оптимизации. [5, глава 10]
8 5 марта 2019 Негладкая безусловная оптимизация. Субградиентный метод. Проксимальные методы.
9 12 марта 2019 Стохастическая оптимизация.
10 19 марта 2019 Ускоренный проксимальный градиентный метод.

Семинары

№ п/п Дата Занятие Материалы
1 15 января 2019 Матрично-векторное дифференцирование (часть 1). Конспект
2 22 января 2019 Матрично-векторное дифференцирование (часть 2). Скорости сходимости. Условия оптимальности. Конспект
3 29 января 2019 Разностное дифференцирование. Методы градиентного спуска и Ньютона на практике. Ipynb
4 5 февраля 2019 Выпуклые множества и функции Конспект
5 12 февраля 2019 Нелинейный метод сопряжённых градиентов. Предобуславливание. Материалы Презентация
6 19 февраля 2019 Условия ККТ. Эквивалентные преобразования задач. Конспект
7 26 февраля 2019 Двойственность. Сопряжённые функции / нормы. Конспект
8 5 марта 2019 Субдифференциальное исчисление. Конспект
9 12 марта 2019 Проксимальные операторы.

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

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

  • Практика №1, дэдлайны — мягкий: 12 февраля (23:59), жёсткий: 20 февраля (23:59).
  • Практика №2, дэдлайны — мягкий: 2 марта (23:59), жёсткий: 10 марта (23:59).
  • Практика №3, дэдлайны — мягкий: 14 марта (23:59), жёсткий: 22 марта (23:59).

Дополнительный материал

  • Конспект по матрично-векторным скалярным произведениям и нормам.

Литература

  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.
  10. Y. Nesterov. Lectures on convex optimization, Springer, 2018.