Метод внутренней точки и барьерные функции

Метод внутренней точки и барьерные функции

Идея: как обойти ограничения?

Задача с ограничениями: min f(x) при gᵢ(x) ≤ 0. Один из подходов — «забыть» про ограничения, но добавить большой штраф за их нарушение. Логарифмический барьер делает это изящно: он уходит в +∞ при приближении x к границе допустимого множества. Метод внутренней точки (МВТ) систематически использует этот барьер, постепенно «уменьшая» его влияние, пока не получит точное решение. Теоретическая сложность МВТ — полиномиальная, и это первый полиномиальный алгоритм для линейного программирования (Хачиян, 1979; Кармаркар, 1984).

Логарифмический барьер

Для задачи min f(x) при gᵢ(x) ≤ 0 вводим логарифмический барьер:

φ(x) = − Σᵢ log(−gᵢ(x))

Смысл: когда gᵢ(x) → 0 (приближаемся к границе ограничения), −gᵢ(x) → 0⁺ → log → −∞ → φ(x) → +∞. Барьер «отталкивает» от границы.

При gᵢ(x) = −t (x строго внутри, зазор = t): φ(x) = − log t. При удвоении зазора барьер уменьшается на log 2.

Барьерная задача: min f(x) + (1/t) φ(x)

Параметр t > 0 — «точность». При t → ∞ барьерный член (1/t)φ(x) → 0, и решение сходится к оригинальному.

Центральный путь

Для каждого t > 0 существует единственное решение барьерной задачи x*(t) — это центральный путь задачи.

Условие оптимальности барьерной задачи (условие ККТ без ограничений):

∇f(x*(t)) + (1/t) Σᵢ (1/(−gᵢ(x*(t)))) ∇gᵢ(x*(t)) = 0

Если обозначить λᵢ*(t) = 1/(−t gᵢ(x*(t))), то это в точности условие стационарности ККТ оригинальной задачи! Центральный путь — это «смягчённые» ККТ-условия.

Зазор двойственности на центральном пути: f(x*(t)) − d* = m/t, где m — число ограничений. Точность ε достигается при t = m/ε.

Алгоритм МВТ

1. Начать с t = t₀, x⁰ строго внутри (gᵢ(x⁰) < 0)
2. Решить барьерную задачу методом Ньютона: x^+ = x − (∇²L)⁻¹ ∇L (несколько ньютоновских шагов)
3. Увеличить t: t ← μt (μ > 1, обычно μ = 10−20)
4. Повторить до точности ε

Сложность: O(√m) итераций «внешнего» цикла, каждая — один шаг Ньютона O(n³) (инвертирование матрицы). Итого: O(√m · n³).

Для LP: O(√n log(1/ε)) итераций — полиномиально!

Самодвойственные барьеры

Барьер φ называется ν-самодвойственным (ν-self-concordant) если выполнено:

|D³φ(x)[h,h,h]| ≤ 2(D²φ(x)[h,h])^{3/2}

Это «условие согласованности»: третья производная контролируется второй. При таком условии метод Ньютона имеет особые гарантии сходимости.

Параметры самодвойственности:

• Для ЛП: φ(x) = −Σ log xᵢ, ν = n (ограничения x ≥ 0)
• Для SDP: φ(X) = −log det X, ν = n (матрица n×n)
• Для SOCP: φ = −log(t² − ‖x‖²), ν = 2

Число ньютоновских шагов: O(√ν log(1/ε)). Чем меньше ν, тем быстрее МВТ.

Полный разбор: ЛП через МВТ

Задача: min cᵀx при Ax = b, x ≥ 0 (стандартная форма ЛП).

Барьерная задача: min cᵀx − (1/t) Σᵢ log xᵢ при Ax = b.

Условия ККТ: c − (1/t)X⁻¹e + Aᵀλ = 0, Ax = b. Здесь X = diag(x).

Шаг Ньютона: Решаем линейную систему: [X⁻² Aᵀ] [Δx] [c + Aᵀλ − (1/t)X⁻¹e] [A 0 ] [Δλ] = [0]

Размер системы (n+m)×(n+m). При структурированной A — можно решить за O(n · m²) (если m << n).

Пример: транспортная задача 100×100 (10000 переменных): МВТ решает за ~50 итераций (~50 систем линейных уравнений), симплекс-метод — за ~10000 итераций по вершинам.

Применения

МВТ используется как основа большинства промышленных решателей (MOSEK, Gurobi, CPLEX). Для больших LP — предпочтительнее симплекса (меньше итераций). Для SDP — единственная практически используемая парадигма. В теории управления МВТ решает LMI-задачи синтеза регуляторов H∞ и задачи устойчивости по Ляпунову.

Алгоритмическая реализация

На практике метод внутренней точки требует тщательной реализации:

1. Стартовая точка: должна лежать строго внутри допустимого множества. Часто используется фаза I — отдельная задача для нахождения такой точки.
2. Линейный поиск: после вычисления Ньютоновского направления делается шаг с обратным трекингом, чтобы оставаться внутри.
3. Обновление барьерного параметра: t ← μt с μ ≈ 10. Слишком большое μ ускоряет, но дестабилизирует; слишком маленькое — замедляет.
4. Критерий остановки: по двойственному зазору — гарантированному расстоянию от оптимума.

Современные пакеты

Метод внутренней точки реализован в промышленных решателях: MOSEK, Gurobi (для QP/SOCP), CVXOPT, IPOPT (для нелинейных задач). Для семидефинитного программирования (SDP) используются специализированные версии: SDPT3, SeDuMi, COSMO. В машинном обучении SDP применяется для метрического обучения, релаксаций кластеризации, управления роботами с ограничениями устойчивости. Метод внутренней точки выигрывает у симплекс-метода на больших разреженных задачах, особенно когда количество ограничений сравнимо с количеством переменных.