Методы штрафных и барьерных функций: алгоритмы внутренней точки в нелинейной оптимизации

Основная идея метода внешних штрафных функций заключается в том, чтобы убрать математические ограничения из задачи, но добавить к самой целевой функции специальные слагаемые — штрафы. Пока алгоритм ищет минимум и находится внутри разрешенной зоны, штраф тождественно равен нулю. Но как только итерационный процесс пересекает границу и выходит в недопустимую область, штрафная функция начинает стремительно расти (чаще всего квадратично, пропорционально квадрату нарушения ограничения). Алгоритм безусловной оптимизации, стремясь минимизировать общую сумму, чувствует эту «резиновую стену» и отталкивается обратно. Итеративно увеличивая коэффициент жесткости штрафа (стремясь к бесконечности), математики заставляют решение всё точнее прижиматься к истинной границе допустимой области снаружи.

В отличие от внешних штрафов, метод барьерных функций (метод внутренних точек) работает исключительно внутри допустимой области. Ограничения также переносятся в целевую функцию, но в виде математических барьеров. Классическим примером является логарифмический барьер: если переменная x должна быть больше нуля, в функцию добавляется слагаемое минус логарифм x (или обратная функция 1/x). Пока точка находится глубоко внутри области, барьер мал. Но по мере приближения к границе (x стремится к нулю), значение логарифма устремляется к минус бесконечности, создавая непреодолимую виртуальную гору, которая отпугивает градиентный алгоритм. Плавно уменьшая весовой коэффициент барьера (стремясь к нулю), алгоритм шаг за шагом подбирается к границе изнутри.

Долгое время барьерные методы считались теоретически изящными, но вычислительно неустойчивыми (матрицы Гессе становились плохо обусловленными при приближении к границам). Однако в 1984 году математик Нарендра Кармаркар совершил абсолютную революцию, опубликовав свой проективный алгоритм внутренней точки для линейного программирования. Он доказал, что движение сквозь внутреннюю часть многогранника (сквозь барьеры), а не по его ребрам (как это делал симплекс-метод), позволяет решать задачи с полиномиальной временной сложностью. Это открытие вызвало настоящий шок в научном сообществе и привело к бурному ренессансу барьерных функций в форме прямых-двойственных алгоритмов внутренней точки (Primal-Dual Interior Point Methods).

Современные прямые-двойственные алгоритмы опираются на модификацию условий Каруша-Куна-Таккера (KKT). Центральное уравнение ККТ — условие дополняющей нежесткости (произведение переменной на ее двойственную оценку равно нулю) — возмущается добавлением небольшого барьерного параметра мю. Полученная сглаженная система нелинейных уравнений решается с помощью итерационного метода Ньютона. По мере сходимости алгоритма параметр мю плавно устремляется к нулю, и центральная траектория безошибочно выводит решение прямо к глобальному оптимуму. Сегодня алгоритмы внутренней точки встроены во все коммерческие решатели (CPLEX, Gurobi) и способны за доли секунды оптимизировать энергетические и финансовые сети с миллионами ограничений, недоступными для классического симплекс-метода.