Учебник Методы оптимизации для начинающих

Программа курса

1. 1 Что такое оптимизация

   1. Оптимизация вокруг нас

      Что такое оптимизация на интуитивном уровне: поиск наилучшего решения среди допустимых, примеры из ML, экономики, логистики.

   2. Целевая функция и ландшафт

      Геометрическая интуиция оптимизации: целевая функция как ландшафт, линии уровня, долины и хребты, минимум как дно впадины.

   3. Зоопарк задач оптимизации

      Классификация задач оптимизации: непрерывные и дискретные, выпуклые и невыпуклые, с ограничениями и без, гладкие и негладкие.

2. 2 Матанализ для оптимизации

   1. Градиент — направление наискорейшего роста

      Градиент функции многих переменных: что это, почему он указывает в сторону роста и как посчитать его численно на чистом Python.

   2. Гессиан и кривизна

      Матрица вторых производных (гессиан): что она говорит о кривизне функции, выпуклости и почему важна для метода Ньютона.

   3. Условия оптимальности

      Необходимое условие минимума $\nabla f=0$ и достаточное условие через гессиан: как математически распознать оптимум.

   4. Выпуклость с точки зрения анализа

      Определение выпуклой функции через хорду и через гессиан, почему выпуклость гарантирует, что локальный минимум глобален.

3. 3 Одномерная оптимизация

   1. Зачем уметь искать минимум по одной переменной

      Одномерная оптимизация как кирпичик многомерных методов: линейный поиск длины шага, унимодальность, интервал неопределённости.

   2. Метод золотого сечения

      Метод золотого сечения для поиска минимума унимодальной функции: идея сужения интервала, коэффициент $\varphi$ и исполнимая реализация.

4. 4 Градиентный спуск

   1. Идея и формула спуска

      Градиентный спуск: почему шаг против градиента уменьшает функцию, формула $x_{k+1}=x_k-\alpha\nabla f(x_k)$ и первая реализация.

   2. Learning rate: между медленно и расходится

      Как длина шага влияет на градиентный спуск: малый шаг тормозит, большой расходится; критический шаг и идея адаптации.

   3. Овраги и осцилляция

      Почему градиентный спуск медленно ползёт в вытянутых оврагах, что такое плохая обусловленность и как зигзаг убивает скорость.

5. 5 Ускорения градиентного спуска

   1. Momentum — инерция спуска

      Метод момента: накопление скорости как у шарика, скатывающегося по склону; формула, гашение осцилляций и реализация.

   2. Ускорение Нестерова и Adam

      Метод Нестерова (взгляд вперёд) и Adam (адаптивный шаг на координату): два главных ускорителя современного обучения, с реализацией Adam.

6. 6 Метод Ньютона и второй порядок

   1. Ньютон: учитываем кривизну

      Метод Ньютона для минимизации: квадратичная модель функции, формула шага через обратный гессиан и квадратичная сходимость с реализацией.

   2. Квазиньютоновские методы и BFGS

      Квазиньютоновские методы строят приближение обратного гессиана по градиентам: идея BFGS, L-BFGS для больших задач, баланс цены и скорости.

7. 7 Линейное программирование

   1. Геометрия линейных задач

      Линейное программирование: целевая и ограничения линейны, допустимое множество — многогранник, оптимум всегда в вершине.

   2. Симплекс-метод

      Симплекс-метод: движение по рёбрам многогранника от вершины к вершине с улучшением цели, симплекс-таблица и реализация на малой задаче.

   3. Двойственность и интерпретация

      Двойственность в линейном программировании: прямая и двойственная задача, теневые цены ресурсов и слабая/сильная двойственность.

8. 8 Оптимизация с ограничениями

   1. Множители Лагранжа

      Метод множителей Лагранжа для задач с равенствами: условие касания $\nabla f=\lambda\nabla g$, геометрическая интуиция и пример.

   2. Условия Каруша–Куна–Таккера

      Условия ККТ обобщают Лагранжа на неравенства: стационарность, допустимость, неотрицательность множителей и дополняющая нежёсткость.

   3. Штрафные функции

      Метод штрафных функций: превращаем задачу с ограничениями в безусловную, добавляя штраф за нарушение, с реализацией и анализом.

9. 9 Метаэвристики

   1. Имитация отжига

      Имитация отжига (simulated annealing): температура, вероятностный приём ухудшающих шагов и побег из локальных минимумов на примере коммивояжёра.

   2. Генетические алгоритмы

      Генетический алгоритм: популяция решений, отбор, скрещивание и мутация по аналогии с эволюцией, с исполнимой реализацией.

   3. Роевые методы и обзор PSO

      Метод роя частиц (PSO): частицы летают в пространстве решений, ориентируясь на свой и общий лучший опыт; место PSO среди метаэвристик.

10. 10 Дискретная и комбинаторная оптимизация

    1. Задача о рюкзаке и динамическое программирование

       Задача о рюкзаке: выбрать предметы максимальной ценности при ограничении веса; точное решение динамическим программированием с реализацией.

    2. Коммивояжёр и NP-трудность

       Задача коммивояжёра, понятие NP-трудности, почему точные методы экспоненциальны и когда переходить к эвристикам и приближениям.

11. 11 Стохастика, практика и инструменты

    1. Стохастический градиентный спуск

       SGD и мини-батчи: почему в машинном обучении считают градиент по части данных, шум как помощник и реализация на линейной регрессии.

    2. Многокритериальная оптимизация и Парето

       Многокритериальная оптимизация: конфликтующие цели, доминирование по Парето, Парето-фронт и способы свести задачу к однокритериальной.

    3. Как выбрать метод оптимизации

       Практическое руководство по выбору метода оптимизации под задачу: дерево решений по выпуклости, размерности, ограничениям и наличию градиента.

    4. Инструменты и применения

       Обзор солверов оптимизации: scipy.optimize, cvxpy, OR-Tools, PuLP — что и когда использовать, и где оптимизация работает в реальном мире.