1. Понятие о численных методах оптимизации. Сильно выпуклые задачи, выпуклые (вырожденные) задачи, невыпуклые задачи. Гладкие, негладкие задачи. ([1] п. 2.1 - таблица 2.1 и ее обоснование, п. 2.4)
2. Регуляризация и рестарты. Привести примеры! ([1] пп. 2.1, 2.10.8)
3. Метод градиентного спуска. Выпуклые задачи. Невыпуклые задачи (сходимость к локальному экстремуму). ([2] параграф 1)
4. Невыпуклая оптимизация. Примеры трудных задач невыпуклой оптимизации. ([2] параграф 1)
5. Условие Поляка-Лоясиевича (ПЛ) и глобальная сходимость градиентного спуска для невыпуклых задач, целевая функция которых удовлетворяет условию (ПЛ). Как изменятся оценки скорости сходимости, если градиент доступен с аддитивным шумом в концепции относительной точности? Сведение решение системы нелинейных уравнений к задаче оптимизации с условием (ПЛ). ([2] параграф 1; [1] п. 2.11.1)
6. Двойственная задача. Слабая и сильная двойственность для задач выпуклой оптимизации. Теорема о минмаксе (Фон Неймана, Сион-Какутани) (без доказательства). Понятие о прямо-двойственных методах на примере решение задачи минимизации выпуклого сепарабельного функционала с аффинными ограничениями с помощью перехода к двойственной задаче и ее решения методом градиентного спуска. ([2] параграф 4 (на лекции было изложение в варианте с регуляризацией - см. упражнение 4.4); [1] п. 1.9)
7. Унимодальные функции одной переменной. Методы одномерной минимизации (метод дихотомии, метод золотого сечения). Задача о распределении ресурсов. ([1] п. 2.2.1; [1] упражнение 4.7)
8. Методы маломерной оптимизации: метод центров тяжести, метод эллипсоидов. ([1] пп. 2.2.2, 2.2.3; [2] упражнение 1.4)
9. Способы выбора шага в методах. Наискорейший спуск. Адаптивный способ выбора шага. ([2] замечание 1.4, стр. 58-60, упражнение 2.6)а
10. Сопряженные направления. Метод сопряженных градиентов для минимизации квадратичных функций. Метод сопряженных градиентов для решения задач выпуклой оптимизации. ([1], п. 2.4; [2] замечание 1.6)
11. Метод тяжелого шарика Поляка. Метод Чебышева. Ускоренный градиентный метод (метод подобных треугольников). ([1], п. 2.4)
12. Задачи оптимизации на множествах простой структуры. Дивергенция Брэгмана. Метод проекции (суб-)градиента, метод зеркального спуска. ([2], параграф 2; [1] п. 2.10)
13. Метод условного градиента (Франк-Вульфа). Пример задачи минимизации квадратичной формы с разреженной положительно определенной матрицей на единичном симплексе. ([2] упражнение 1.6; [1] пп. 2.6, 3.5)
14. Композитная оптимизация. Пример Tomogravity model. ([2] п. 2.10.8; [1] параграфы 3 и 5)
15. Универсальный градиентный спуск. ([2] параграф 5)
16. (билет только для досрочного экзамена, появляется при согласии студента) Проксимальный градиентный спуск. Ускоренный проксимальный метод. Каталист - общий способ ускорения различных неускоренных методов. ([2] параграф 3 и Приложение; [1] п. 2.7)
17. Метод Ньютона. Окрестность квадратичной скорости сходимости. ([2] Приложение)
18. Стохастическая оптимизация. Минибатчинг и распараллеливание. ([2] Приложение; https://arxiv.org/pdf/1907.04232.pdf)
19. Рандомизированные методы. Минимизация квадратичной формы на симплексе. Покомпонентные методы. ([2] замечание 5.2 и Приложение)
20. Теория линейного программирования: Определение и представление политопов и полиэдров. Сложность представления, теорема Яннакакиса.
21. Двойственная линейная программа. Сильная двойственность в ЛП. Условия оптимальности.
22. Симплекс-метод: Определение симплекс-таблицы и (не)базового индексного множества. Допустимые, двойственно допустимые, оптимальные таблицы. Связь с вершинами прямого / двойственного допустимого полиэдра.
23. Применение в целочисленном ЛП: Формулировка задачи ЦЛП. Метод ветвлений и границ. Применение двойственного симплекс-метода в ЦЛП.
24. Методы внутренней точки в ЛП: Центральный путь задачи. Представление допустимого множества ЛП в ортанте переменных x_i*s_i. Длинно-шаговой метод для решения ЛП.

🚂 Материалы лекций со ссылками