Метод штрафных функций: оптимизация с ограничениями

Большинство реальных задач оптимизации формулируется с ограничениями: минимизировать расход материала, но не выйти за пределы прочности; максимизировать прибыль, но уложиться в бюджет. Прямые методы безусловной минимизации (градиентный спуск, метод Ньютона) такие условия учитывать не умеют. Метод штрафных функций решает эту проблему элегантно: он «вшивает» ограничения в саму целевую функцию через добавочное слагаемое-штраф, которое резко растёт при их нарушении. В результате задача с ограничениями сводится к последовательности обычных безусловных задач, для которых уже есть весь стандартный арсенал. Разберём идею, виды штрафов и типичную пошаговую схему.

В чём идея метода штрафных функций

Пусть требуется минимизировать $f(x)$ при ограничениях $g_i(x) \le 0$, $i = 1, \dots, m$ и $h_j(x) = 0$, $j = 1, \dots, p$. Метод штрафных функций строит вспомогательную функцию

$P(x, r) = f(x) + r \cdot \Phi(x),$

где $\Phi(x)$ - штрафная функция, измеряющая степень нарушения ограничений, а $r > 0$ - коэффициент штрафа. Идея в том, что $\Phi(x)$ равна нулю (или близка к нему) в допустимой области и положительна вне её. Минимизируя $P(x, r)$ как безусловную задачу, мы заставляем алгоритм «не вылезать» за границы: любое нарушение немедленно дорого обходится. Меняя $r$ по определённому правилу и решая серию безусловных задач, мы получаем последовательность точек $x(r)$, сходящуюся к решению исходной задачи с ограничениями.

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

Внешний штраф: подход извне допустимой области

Метод внешних штрафных функций (exterior penalty) допускает движение по недопустимым точкам и наказывает за выход за границы. Классическая квадратичная штрафная функция выглядит так:

$\Phi(x) = \sum_{i=1}^{m} \big(\max\{0,\, g_i(x)\}\big)^2 + \sum_{j=1}^{p} h_j(x)^2.$

Для неравенств штраф включается только при $g_i(x) > 0$ (ограничение нарушено), для равенств - при любом отклонении $h_j(x) \ne 0$. Вспомогательная задача - минимизировать $P(x, r) = f(x) + r\,\Phi(x)$ при возрастающей последовательности $r_k \to \infty$.

Чем больше $r_k$, тем сильнее штраф и тем ближе минимум $P$ к истинному решению. В пределе $r_k \to \infty$ точки $x(r_k)$ сходятся к оптимуму исходной задачи. Важная особенность: на конечных итерациях приближение лежит, как правило, вне допустимой области (ограничения слегка нарушены) - отсюда и название «внешний». Это допустимо, если небольшое нарушение ограничений в процессе расчёта не критично.

Внутренний (барьерный) штраф: движение изнутри

Метод внутренних штрафных функций, или барьерных функций (interior / barrier), наоборот, держит траекторию строго внутри допустимой области и ставит «стену» на границе. Применяется только к ограничениям-неравенствам $g_i(x) \le 0$. Две классические барьерные функции:

$B(x) = -\sum_{i=1}^{m} \frac{1}{g_i(x)} \quad \text{(обратная)}, \qquad B(x) = -\sum_{i=1}^{m} \ln\big(-g_i(x)\big) \quad \text{(логарифмическая)}.$

Вспомогательная функция здесь $P(x, r) = f(x) + r\, B(x)$, причём параметр $r > 0$ теперь убывает: $r_k \to 0$. При приближении $x$ к границе ($g_i(x) \to 0^-$) барьер $B(x) \to +\infty$, не давая точке покинуть область. По мере уменьшения $r_k$ барьер становится всё «тоньше», и минимум приближается к границе, если оптимум лежит именно там. Логарифмический барьер - основа методов внутренней точки, на которых построены современные solver-ы линейного и выпуклого программирования.

Выбор коэффициента штрафа и условия сходимости

Коэффициент штрафа нельзя ставить сразу очень большим (для внешнего) или очень малым (для барьерного): это делает вспомогательную функцию плохо обусловленной - её линии уровня вытягиваются в узкие овраги, и безусловный метод сходится медленно или «застревает». Поэтому работает итеративная схема с обновлением параметра:

• внешний штраф: $r_{k+1} = c\, r_k$, $c > 1$ (типично $c = 10$);
• барьерный штраф: $r_{k+1} = r_k / c$, $c > 1$.

На каждом шаге решается безусловная задача, а её решение $x(r_k)$ берётся стартовой точкой для следующего шага - это резко ускоряет сходимость (тёплый старт). Останов - когда нарушение ограничений (для внешнего) либо изменение точки между шагами стало меньше заданного допуска $\varepsilon$. Для выпуклых задач последовательность $x(r_k)$ гарантированно сходится к глобальному оптимуму; в невыпуклом случае - к локальному, как и у любого метода спуска.

Связь с множителями Лагранжа

Метод штрафов тесно связан с классической теорией условного экстремума. Если в задаче только равенства $h_j(x) = 0$ и взять квадратичный штраф, то условие стационарности $\nabla P(x, r) = 0$ даёт

$\nabla f(x) + \sum_{j=1}^{p} 2 r\, h_j(x)\, \nabla h_j(x) = 0,$

и величина $\lambda_j = 2 r\, h_j(x)$ в пределе $r \to \infty$ стремится к множителю Лагранжа из условий стационарности функции Лагранжа. То есть штраф неявно восстанавливает множители Лагранжа - об этой теории подробнее в статье про условный экстремум и множители Лагранжа. Развитие этой связи - метод модифицированной функции Лагранжа (augmented Lagrangian), который добавляет штраф к лагранжиану и не требует устремлять $r$ к бесконечности, избегая плохой обусловленности.

Пошаговая схема решения

Для задачи $\min f(x)$ при $g_i(x) \le 0$ методом внешних штрафов:

1. Задать стартовую точку $x_0$, начальный коэффициент $r_0$ (например $r_0 = 1$), множитель $c = 10$ и допуск $\varepsilon$.
2. Сформировать $P(x, r_k) = f(x) + r_k \sum_i (\max\{0, g_i(x)\})^2$.
3. Решить безусловную задачу $\min_x P(x, r_k)$ любым подходящим методом (градиентный спуск, Ньютон), стартуя с $x_{k-1}$; получить $x_k$.
4. Проверить останов: если суммарное нарушение ограничений $< \varepsilon$ - стоп, $x_k$ - приближённое решение.
5. Иначе увеличить штраф $r_{k+1} = c\, r_k$, перейти к шагу 2.

Для барьерного метода схема та же, но $x_0$ обязана быть строго внутри допустимой области, а $r$ на шаге 5 уменьшается: $r_{k+1} = r_k / c$.

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

• Сразу берут огромный $r$. Вспомогательная функция становится крайне плохо обусловленной, и безусловный метод не сходится. Нужно наращивать $r$ постепенно, переиспользуя предыдущую точку.
• Барьерный метод стартуют из недопустимой точки. Логарифм или дробь от $g_i(x) \ge 0$ не определены - алгоритм сразу падает. Для барьеров стартовая точка обязана быть строго внутри области.
• Путают направление изменения параметра. Для внешнего штрафа $r$ растёт, для барьерного - убывает. Перепутав, получают расходимость.
• Забывают про $\max\{0, g_i(x)\}$. Если в штраф для неравенства подставить просто $g_i(x)^2$, метод начнёт «наказывать» и за нахождение глубоко внутри допустимой области, искажая решение.
• Ожидают точного попадания в допустимую область. У внешнего метода приближение почти всегда чуть нарушает ограничения - это нормально, контролируется допуском $\varepsilon$.

FAQ

Чем внешний штраф отличается от внутреннего? Внешний (квадратичный) допускает недопустимые точки и наказывает за выход за границу, коэффициент $r$ растёт к бесконечности. Внутренний (барьерный) держит траекторию строго внутри области, ставя бесконечную «стену» на границе, коэффициент $r$ убывает к нулю. Барьерный работает только с неравенствами.

Гарантирует ли метод глобальный минимум? Только для выпуклых задач (выпуклая $f$ и выпуклая допустимая область). В невыпуклом случае метод штрафов, как любой метод спуска, находит локальный оптимум, зависящий от стартовой точки.

Зачем нужен метод модифицированной функции Лагранжа, если есть штрафы? Чистый штраф требует $r \to \infty$, что порождает плохую обусловленность. Augmented Lagrangian добавляет к штрафу слагаемое с оценками множителей Лагранжа и сходится при конечных $r$, поэтому численно устойчивее.

Коротко

Метод штрафных функций превращает задачу оптимизации с ограничениями в последовательность безусловных задач, добавляя к цели штрафное слагаемое $r\,\Phi(x)$. Внешний (квадратичный) штраф наказывает за нарушение ограничений и требует роста $r \to \infty$; внутренний (барьерный, логарифмический) удерживает точку внутри допустимой области при $r \to 0$. Коэффициент штрафа меняют постепенно, переиспользуя предыдущее решение как тёплый старт, а сама конструкция в пределе восстанавливает множители Лагранжа, связывая метод с классической теорией условного экстремума.