Оптимизация
Метод внутренней точки
В 1984 году Нарендра Кармаркар показал, что можно решать LP за полиномиальное время, двигаясь через центр допустимой области - революция после 37 лет симплекса. Сегодня IPM решает задачи управления портфелем на Уолл-стрит, обучает SVM и оптимизирует спутниковые манёвры - там, где симплекс не справляется.
- **Финансы:** портфельная оптимизация (Markowitz QP) с тысячами активов решается MOSEK IPM за секунды в Bloomberg Terminal
- **ML:** обучение SVM сводится к QP; IPM-солверы (LIBSVM, SMO) обучают на миллионах примеров
- **Аэрокосмос:** траектории спутников оптимизируются как SOCP - только IPM справляется с такой структурой
Предварительные знания
Барьерный метод
Задача с неравенствами-ограничениями: min f(x) s.t. gᵢ(x) ≤ 0. Идея барьерного метода - добавить **логарифмический барьер** к целевой функции, который уходит в +∞ при приближении к границе допустимой области. Это превращает ограниченную задачу в безограниченную.
**Почему лог-барьер?** -log(-g(x)) стремится к +∞ при g(x)→0⁻ и равен 0 при g(x)=-1 (глубоко внутри). Он «отталкивает» решение от границ, заставляя оставаться строго внутри допустимой области. При увеличении t барьер становится менее значимым, и решение приближается к истинному оптимуму.
Барьерный метод работает только для **строго допустимых** начальных точек (interior feasible start): нужна точка x₀ с gᵢ(x₀) < 0 для всех i. Найти такую начальную точку - отдельная задача (Phase I).
Почему логарифмический барьер -log(-g(x)) эффективен для работы с ограничением g(x) ≤ 0?
Центральный путь
При варьировании параметра t от 0 до ∞ оптимумы барьерных задач образуют кривую внутри допустимой области - **центральный путь** x*(t). Это непрерывная траектория от некоторой центральной точки (t→0) до оптимума (t→∞). Interior point методы движутся вдоль этого пути.
Теоретическая сложность IPM: **O(√n · log(1/ε))** шагов Ньютона для достижения точности ε. Каждый шаг Ньютона требует O(n³) операций (решение системы линейных уравнений). Итого: O(n^3.5 · log(1/ε)) - полиномиальная сложность, в отличие от worst-case экспоненциального симплекса.
| Метод | Сложность | Практика |
|---|---|---|
| Симплекс | worst-case: O(2ⁿ) | Быстрый на практике, не полиномиальный |
| IPM (LP) | O(n^3.5 log(1/ε)) | Полиномиальный, медленнее симплекса на простых задачах |
| IPM (QP/SOCP) | O(n^3.5 log(1/ε)) | Лучший выбор для выпуклых нелинейных задач |
| IPM (SDP) | O(n^6.5 log(1/ε)) | Единственный эффективный метод для SDP |
Что такое центральный путь в IPM и зачем он нужен?
Шаги Ньютона в IPM
На каждом шаге IPM нужно приближённо решить барьерную задачу для текущего t. Используется **метод Ньютона**: квадратичное приближение барьерной функции вокруг текущей точки x. Шаг Ньютона: Δx = -(∇²F(x))⁻¹ ∇F(x), где F = t·f - Σlog(-gᵢ).
**Duality gap** в IPM: на каждом шаге гарантия качества решения - m/t, где m - число ограничений. При t → ∞ гарантированная ошибка → 0. Это позволяет точно контролировать точность решения, в отличие от симплекса, где качество нельзя оценить до завершения.
В барьерном методе параметр t постепенно увеличивается (умножается на μ > 1). Что происходит при слишком большом μ?
Primal-Dual IPM и применения
**Primal-dual IPM** - более эффективная вариация: одновременно обновляет прямые (x) и двойственные переменные (y, s), применяя один общий шаг Ньютона к системе KKT-условий с барьером. Это стандарт в промышленных солверах (MOSEK, GUROBI IPM, CLARABEL).
**Когда использовать IPM vs симплекс:** для LP на больших разреженных задачах - симплекс быстрее (warm-start, re-optimization). Для QP, SOCP, SDP - IPM единственный практичный метод. CVXPY автоматически выбирает solver на основе типа задачи.
Метод внутренней точки всегда медленнее симплекса
Для LP на малых и средних задачах симплекс часто быстрее. Для QP, SOCP и SDP IPM - единственный эффективный метод. Для очень больших LP IPM конкурентен благодаря полиномиальной сложности.
Симплекс имеет превосходный warm-start и повторную оптимизацию. IPM не переиспользует информацию между итерациями и требует разложения матрицы O(n³) на каждом шаге. Но для задач с нелинейной целью (QP) Гессе уже встроена в шаг Ньютона, что даёт IPM структурное преимущество.
Почему IPM является предпочтительным методом для квадратичного программирования (QP), а не симплекс?
Ключевые идеи
- **Барьерный метод:** заменяет ограничения логарифмическим барьером -Σlog(-gᵢ); решение барьерной задачи приближается к оптимуму при t→∞
- **Центральный путь:** кривая x*(t) оптимумов барьерной задачи; IPM движется вдоль неё шагами Ньютона
- **Сложность:** O(√n · log(1/ε)) шагов Ньютона - полиномиальная гарантия; каждый шаг O(n³)
- **Primal-dual IPM:** стандарт в CVXPY/MOSEK; лучший выбор для QP, SOCP, SDP
Связанные темы
IPM использует выпуклость и дополняет симплекс для нелинейных задач:
- Выпуклая оптимизация — IPM разработан для выпуклых задач; без выпуклости барьерный метод не гарантирует оптимум
- KKT условия — Primal-dual IPM применяет шаги Ньютона к возмущённым KKT условиям
- Линейное программирование — IPM - альтернатива симплексу для LP с полиномиальной гарантией
Вопросы для размышления
- Почему логарифмический барьер работает лучше, чем простой штраф max(0, gᵢ(x)) за нарушение ограничения? Что происходит с градиентом при приближении к границе?
- Симплекс двигается по границе допустимой области (вершины), IPM - внутри. В чём практические преимущества каждого подхода для разных типов задач?
- Как CVXPY решает задачу портфельной оптимизации? Какой тип задачи (LP/QP/SOCP) она представляет и какой solver выбирается автоматически?