Непрерывная оптимизация (ТИ, АДИС, АПР, РС) — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Dmitriy (обсуждение | вклад) (→Книги) |
Dmitriy (обсуждение | вклад) (→Лекции) |
||
| Строка 77: | Строка 77: | ||
== Лекции == | == Лекции == | ||
| − | + | {| class="wikitable" | |
| − | Зачем нужна оптимизация? Примеры задач невыпуклой оптимизации и нижние оценки сложности их решения. Понятие сопротивляющегося оракула (первый параграф пособия [1]). Введение в выпуклую оптимизацию. Основные понятия. Выпуклые функции, выпуклые множества. Теорема об отделимости. Принцип множителей Лагранжа | + | |- |
| − | + | ! Дата !! Преподаватель !! Описание !! Дополнительно | |
| − | + | |- | |
| − | Основные вспомогательные факты факты выпуклой оптимизации (формула Демьянова Данскина, двойственная задача и т.д.). Примеры задач | + | | 10.01.2020 || [https://www.hse.ru/org/persons/320473622 Иванова Анастасия Сергеевна] || Зачем нужна оптимизация? Примеры задач невыпуклой оптимизации и нижние оценки сложности их решения. Понятие сопротивляющегося оракула (первый параграф пособия [1]). Введение в выпуклую оптимизацию. Основные понятия. Выпуклые функции, выпуклые множества. Теорема об отделимости. Принцип множителей Лагранжа || |
| − | + | |- | |
| − | + | | 15.01.2020 || [https://www.hse.ru/org/persons/320473622 Иванова Анастасия Сергеевна] || Основные вспомогательные факты факты выпуклой оптимизации (формула Демьянова Данскина, двойственная задача и т.д.). Примеры задач || | |
| − | Градиентный спуск и его окрестности (все в евклидовой норме). Рассмотреть два случая когда оптимизация на всем пространстве и на выпуклом множестве простом относительно проектирования. Оценка скорости сходимости в выпуклом, сильно выпуклом случаях. В условии Поляка-Лоясиевича. В невыпуклом случае (первый параграф пособия [1]). Первые понятия об универсальных методах (второй и пятый параграф пособия [1]). | + | |- |
| + | | 22.01.2020 || [https://www.hse.ru/org/persons/161002023 Тюрин Александр Игоревич]|| Градиентный спуск и его окрестности (все в евклидовой норме). Рассмотреть два случая когда оптимизация на всем пространстве и на выпуклом множестве простом относительно проектирования. Оценка скорости сходимости в выпуклом, сильно выпуклом случаях. В условии Поляка-Лоясиевича. В невыпуклом случае (первый параграф пособия [1]). Первые понятия об универсальных методах (второй и пятый параграф пособия [1]). || | ||
| + | |- | ||
| + | | 29.01.2020 || [https://www.hse.ru/org/persons/161002023 Тюрин Александр Игоревич]|| Быстрый градиентный метод и его окрестности (все в евклидовой норме). Оценка скорости сходимости в выпуклом, сильно выпуклом случаях. Метод рестартов (можно по вот этой работе arXiv:1407.1537). Метод сопряженных градиентов. Понятие о нижних оценках скорости сходимости (первый параграф пособия [1]). || | ||
| + | |- | ||
| + | | 05.02.2020 || [https://www.hse.ru/org/persons/? Титов Александр Александрович]|| Негладкая выпуклая оптимизация на выпуклых множествах. Понятие прокс-функции. Метод зеркального спуска. Метод зеркального спуска для задач с функциональными ограничениями (второй параграф пособия [1]). || | ||
| + | |- | ||
| + | | 12.02.2020 || Гасников|| Модельная общность для задач выпуклой оптимизации. Относительная гладкость, Неточность в градиенте и при проектировании. Градиентный спуск и быстрый градиентный метод в модельной общности. Универсальные методы в модельной общности (третий и пятый параграф пособия [1] и arXiv:1902.00990) || | ||
| + | |- | ||
| + | | 19.02.2020 || [https://www.hse.ru/org/persons/? Титов Александр Александрович]|| Примеры выпукло-вогнутых седловых задач (отсюда arXiv:1410.3118 arXiv:1501.02205 можно взять мотивировочные примеры) и монотонных вариационных неравенств (тут можно упомянуть конкурентное равновесие Вальраса в модели Эрроу-Дебре - см., например, книги Никайдо и Ашманова). Постановка задачи. Основные алгоритмы. Метод Mirror Prox и его работа в условиях неточно заданного градиента, неточного проектирования (можно по arXiv:1902.00990). || | ||
| + | |- | ||
| + | | 26.02.2020 || [https://www.hse.ru/org/persons/320473622 Иванова Анастасия Сергеевна]|| Прямо-двойственные методы. Прямо-двойственность градиентного спуска, быстрого градиентного спуска. Пример решения задачи сильно выпуклой оптимизации при аффинных ограничениях. Сходимость по норме градиента. Восстановление решение прямой задачи по последовательности точек, сгенерированной методом, решающим двойственную задачу (четвертый параграф пособия [1]). || | ||
| + | |- | ||
| + | | 04.03.2020 || Шпирко|| Регуляризация прямой задачи. Сглаживание прямой задачи, через регуляризацию двойственной (замечание 4.1 пособия [1], см. также [7]). Примеры приложения двойственного сглаживания (задачи вида минимизации функции максимума). Метод штрафных функций (четвертый параграф пособия [1]). || | ||
| + | |- | ||
| + | | 11.03.2020 || Шпирко|| Решение задач выпуклой оптимизации больших размеров с помощью субградиентных методов и метода условного градиента. Примеры: упражнение 1.6 пособия [1], Truss Topology Design. || | ||
| + | |- | ||
| + | | 18.03.2020 || Шпирко|| Квазиньютоновские методы BFGS, L-BFGS. Методы второго порядка. Метод Ньютона. Методы внутренней точки (см. [6]) || | ||
| + | |- | ||
| + | | 25.03.2020 || Шпирко|| Методы внутренней точки (продолжение) (см. [6]) || | ||
| + | |- | ||
| + | | 01.04.2020 || [https://www.hse.ru/org/persons/320473622 Иванова Анастасия Сергеевна]|| Каталист Монтейро-Свайтера (можно по arXiv:1911.11271). Слайдинг Лана (упражнение 3.8 пособия [1]). Опимальные тензорные методы (замечание 3.3 и приложение пособия). || | ||
| + | |- | ||
| + | | 08.04.2020 || [https://www.hse.ru/org/persons/161002023 Тюрин Александр Игоревич]|| Стохастический градиентный спуск. Понятие о минибатчинге. Адаптивные процедуры (приложение пособия [1] и arXiv:1911.08380). AdaGrad, Adam, метод Баха-Леви arXiv:1902.01637 - их преимущества и недостатки https://openreview.net/pdf?id=ryQu7f-RZ || | ||
| + | |- | ||
| + | | 15.04.2020 || [https://www.hse.ru/org/persons/320473622 Иванова Анастасия Сергеевна]|| Примеры приложения каталиста к покомпонентным методам и методам рандомизации суммы. Более подробный рассказ про покомпонентные/безградиентные методы и методы редукции дисперсии (минимизации функций вида суммы) (приложение пособи анных, статистики https://www.cs.cornell.edu/~sridharan/thesis.pdf || | ||
| + | |- | ||
| + | | 29.04.2020 || [https://www.hse.ru/org/persons/320473622 Иванова Анастасия Сергеевна]|| Введение в распределенную оптимизацию. Централизованная оптимизация на примере задачи о распределении ресурсов arXiv:1806.09071, arXiv:1909.13321, arXiv:1911.07354). Децентрализованная оптимизация arXiv:1904.09015, arXiv:1911.07363 || | ||
| + | |- | ||
| + | |} | ||
== Семинары == | == Семинары == | ||
Версия 17:59, 14 января 2020
Содержание
О курсе
Курс читается для студентов 3-го курса ПМИ ФКН ВШЭ в 3-4 модулях.
Лектор: Гасников Александр Владимирович
Полезные ссылки
Канал в telegram для объявлений: https://t.me/optimizationHSE2020
Чат в telegram для обсуждений (предназначение чата до конца не ясно, вопросы может быть правильнее задавать в чатах групп):
Ссылка на курс в Anytask:
[ Таблица с оценками]
Семинары
| Группа | Преподаватель | Учебный ассистент |
|---|---|---|
| 173 (ТИ) | Титов Александр Александрович | |
| 174 (АДИС) | Тюрин Александр Игоревич | |
| 175 (РС) | Иванова Анастасия Сергеевна | [Дмитрий Макаренко] |
| 176 (РС) | Иванова Анастасия Сергеевна | [Дмитрий Макаренко] |
| 177 | Иванова Анастасия Сергеевна | [Дмитрий Макаренко] |
Правила выставления оценок
В курсе предусмотрено несколько форм контроля знания:
- Домашние работы (теоретические и практические)
- Письменная контрольная работа
- Экзамен
- Проект, включающий в себя теоретическую и практическую часть
- Самостоятельные работы на семинарах, проверяющие знание основных фактов с лекций и с ДЗ
Итоговая оценка вычисляется на основе оценки за работу в семестре и оценки за экзамен:
Итог = MIN{Округление(0.15 * ДЗ + 0.20 * КР + 0.3 * Э + 0.35 * ПР + 0.1 * СР), 10}
ДЗ — средняя оценка за домашние работы
КР — оценка за контрольную работу
Э — оценка за экзамен
ПР — оценка за проект
СР — средняя оценка за самостоятельные работы на семинарах
Округление вниз.
Правила сдачи заданий
За каждый день просрочки после мягкого дедлайна снимается 1 балл. После жёсткого дедлайна работы не принимаются. Даже при опоздании на одну секунду. Сдавайте заранее. Есть исключения, о них написано ниже.
При обнаружении плагиата оценки за домашнее задание обнуляются всем задействованным в списывании студентам, а также подаётся докладная записка в деканат. Следует помнить, что при повторном списывании деканат имеет право отчислить студента.
При наличии уважительной причины пропущенную проверочную можно написать позднее, а дедлайн по домашнему заданию может быть перенесён. Дедлайн по домашнему заданию переносится на количество дней, равное продолжительности уважительной причины. Решение о том, является ли причина уважительной, принимает исключительно учебный офис.
Лекции
| Дата | Преподаватель | Описание | Дополнительно |
|---|---|---|---|
| 10.01.2020 | Иванова Анастасия Сергеевна | Зачем нужна оптимизация? Примеры задач невыпуклой оптимизации и нижние оценки сложности их решения. Понятие сопротивляющегося оракула (первый параграф пособия [1]). Введение в выпуклую оптимизацию. Основные понятия. Выпуклые функции, выпуклые множества. Теорема об отделимости. Принцип множителей Лагранжа | |
| 15.01.2020 | Иванова Анастасия Сергеевна | Основные вспомогательные факты факты выпуклой оптимизации (формула Демьянова Данскина, двойственная задача и т.д.). Примеры задач | |
| 22.01.2020 | Тюрин Александр Игоревич | Градиентный спуск и его окрестности (все в евклидовой норме). Рассмотреть два случая когда оптимизация на всем пространстве и на выпуклом множестве простом относительно проектирования. Оценка скорости сходимости в выпуклом, сильно выпуклом случаях. В условии Поляка-Лоясиевича. В невыпуклом случае (первый параграф пособия [1]). Первые понятия об универсальных методах (второй и пятый параграф пособия [1]). | |
| 29.01.2020 | Тюрин Александр Игоревич | Быстрый градиентный метод и его окрестности (все в евклидовой норме). Оценка скорости сходимости в выпуклом, сильно выпуклом случаях. Метод рестартов (можно по вот этой работе arXiv:1407.1537). Метод сопряженных градиентов. Понятие о нижних оценках скорости сходимости (первый параграф пособия [1]). | |
| 05.02.2020 | Титов Александр Александрович | Негладкая выпуклая оптимизация на выпуклых множествах. Понятие прокс-функции. Метод зеркального спуска. Метод зеркального спуска для задач с функциональными ограничениями (второй параграф пособия [1]). | |
| 12.02.2020 | Гасников | Модельная общность для задач выпуклой оптимизации. Относительная гладкость, Неточность в градиенте и при проектировании. Градиентный спуск и быстрый градиентный метод в модельной общности. Универсальные методы в модельной общности (третий и пятый параграф пособия [1] и arXiv:1902.00990) | |
| 19.02.2020 | Титов Александр Александрович | Примеры выпукло-вогнутых седловых задач (отсюда arXiv:1410.3118 arXiv:1501.02205 можно взять мотивировочные примеры) и монотонных вариационных неравенств (тут можно упомянуть конкурентное равновесие Вальраса в модели Эрроу-Дебре - см., например, книги Никайдо и Ашманова). Постановка задачи. Основные алгоритмы. Метод Mirror Prox и его работа в условиях неточно заданного градиента, неточного проектирования (можно по arXiv:1902.00990). | |
| 26.02.2020 | Иванова Анастасия Сергеевна | Прямо-двойственные методы. Прямо-двойственность градиентного спуска, быстрого градиентного спуска. Пример решения задачи сильно выпуклой оптимизации при аффинных ограничениях. Сходимость по норме градиента. Восстановление решение прямой задачи по последовательности точек, сгенерированной методом, решающим двойственную задачу (четвертый параграф пособия [1]). | |
| 04.03.2020 | Шпирко | Регуляризация прямой задачи. Сглаживание прямой задачи, через регуляризацию двойственной (замечание 4.1 пособия [1], см. также [7]). Примеры приложения двойственного сглаживания (задачи вида минимизации функции максимума). Метод штрафных функций (четвертый параграф пособия [1]). | |
| 11.03.2020 | Шпирко | Решение задач выпуклой оптимизации больших размеров с помощью субградиентных методов и метода условного градиента. Примеры: упражнение 1.6 пособия [1], Truss Topology Design. | |
| 18.03.2020 | Шпирко | Квазиньютоновские методы BFGS, L-BFGS. Методы второго порядка. Метод Ньютона. Методы внутренней точки (см. [6]) | |
| 25.03.2020 | Шпирко | Методы внутренней точки (продолжение) (см. [6]) | |
| 01.04.2020 | Иванова Анастасия Сергеевна | Каталист Монтейро-Свайтера (можно по arXiv:1911.11271). Слайдинг Лана (упражнение 3.8 пособия [1]). Опимальные тензорные методы (замечание 3.3 и приложение пособия). | |
| 08.04.2020 | Тюрин Александр Игоревич | Стохастический градиентный спуск. Понятие о минибатчинге. Адаптивные процедуры (приложение пособия [1] и arXiv:1911.08380). AdaGrad, Adam, метод Баха-Леви arXiv:1902.01637 - их преимущества и недостатки https://openreview.net/pdf?id=ryQu7f-RZ | |
| 15.04.2020 | Иванова Анастасия Сергеевна | Примеры приложения каталиста к покомпонентным методам и методам рандомизации суммы. Более подробный рассказ про покомпонентные/безградиентные методы и методы редукции дисперсии (минимизации функций вида суммы) (приложение пособи анных, статистики https://www.cs.cornell.edu/~sridharan/thesis.pdf | |
| 29.04.2020 | Иванова Анастасия Сергеевна | Введение в распределенную оптимизацию. Централизованная оптимизация на примере задачи о распределении ресурсов arXiv:1806.09071, arXiv:1909.13321, arXiv:1911.07354). Децентрализованная оптимизация arXiv:1904.09015, arXiv:1911.07363 |
Семинары
Практические задания
Теоретические домашние задания
Контрольная работа
Экзамен
Полезные материалы
Книги
- Гасников А. В. Современные численные методы оптимизации. Метод универсального градиентного спуска. – М.: МФТИ, 2018.
- Гасников А. В. Презентации к избранным частям курса (наиболее важными являются презентации 1-4)
- Поляк Б.Т. Введение в оптимизацию. Изд. 2-ое, испр. и доп. – М.: ЛЕНАНД, 2014.
- Boyd S., Vandenberghe L. Convex optimization. – Cambridge University Press, 2004.
- Bubeck S. Convex optimization: algorithms and complexity. – Foundations and Trends in Machine Learning, 2015. – V. 8, N 3–4. – P. 231–357.
- Nemirovski A. Advanced Nonlinear Programming. – Lectures, ISyE 7683 Spring 2019.
- Nesterov Yu. Lectures on convex optimization. – Springer, 2018.
- Lan G. Lectures on optimization. Methods for Machine Learning, 2019.
