Условия Каруша–Куна–Таккера

Условия ККТ — золотой стандарт оптимальности для задач с неравенствами, обобщение Лагранжа.

Условия ККТ (Каруша–Куна–Таккера) — необходимые условия оптимума задачи с ограничениями-неравенствами $g_i(x)\le 0$: стационарность, допустимость, неотрицательность множителей и дополняющая нежёсткость.

От равенств к неравенствам

Лагранж работает с равенствами $g=0$. Но чаще ограничения — неравенства: «не больше бюджета» $g(x)\le0$, «неотрицательный объём» $x\ge0$. Тут возникает новый эффект: ограничение может быть активным (выполнено как равенство, $g=0$, «упёрлись в стену») или неактивным (с запасом, $g<0$, «стена далеко»). ККТ аккуратно описывают оба случая.

Четыре условия

Для задачи $\min f(x)$ при $g_i(x)\le0$ оптимум $x^*$ с множителями $\mu_i$ удовлетворяет:

Стационарность: $\nabla f(x^*)+\sum_i\mu_i\nabla g_i(x^*)=0$.
Допустимость: $g_i(x^*)\le0$ для всех $i$.
Неотрицательность множителей: $\mu_i\ge0$.
Дополняющая нежёсткость: $\mu_i\,g_i(x^*)=0$.

Сердце ККТ — дополняющая нежёсткость

Условие $\mu_i g_i=0$ — самое содержательное. Оно говорит: для каждого ограничения либо множитель ноль ($\mu_i=0$), либо ограничение активно ($g_i=0$). Перевод: у ограничения с запасом нулевая «цена» (оно не давит на решение); давит только активное. Это тот же принцип, что теневые цены в LP.

Пример с проверкой случаев

Минимизируем $f(x)=(x-3)^2$ при ограничении $x\le1$ (то есть $g=x-1\le0$). Безусловный минимум в $x=3$ недопустим. ККТ: либо ограничение неактивно ($\mu=0$, тогда $x=3$ — нарушает $x\le1$, отбрасываем), либо активно ($x=1$). Проверим оба сценария численно.

def f(x):
    return (x - 3) ** 2

# Сценарий A: ограничение неактивно -> безусловный минимум
x_uncon = 3.0
print("Безусловный минимум x=3 допустим? ", x_uncon <= 1, "(нарушает x<=1)")

# Сценарий B: ограничение активно -> x = 1
x_active = 1.0
# множитель из стационарности: f'(x) + mu*g'(x) = 0,  2(x-3) + mu*1 = 0
mu = -2 * (x_active - 3)
print("Активное ограничение: x*=1, f=", f(x_active))
print("Множитель mu =", mu, "(>=0? ", mu >= 0, ")")
print("Дополняющая нежёсткость mu*g =", mu * (x_active - 1))

Вывод:

Безусловный минимум x=3 допустим?  False (нарушает x<=1)
Активное ограничение: x*=1, f= 4.0
Множитель mu = 4.0 (>=0?  True )
Дополняющая нежёсткость mu*g = 0.0

Сценарий A отпал (недопустим). В сценарии B все условия ККТ выполнены: $x^*=1$, $\mu=4\ge0$, дополняющая нежёсткость $\mu\cdot g=0$. Ответ: минимум на границе $x=1$ со значением $f=4$, ограничение активно.

Когда ККТ достаточны

В общем случае ККТ — лишь необходимые условия. Но для выпуклой задачи (выпуклые $f$ и $g_i$) при выполнении условия регулярности (например, Слейтера — существует строго допустимая точка) ККТ становятся и достаточными: любая ККТ-точка глобально оптимальна. Это делает ККТ практическим инструментом проверки оптимальности в выпуклой оптимизации.

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

ККТ — фундамент всех современных солверов условной оптимизации. Методы внутренней точки решают слегка возмущённую систему ККТ (заменяя дополняющую нежёсткость $\mu_i g_i=0$ на $\mu_i g_i=-t$ и устремляя $t\to0$), двигаясь по «центральному пути» к оптимуму. Так LP, квадратичное и более общее выпуклое программирование сводятся к численному решению ККТ-системы Ньютоном.

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

Отрицательный множитель. Для $\le$-ограничений $\mu_i\ge0$; отрицательный означает, что вы перепутали знак или это не минимум.
Игнорировать дополняющую нежёсткость. Нельзя одновременно иметь $\mu_i>0$ и $g_i<0$.
Считать ККТ достаточными в невыпуклом случае. Там это лишь кандидаты в оптимум.

Итоги

ККТ обобщают Лагранжа на неравенства: стационарность + допустимость + $\mu_i\ge0$ + $\mu_i g_i=0$.
Дополняющая нежёсткость: множитель ненулевой только у активных ограничений.
Для выпуклых задач (при регулярности) ККТ необходимы и достаточны — критерий глобального оптимума.