Метод внутренней точки

1984. Нарендра Кармаркар из Bell Labs публикует алгоритм для LP со сложностью $O(n^{3.5})$. Simplex мог работать экспоненциально. Interior point - полиномиально. Karmarkar's paper перевернул теорию, но Simplex до сих пор быстрее на практике. Почему? Потому что сложность в худшем случае и сложность на типичных задачах - разные вещи. Interior point побеждает там, где Simplex тонет: большие SDP, плотные QP, плохо обусловленные задачи. SVM, portfolio optimization, compressed sensing, network flow - всё это решается через IPM. CVXPY, MOSEK, Gurobi, HiGHS - под капотом у всех один и тот же алгоритм: log-барьер + шаги Ньютона + $t \to \infty$.

• **SVM dual QP (libsvm, sklearn):** классификатор обучается через IPM на квадратичной программе - support vectors это KKT complementary slackness на практике
• **CVXPY / CVX:** frontend для сотен ADMM и IPM вызовов в день - portfolio opt, resource allocation, MPC в робототехнике
• **Portfolio optimization (Black-Litterman):** ежедневный пересчёт весов активов через QP, ECOS делает 10-20 шагов Ньютона за миллисекунды
• **Compressed sensing (basis pursuit):** L1-минимизация через LP с $2n$ ограничениями, Gurobi решает за $O(\sqrt{n})$ итераций IPM

Предварительные знания

• KKT-условия
• Сходимость GD

Log-барьер и центральный путь

**1984. Карел Рэймпорт, Bell Labs. Нарендра Кармаркар публикует алгоритм для LP со сложностью $O(n^{3.5})$.** Simplex мог работать экспоненциально на патологических задачах - это было известно с 1972 года (Klee-Minty cube). Кармаркар доказал: существует метод с полиномиальной гарантией. Но вот парадокс - Simplex до сих пор быстрее на 99% реальных задач. Interior point выигрывает только на плохо обусловленных и очень больших LP. Почему метод с лучшей теорией проигрывает на практике? Ответ в том, как именно он устроен.

Стандартная задача с неравенствами: $\min_x f_0(x)$ при $f_i(x) \leq 0$, $i = 1, \ldots, m$. Ограничения создают барьер на границе допустимого множества. Идея барьерного метода - сделать барьер **явным** в целевой функции, а потом его убрать в пределе.

**Log-барьер и барьерная задача:** $$\phi_t(x) = t \cdot f_0(x) - \sum_{i=1}^{m} \log(-f_i(x))$$ Здесь $t > 0$ - параметр масштаба, $-\log(-f_i(x)) \to +\infty$ при $f_i(x) \to 0^-$ - функция уходит в бесконечность на границе. При $t$ большом первый член доминирует, и задача приближается к исходной. **Центральный путь** $x^*(t)$ - оптимальное решение барьерной задачи как функция от $t$: $$x^*(t) = \arg\min_{f_i(x) < 0} \phi_t(x)$$ При $t \to \infty$: $x^*(t) \to x^*$ - центральный путь сходится к оптимуму исходной задачи.

CVXPY строит такой барьер автоматически. Когда пишется `prob.solve(solver='ECOS')` - под капотом ECOS (Embedded Conic Solver) следует по центральному пути, увеличивая $t$ на каждой итерации. SVM в scikit-learn с `kernel='linear'` через liblinear тоже использует interior point внутри dual LP. Gurobi и CPLEX - лидеры коммерческих LP/QP-решателей - по умолчанию запускают IPM для задач с плотными матрицами.

**Оценка зазора:** на центральном пути при заданном $t$ достигается гарантия качества: $$f_0(x^*(t)) - f_0(x^*) \leq \frac{m}{t}$$ Для точности $\varepsilon$: достаточно $t \geq m / \varepsilon$. Чем больше ограничений $m$, тем крупнее $t$ нужен - и тем сложнее подзадача внутри.

Шаг Ньютона в барьерной подзадаче

Барьерная функция $\phi_t$ - строго выпуклая и дважды дифференцируемая везде внутри допустимого множества. Идеальный кандидат для метода Ньютона. GD на такой функции имел бы сходимость $(1-1/\kappa)^k$ - и $\kappa$ может быть огромным. Ньютон при той же геометрии сходится **квадратично** в окрестности оптимума: ошибка на каждой итерации возводится в квадрат.

**Шаг Ньютона для $\phi_t$:** $$\Delta x_{nt} = -[\nabla^2 \phi_t(x)]^{-1} \nabla \phi_t(x)$$ Для барьерной задачи: $$\nabla \phi_t(x) = t \nabla f_0(x) + \sum_{i=1}^{m} \frac{1}{-f_i(x)} \nabla f_i(x)$$ $$\nabla^2 \phi_t(x) = t \nabla^2 f_0(x) + \sum_{i=1}^{m} \frac{1}{f_i(x)^2} \nabla f_i(x) \nabla f_i(x)^T - \sum_{i=1}^{m} \frac{1}{-f_i(x)} \nabla^2 f_i(x)$$ **Декремент Ньютона** - мера близости к оптимуму в метрике Гессиана: $$\lambda(x)^2 = \nabla \phi_t(x)^T [\nabla^2 \phi_t(x)]^{-1} \nabla \phi_t(x)$$ Остановка: $\lambda(x)^2 / 2 \leq \varepsilon$.

Portfolio optimization - классика interior point. Markowitz (1952): $\min_w w^T \Sigma w$ при $\mathbf{1}^T w = 1$, $w \geq 0$ (или с заданной доходностью $\mu^T w \geq r$). Black-Litterman модель добавляет prior на доходности - задача превращается в QP. CVXPY решает его за миллисекунды через ECOS, который делает 10-30 шагов Ньютона внутри барьера. Hedge-фонды пересчитывают портфель ежедневно - 250 QP в год, каждый через IPM.

**Алгоритм барьерного метода (схема):** ``` вход: начальная точка x (feasible), t_0 > 0, mu > 1, epsilon повторять: 1. Центрирование: решить min phi_t(x) методом Ньютона (до lambda^2/2 <= epsilon_inner) 2. Обновление: t := mu * t 3. Остановка: m/t <= epsilon ``` **Выбор $\mu$**: большой $\mu$ - меньше внешних итераций, но сложнее каждое центрирование. Типичное значение $\mu = 10$-$20$. На каждом центрировании Ньютон делает $O(1)$ шагов (если задача само-согласована).

Само-согласованность и полиномиальная сложность

Почему log-барьер работает настолько хорошо? У Ньютона на произвольной выпуклой функции нет гарантии на количество итераций до $\varepsilon$-точности: функция может иметь произвольную кривизну. Log-барьер обладает особым свойством - **само-согласованностью** (self-concordance). Нестеров и Немировский ввели этот класс в 1994 году и доказали полиномиальную сложность IPM именно через него.

**Само-согласованность (Nesterov-Nemirovskii 1994):** Функция $f: \mathbb{R} \to \mathbb{R}$ само-согласована, если: $$|f'''(x)| \leq 2 [f''(x)]^{3/2}$$ Для многомерного случая (вдоль любого направления $v$): производные третьего порядка ограничены через кривизну. **Следствие:** в $\lambda$-регионе (где $\lambda(x) < 1$) Ньютон сходится квадратично с **гарантированным числом итераций** - без знания глобальных $L$, $\mu$. **Log-барьер само-согласован:** $-\log(x)$ для $x > 0$ удовлетворяет условию с точностью до константы. Сумма само-согласованных функций - само-согласована. Поэтому $\phi_t(x)$ - само-согласована. **Сложность IPM через само-согласованность:** $$\text{Newton iterations per centering} = O(\sqrt{m} \log(m / \varepsilon))$$ Общая сложность: $O(\sqrt{m})$ центрирований $\times$ $O(1)$ шагов Ньютона = $O(\sqrt{m} \log(1/\varepsilon))$ итераций.

Compressed sensing - minimization $\|x\|_1$ при $Ax = b$ (basis pursuit). Через LP-реформулировку: ввести $t_i \geq 0$ с $-t_i \leq x_i \leq t_i$, минимизировать $\sum t_i$. Результирующий LP с $m = 2n$ ограничениями - прямо для interior point. Gurobi решает basis pursuit за $O(\sqrt{n})$ итераций IPM. Это быстрее, чем iterative thresholding (ISTA/FISTA) при плохо обусловленных $A$.

**Самосогласованные барьеры для конических программ:** - **LP** ($x \geq 0$): $-\sum_i \log x_i$ - стандартный барьер, $m$ параметр - **SOCP** ($\|Ax + b\| \leq c^T x + d$): $-\log(t^2 - \|u\|^2)$ - барьер для second-order cone - **SDP** ($X \succeq 0$): $-\log \det X$ - матричный log-барьер Все три - само-согласованы. Именно поэтому CVXPY/CVX решает LP, SOCP и SDP одним и тем же движком (MOSEK, ECOS, SCS) - разные проблемы, одна алгоритмическая схема.

Primal-dual IPM и практика: CVXPY, Gurobi, SVM

Барьерный метод - **primal** метод: на каждом шаге находится допустимая прямая точка $x^*(t)$, двойственные переменные восстанавливаются постфактум. **Primal-dual IPM** следит за прямыми и двойственными переменными одновременно, решая KKT-систему напрямую. Это метод, реализованный в Gurobi, CPLEX, MOSEK - коммерческих решателях, которые обрабатывают LP с миллионами переменных.

**Primal-dual IPM - KKT-итерация:** KKT-условия для задачи с $f_i(x) \leq 0$: $$\nabla f_0(x^*) + \sum_i \lambda_i^* \nabla f_i(x^*) = 0$$ $$\lambda_i^* f_i(x^*) = 0 \quad (\text{complementary slackness})$$ $$f_i(x^*) \leq 0, \quad \lambda_i^* \geq 0$$ Predictor-corrector шаг: ввести **surrogate дополнительность** $\lambda_i |f_i(x)| = 1/t$ (вместо нуля). При $t \to \infty$ - сходимость к KKT. На каждом шаге Newton-like система: $$\begin{pmatrix} \nabla^2 f_0 + \sum \lambda_i \nabla^2 f_i & \nabla f_i^T \\ \Lambda F & \text{diag}(f_i) \end{pmatrix} \begin{pmatrix} \Delta x \\ \Delta \lambda \end{pmatrix} = \text{rhs}$$ **Convergence:** $O(\sqrt{m})$ итераций, каждая - решение линейной системы $O((n+m)^3)$ или $O(n^2 m)$ через sparse Cholesky.

SVM dual - квадратичная программа. Обучение SVM с $n$ примерами: $\max_\alpha \mathbf{1}^T \alpha - \frac{1}{2} \alpha^T Q \alpha$ при $y^T \alpha = 0$, $0 \leq \alpha_i \leq C$. Матрица $Q_{ij} = y_i y_j K(x_i, x_j)$ - ядровая. libsvm (Vapnik, Joachims 1999) использует SMO (sequential minimal optimization) - специализированный IPM для SVM. Sklearn `SVC` вызывает libsvm под капотом. CVXPY со solver='OSQP' решает тот же QP через ADMM, а с solver='ECOS' - через primal-dual IPM.

Network flow - LP на графе: $\min c^T f$ при $Bf = d$ (баланс потоков), $0 \leq f \leq u$ (пропускная способность). Матрица $B$ - инциденций, разреженная. Специализированные IPM используют разреженную Cholesky для $B^T B$ - сложность падает с $O(n^3)$ до $O(n^{1.5})$ для планарных графов. HiGHS (открытый LP-решатель, 2022) реализует именно этот вариант и обгоняет GLPK в 10-100 раз на крупных задачах.

Ключевые идеи

• **Log-барьер** $\phi_t(x) = t f_0(x) - \sum \log(-f_i(x))$ заменяет ограничения штрафом; центральный путь $x^*(t) \to x^*$ при $t \to \infty$
• **Гарантия качества:** $f_0(x^*(t)) - f_0(x^*) \leq m/t$ - точность определяется числом ограничений и параметром $t$
• **Шаг Ньютона внутри барьера** сходится квадратично; Newton decrement $\lambda(x)^2/2$ - адаптивный критерий остановки
• **Само-согласованность (Nesterov-Nemirovskii 1994):** $|f'''| \leq 2(f'')^{3/2}$ гарантирует $O(\sqrt{m} \log(1/\varepsilon))$ итераций без глобальных констант $L$, $\mu$
• **Primal-dual IPM** обновляет $x$ и $\lambda$ совместно через KKT-систему - это движок Gurobi, MOSEK, CPLEX

Что дальше

Interior point - вершина методов первого и второго порядка для convex задач. Дальше - декомпозиция и распределённые методы:

• Декомпозиция двойственности и ADMM — Dual decomposition расщепляет большие IPM-задачи на параллельные подзадачи
• KKT-условия — KKT - алгебраическое сердце IPM: primal-dual метод решает возмущённую KKT-систему
• Проксимальные методы — ISTA/FISTA - альтернатива IPM для структурированных негладких задач (LASSO, group sparsity)

Вопросы для размышления

• CVXPY решает SDP через IPM за $O(n^{3.5})$ операций. Для обучения нейросети размером $n = 10^6$ параметров это неприменимо - почему? Какие методы используются вместо IPM в таком масштабе?
• Само-согласованность log-барьера позволяет использовать Newton decrement $\lambda(x)^2/2$ как критерий остановки без знания $L$ и $\mu$. Как это связано с тем, что в GD нужен явный $L$ для выбора шага?
• Simplex быстрее IPM на типичных LP, но IPM выигрывает на QP и SDP. Что принципиально меняется в структуре задачи при переходе от LP к QP, что делает Simplex неэффективным?

Связанные уроки

• cvx-05 — KKT-условия - язык, на котором IPM находит оптимум
• cvx-06 — IPM заменяет GD на Ньютон внутри барьерной подзадачи
• cvx-07 — Проксимальные методы - соседний класс алгоритмов с иной структурой
• cvx-09 — Декомпозиция двойственности и ADMM строятся на KKT IPM
• ml-13-svm — SVM dual QP решается interior point методом
• calc-19-gradient — Градиент и Гессиан - основные объекты шага Ньютона
• la-06-gauss