Выпуклая оптимизация
Методы внутренней точки и самосогласованные барьеры
Симплекс-метод работал десятилетиями, но никто не мог доказать его полиномиальность. В 1984 году Хачиян дал теоретическое доказательство, а Нестеров и Немировский - практически эффективный полиномиальный алгоритм через барьерные функции.
- CVXPY: используется в 1600+ научных статьях 2023 года, решает LP/QP/SDP за полиномиальное время через interior-point методы с единым интерфейсом
- Финансовая оптимизация портфеля: задача Марковица с n=10000 активами решается за секунды interior-point против часов симплекс-метода
- H-infinity управление: синтез робастного регулятора для авиации сводится к SDP, решаемой за O(n^{3.5}) операций
- Компиляторы и верификация: проверка безопасности программ через абстрактную интерпретацию требует тысячи LP за секунды
Предварительные знания
- Выпуклые множества и функции
- Условия KKT
- Метод Ньютона
Метод барьеров: логарифмический барьер
Метод барьеров - первая ветвь internal-point методов, восходящая к работам Fiacco-McCormick (1968). Идея: заменить задачу с ограничениями на серию задач без ограничений, добавив штрафной член, который стремится к бесконечности при приближении к границе допустимой области. Логарифмический барьер - канонический выбор, обеспечивающий полиномиальную сложность для линейного и квадратичного программирования.
Шаг увеличения t - ключевой параметр. Обычно t_{k+1} = mu * t_k с mu в диапазоне 10-100. Большое mu - меньше внешних итераций, но каждая внутренняя задача сложнее. Оптимальный mu ~ exp(O(sqrt(m))) - дает O(sqrt(m)*log(1/eps)) суммарных Ньютоновских шагов.
Какое свойство логарифмического барьера обеспечивает полиномиальную сложность?
Прямо-двойственные методы
Прямо-двойственные методы (Mehrotra 1992) отказываются от строгой последовательности внешних задач барьерного метода. Вместо этого они работают одновременно с прямой переменной x, двойственной lambda и параметром перехода t. Шаги Ньютона решают возмущённые KKT-условия, обеспечивая практически наилучшую сходимость на больших задачах.
Предиктор-корректор Mehrotra - стандарт индустриальных решателей (CPLEX, Gurobi). Предиктор делает шаг к границе, корректор подкрашивает дисбаланс комплементарности. Эмпирически в 2-3 раза быстрее простого предиктора.
В отличие от чистого барьерного метода, прямо-двойственный не требует строгой внутренней точки на старте - infeasible-start варианты работают с произвольным x, lambda > 0. Это критично для крупных промышленных задач, где найти feasible-точку само по себе сложно.
Чем прямо-двойственные методы отличаются от чистого барьерного метода?
Теория сходимости и сложность
Теория сложности interior-point методов революционна: Karmarkar (1984) показал, что линейное программирование решается за полиномиальное время, опровергнув предположение о субэкспоненциальной сложности всех методов отличных от симплекса. Современная теория (Nesterov-Nemirovski 1994) даёт единое доказательство для широкого класса self-concordant функций.
Self-concordant барьеры существуют для всех замкнутых выпуклых множеств с непустой внутренностью, но конструктивные формулы известны только для канонических конусов: положительный ортант (log-barrier), Lorentz cone (log of quadratic), positive semidefinite cone (log det). Симметричные конусы покрывают все практически важные классы.
Для задач с сильным duality gap или плохо обусловленных задач IPM может страдать numerical issues около границы. Регуляризация Mehrotra (slack variables, perturbation) восстанавливает устойчивость; современные решатели используют iterative refinement и presolve для предварительной подготовки задачи.
Эмпирически современные IPM-решатели (CPLEX, Gurobi, Mosek) решают LP с миллионами переменных за секунды, SDP с тысячами переменных за минуты. Для очень больших задач (n > 10^7) применяются first-order методы (ADMM, accelerated gradient), уступающие IPM по точности, но масштабируемые по памяти.
Что определяет полиномиальную сложность interior-point методов?
Ключевые идеи
- Логарифмический барьер -sum ln s_i(x) заменяет ограничения штрафом, стремящимся к inf на границе
- Самосогласованность |F'''| <= 2(F'')^{3/2} гарантирует квадратичную сходимость ньютоновского шага без line search
- Параметр барьера nu: n для LP и SDP матрицы n x n; число итераций O(sqrt(nu) * ln(1/eps))
- Центральный путь {x*(t)} - аналитическая кривая, соединяющая interior с оптимумом при t -> inf
- Предиктор-корректор Меро - практическая реализация в CPLEX/Gurobi: 30-50 итераций для задач с миллионом переменных
Связи с другими областями
Interior-point методы объединяют выпуклый анализ, численную линейную алгебру и теорию сложности.
- Полуопределённое программирование (SDP) — Методы внутренней точки - стандартный решатель SDP с логарифмическим барьером
- Метод внутренней точки — Базовая глава о барьерах и self-concordant функциях
- Стохастическая оптимизация и адаптивные методы — Стохастические аналоги барьерных методов - активная область исследований
Вопросы для размышления
- Почему SDP-барьер -ln det(X) имеет параметр nu = n (а не n^2, хотя матрица n x n имеет n^2 элементов)?
- Как центральный путь связан с условиями дополняющей нежёсткости KKT исходной задачи?
- Почему предиктор-корректор Меро на практике требует вдвое меньше итераций, чем теоретически предсказывает анализ?