Условия Каруша-Куна-Таккера (ККТ) в нелинейном программировании: теория и экономический смысл

Сформулируем математическую модель: минимизировать $f(x)$ при условиях $g_i(x) \le 0$ (неравенства) и $h_j(x) = 0$ (равенства). Условия ККТ состоят из четырех фундаментальных блоков. 1) Стационарность градиента Лагранжиана: $\nabla f(x^*) + \sum \lambda_i \nabla g_i(x^*) + \sum \mu_j \nabla h_j(x^*) = 0$. Это означает, что в точке оптимума $x^*$ градиент целевой функции лежит в конусе, образованном нормалями к поверхностям активных ограничений. 2) Прямая допустимость: $g_i(x^*) \le 0$ и $h_j(x^*) = 0$. 3) Двойственная допустимость (неотрицательность множителей для неравенств): $\lambda_i \ge 0$. 4) Самое интеллектуальное условие — Дополняющая нежесткость (Complementary Slackness): $\lambda_i g_i(x^*) = 0$ для всех $i$.

Условие дополняющей нежесткости является математическим шедевром. Оно гласит: если ограничение-неравенство в точке оптимума является строгим ($g_i(x^*) < 0$), то есть точка лежит строго внутри допустимой области и ограничение "не мешает" оптимизации, то соответствующий множитель $\lambda_i$ обязан быть равен нулю. Если же ограничение "активно", то есть точка лежит прямо на границе ($g_i(x^*) = 0$), то множитель $\lambda_i$ может быть строго положителен. Это условие позволяет алгоритмам динамически "выключать" нерелевантные ограничения, концентрируя вычислительную мощь только на тех барьерах, которые реально ограничивают рост функции.

Для того чтобы условия ККТ были необходимыми условиями локального минимума, задача должна удовлетворять условиям регулярности (Constraint Qualifications, CQ). Самым известным из них является условие Слейтера: если целевая функция и ограничения-неравенства выпуклы, ограничения-равенства аффинны, и существует хотя бы одна точка строго внутри допустимой области ($g_i(x) < 0$), то условия ККТ являются не только необходимыми, но и достаточными для глобального оптимума. В этом случае задача полностью и строго решается через систему ККТ.

Экономический смысл условий ККТ имеет колоссальное значение для бизнес-планирования. Множители $\lambda_i$ (двойственные переменные) — это объективно обусловленные оценки Канторовича, или "теневые цены" (Shadow Prices). Величина $\lambda_i$ точно показывает, на сколько единиц улучшится (уменьшится) значение функции $f(x^*)$, если мы ослабим ограничение $i$ на одну единицу. Если ресурс не исчерпан (неактивное ограничение), его теневая цена $\lambda = 0$ — нет смысла платить за дополнительную единицу того, что и так в избытке. Если ресурс исчерпан, $\lambda > 0$ показывает точную маржинальную стоимость этого ресурса, сигнализируя топ-менеджменту о том, куда именно выгодно инвестировать средства для расширения производственных мощностей.

Список литературы:
1. Kuhn H.W., Tucker A.W. Nonlinear programming. — Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, 1951.
2. Boyd S., Vandenberghe L. Convex Optimization. — Cambridge University Press, 2004.
3. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. — М.: Мир, 1982.