Karush-Kuhn-Tucker conditions
/ Karush: KAR-oosh; Kuhn: koon; Tucker: TUK-er /
Lagrange multipliers handle equality constraints beautifully, but real problems also have inequalities: stay under budget, keep quantities non-negative, do not exceed capacity. The Karush-Kuhn-Tucker conditions, KKT for short, are the master set of first-order necessary conditions that an optimum of such a mixed problem must satisfy. They are the cornerstone of modern constrained optimization.
There are four ingredients. Stationarity: the gradient of the objective is balanced by a weighted sum of the constraint gradients, grad f = sum of mu_i times grad g_i plus the equality terms — just the Lagrange condition extended. Primal feasibility: the point actually obeys all the constraints. Dual feasibility: the multipliers on the inequality constraints have the right sign (non-negative for the standard set-up), because a one-sided fence can only push, never pull. And complementary slackness, the subtle one: for each inequality, either the constraint is active (tight, g = 0) or its multiplier is zero — you cannot have a slack constraint that still exerts force. Complementary slackness is exactly the algebraic statement of active-versus-inactive.
KKT is the engine behind linear and quadratic programming, support-vector machines, optimal control, and economic equilibrium models. The crucial honesty: the KKT conditions are necessary for an optimum only under a constraint qualification (some regularity of the active constraint gradients), and in general they are necessary, not sufficient — a point can satisfy KKT and still not be optimal. The grand exception is convex problems: there, if the constraints are well-behaved, KKT becomes both necessary and sufficient, and any KKT point is a global optimum. That is why convexity is so prized.
Minimize f(x) = x^2 subject to x greater than or equal to 1, written g(x) = 1 - x less than or equal to 0. KKT stationarity gives 2x - mu = 0 with mu greater than or equal to 0, and complementary slackness mu(1 - x) = 0. The constraint is active: x = 1, mu = 2, the constrained minimum.
Complementary slackness forces either a tight constraint or a zero multiplier — here the constraint is tight.
KKT points are merely candidates in a non-convex problem — necessary, not sufficient. Only for convex problems with a constraint qualification does satisfying KKT guarantee a true global optimum.