Штрафные функции

Штрафные функции превращают задачу с ограничениями в обычную, добавляя к цели большой штраф за нарушение.

Метод штрафных функций заменяет условную задачу безусловной $\min f(x)+\rho\,P(x)$, где $P(x)\ge0$ растёт при нарушении ограничений, а $\rho$ — вес штрафа.

Идея: запретить нарушения «деньгами»

У нас уже есть мощные безусловные методы (градиентный спуск, Ньютон). Хочется применить их к задачам с ограничениями. Штрафной подход прост: добавим к цели слагаемое, которое равно нулю в допустимой области и быстро растёт при выходе из неё. Тогда минимизатор «не захочет» нарушать ограничения, и безусловный метод сам останется внутри.

Квадратичный штраф

Для ограничения-равенства $g(x)=0$ берут

$$P(x)=g(x)^2,\qquad F_\rho(x)=f(x)+\rho\,g(x)^2.$$

Для неравенства $g(x)\le0$ — односторонний штраф $P(x)=\max(0,g(x))^2$: ноль, пока ограничение выполнено, и квадрат превышения, когда нарушено. Чем больше $\rho$, тем строже запрет.

Реализация

Решим: $\min f(x,y)=x^2+y^2$ при ограничении $x+y=2$ (минимум квадрата расстояния до начала на прямой; ответ — $x=y=1$, $f=2$). Штрафная задача: $F_\rho=x^2+y^2+\rho(x+y-2)^2$, минимизируем градиентным спуском при растущем $\rho$.

def grad_F(x, y, rho):
    c = x + y - 2
    gx = 2 * x + 2 * rho * c
    gy = 2 * y + 2 * rho * c
    return gx, gy

def minimize(rho, steps=4000):
    x, y = 0.0, 0.0
    alpha = 0.4 / (1 + 2 * rho)        # шаг адаптируем под жёсткость штрафа
    for _ in range(steps):
        gx, gy = grad_F(x, y, rho)
        x -= alpha * gx
        y -= alpha * gy
    return x, y

for rho in [1, 10, 100, 1000]:
    x, y = minimize(rho)
    viol = abs(x + y - 2)
    print(f"rho={rho:5d}: x={x:.4f} y={y:.4f} нарушение|x+y-2|={viol:.4f}")

Вывод:

rho=    1: x=0.6667 y=0.6667 нарушение|x+y-2|=0.6667
rho=   10: x=0.9524 y=0.9524 нарушение|x+y-2|=0.0952
rho=  100: x=0.9950 y=0.9950 нарушение|x+y-2|=0.0100
rho= 1000: x=0.9995 y=0.9995 нарушение|x+y-2|=0.0010

При малом $\rho$ решение «срезает угол», нарушая ограничение ради уменьшения $f$. По мере роста $\rho$ нарушение тает, и решение сходится к точному $x=y=1$. Это типичная схема: решать последовательность задач с растущим $\rho$, стартуя каждую из решения предыдущей.

Внешние и внутренние штрафы

Тип	Идея	Где минимум
Внешний штраф	$\rho\max(0,g)^2$ — штраф снаружи	Подходит к границе снаружи
Барьерный (внутренний)	$-\dfrac{1}{\rho}\ln(-g)$ — стена изнутри	Держится строго внутри

Барьерные функции (логарифмический барьер) не пускают к границе вовсе, создавая бесконечную «стену» при $g\to0$. На них построены методы внутренней точки — те самые, что решают возмущённую систему ККТ.

Как работает под капотом

У чистого штрафа есть подвох: точное удовлетворение ограничения требует $\rho\to\infty$, а это делает задачу плохо обусловленной (овраг становится экстремальным, спуск буксует). Лекарство — метод расширенного Лагранжиана (ALM): к штрафу добавляют лагранжев член $-\lambda g(x)$ и обновляют $\lambda$ между итерациями. Тогда точное решение достигается при конечном $\rho$, без катастрофической обусловленности. Это стандарт для серьёзных условных солверов.

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

Сразу взять огромный $\rho$. Задача станет плохо обусловленной; наращивайте $\rho$ постепенно.
Двусторонний штраф для неравенства. Для $g\le0$ штрафовать надо только превышение $\max(0,g)$, а не сам $g$.
Ждать точного нуля нарушения при конечном $\rho$. Чистый штраф даёт лишь приближение; для точности нужен расширенный Лагранжиан.

Итоги

Штраф превращает условную задачу в безусловную: $\min f+\rho P$, $P$ карает нарушения.
Решают последовательность задач с растущим $\rho$; нарушение уменьшается как $\sim1/\rho$.
Большой $\rho$ портит обусловленность — лучше расширенный Лагранжиан (точность при конечном $\rho$).