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

Метод внутренней точки решает задачи оптимизации, двигаясь не по границе допустимой области, как симплекс-метод, а сквозь её внутренность. Идея простая: к целевой функции добавляют барьер, который уходит в бесконечность у каждого ограничения и тем самым удерживает решение строго внутри. Постепенно ослабляя этот барьер, мы спускаемся по плавной кривой - центральному пути - прямо к оптимуму. Ниже разберём, как строится логарифмический барьер, что такое центральный путь и параметр $\mu$, как $\mu$ связан с зазором двойственности и за сколько шагов метод сходится. Чтобы сразу увидеть связь барьера, пути и зазора, покрути калькулятор: он показывает барьерную функцию, центральный путь и геометрическое убывание зазора одновременно, а дальше мы выведем каждую формулу строго.

Зачем нужна внутренняя точка

Классический симплекс-метод идёт по вершинам многогранника допустимых решений: он перебирает угловые точки, пока не упрётся в оптимум. На практике это работает быстро, но в худшем случае число вершин растёт экспоненциально, и алгоритм может застрять. Метод внутренней точки устроен иначе: он стартует из точки строго внутри допустимой области и движется к оптимуму по гладкой траектории, ни разу не касаясь границы до самого конца. Для задач линейного программирования это даёт полиномиальную оценку сложности, а для выпуклых нелинейных задач - единый и устойчивый аппарат.

Рассчитать для своей задачи

Ключевое слово здесь - внутренняя. Решение всё время остаётся допустимым с запасом, а не балансирует на ребре. Это и делает метод численно устойчивым: нет резких переключений между активными ограничениями, как у симплекса.

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

Рассмотрим простейшую модель, на которой видна вся механика: минимизировать $c\,x$ при ограничениях $a \le x \le b$. Чтобы запретить выход за границы, заменим жёсткие ограничения штрафом, который растёт без предела при приближении к стенке. Самый удобный такой штраф - логарифмический барьер:

$B(x, \mu) = c\,x - \mu\ln(x - a) - \mu\ln(b - x).$

Когда $x$ приближается к $a$ или к $b$, соответствующий логарифм уходит в $-\infty$, а из-за знака минус сам барьер - в $+\infty$. Поэтому минимум $B(x, \mu)$ всегда лежит строго внутри интервала $(a, b)$: барьер физически не пускает решение на границу. Параметр $\mu > 0$ задаёт силу барьера: при большом $\mu$ штраф мощный и тянет точку к центру, при малом - почти не мешает, и решение прижимается к настоящему оптимуму.

Рассчитать для своей задачи

Минимум барьерной функции найти легко: приравняем производную к нулю.

$B'(x) = c - \frac{\mu}{x - a} + \frac{\mu}{b - x} = 0.$

Это уравнение сводится к квадратному относительно $x$, и его корень, лежащий внутри $(a, b)$, и есть искомая внутренняя точка $x^*(\mu)$. Поскольку оба логарифма выпуклы, $B(x, \mu)$ строго выпукла, значит минимум единственный - ровно та точка, которую отмечает калькулятор выше.

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

Если решать задачу минимизации $B(x, \mu)$ для каждого значения $\mu$, точки $x^*(\mu)$ выстраиваются в гладкую кривую. Эта кривая называется центральным путём:

$x^*(\mu) = \arg\min_x \; B(x, \mu).$

При больших $\mu$ путь стартует около аналитического центра области (точки, равноудалённой от ограничений в смысле барьера), а при $\mu \to 0$ он сходится к оптимуму исходной задачи. Идея алгоритма в том, чтобы не решать задачу сразу при $\mu = 0$ - там барьер вырождается, - а идти вдоль пути: взять умеренное $\mu$, найти $x^*(\mu)$ методом Ньютона, уменьшить $\mu$ и повторить, стартуя из предыдущей точки. Каждый шаг короткий, потому что соседние точки пути близки.

Рассчитать для своей задачи

Именно из-за этого метод и называют методом следования за центральным путём. На графике пути в калькуляторе хорошо видно: кривая ровная, без изломов, и при $\mu \to 0$ упирается в горизонталь оптимума. Чем меньше $\mu$, тем ближе текущая точка к ответу.

Параметр mu и зазор двойственности

Параметр $\mu$ - это не просто настройка силы барьера, он имеет точный смысл. Для задачи с $m$ ограничениями-неравенствами выполняется фундаментальное соотношение: на центральном пути зазор двойственности (разность между значениями прямой и двойственной задач) равен

$\text{gap} = m\,\mu.$

В нашей модели два ограничения ($x \ge a$ и $x \le b$), поэтому зазор равен $2\mu$. Это даёт честный критерий остановки: мы не гадаем, близко ли решение, а точно знаем - текущая точка отличается от оптимума по значению не более чем на $m\mu$. Хотим точность $\varepsilon$ - доводим $\mu$ до $\varepsilon / m$. Поэтому метод внутренней точки самосертифицирующийся: вместе с приближённым решением он выдаёт гарантию его качества.

Рассчитать для своей задачи

Шаг метода и сходимость

Алгоритм в чистом виде укладывается в короткий цикл. Выбираем стартовое $\mu_0$ и коэффициент уменьшения $\sigma \in (0, 1)$, например $\sigma = 0{,}5$. На каждой итерации:

1. при текущем $\mu$ делаем один-два шага Ньютона по $x$, приближая $x^*(\mu)$;
2. уменьшаем барьер: $\mu_{k+1} = \sigma\,\mu_k$;
3. проверяем зазор $m\mu_{k+1}$: если он меньше требуемой точности - стоп.

Поскольку $\mu$ убывает геометрически, зазор тоже падает геометрически: $\text{gap}_k = m\,\mu_0\,\sigma^k$. Чтобы довести зазор от стартового до $\varepsilon$, нужно порядка $\log(\varepsilon / \text{gap}_0) / \log\sigma$ итераций - это десятки шагов даже для очень высокой точности. Калькулятор сверху сразу показывает это число для текущих настроек: сдвиньте $\mu$ и посмотрите, как меняется счётчик шагов до $10^{-4}$.

Шаг Ньютона для одномерного барьера выглядит так: $x_{k+1} = x_k - B'(x_k) / B''(x_k)$, где вторая производная $B''(x) = \mu/(x-a)^2 + \mu/(b-x)^2$ всегда положительна, что и гарантирует движение к минимуму. В многомерном случае вместо деления на $B''$ решают линейную систему с гессианом, но логика та же.

Частые ошибки

• Сразу брать $\mu = 0$. При нулевом барьере функция вырождается, а метод Ньютона расходится. Барьер уменьшают постепенно, идя вдоль центрального пути, а не отключают разом.
• Стартовать с границы. Начальная точка обязана быть строго внутренней: при $x = a$ или $x = b$ логарифм не определён. Нужна допустимая точка с запасом по всем ограничениям.
• Путать барьер и штраф. Штрафная функция допускает выход за границу и наказывает за это; барьер не пускает наружу в принципе. Это разные методы, и барьерный требует строго внутренней точки.
• Игнорировать смысл $\mu$. $\mu$ - это не абстрактный темп, а зазор двойственности, делённый на число ограничений. Критерий остановки задают через зазор $m\mu$, а не на глаз.
• Слишком резко снижать $\mu$. Если умножать $\mu$ на очень малый коэффициент, новая точка оказывается далеко от пути и Ньютон может не сойтись за пару шагов. Баланс между числом внешних итераций и сложностью внутренних задаёт $\sigma$.

FAQ

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

Что такое центральный путь простыми словами? Это кривая, которую заметают минимумы барьерной функции при разных $\mu$. Каждая её точка - компромисс между минимизацией цели и удержанием решения подальше от границ. При $\mu \to 0$ компромисс смещается в сторону цели, и путь приходит точно в оптимум.

Почему параметр $\mu$ равен зазору двойственности? На центральном пути условия дополняющей нежёсткости выполняются не точно, а с зазором $\mu$ на каждое ограничение. Сумма этих зазоров и есть разность прямой и двойственной целевых функций, то есть зазор двойственности $m\mu$. Это даёт встроенную гарантию точности решения.

Коротко

Метод внутренней точки заменяет жёсткие ограничения логарифмическим барьером $B(x,\mu) = c\,x - \mu\ln(x-a) - \mu\ln(b-x)$ и движется к оптимуму по центральному пути - кривой минимумов $x^*(\mu)$. Параметр $\mu$ задаёт силу барьера и одновременно равен зазору двойственности, делённому на число ограничений, поэтому при $\mu \to 0$ внутренняя точка сходится к оптимуму, а зазор $m\mu$ служит точным критерием остановки. Геометрическое уменьшение $\mu$ даёт сходимость за десятки шагов и встроенную гарантию качества решения.