KKT Conditions
The Karush-Kuhn-Tucker conditions generalize Lagrange multipliers to inequality constraints, characterizing constrained optima.
The four conditions
For minimizing f(x) subject to inequalities g_i(x) <= 0 and equalities h_j(x) = 0, a point x* with multipliers mu_i, nu_j is a KKT point if it satisfies: stationarity, primal feasibility, dual feasibility, and complementary slackness. These conditions are necessary for optimality under a constraint qualification and sufficient when the problem is convex.
Written out
- Stationarity: grad f + sum mu_i grad g_i + sum nu_j grad h_j = 0.
- Primal feasibility: g_i(x*) <= 0 and h_j(x*) = 0.
- Dual feasibility: mu_i >= 0 (inequality multipliers are nonnegative).
- Complementary slackness: mu_i * g_i(x*) = 0 for each i.
Complementary slackness
The condition mu_i * g_i = 0 says that for each inequality constraint, either the constraint is active (g_i = 0, tight) with a possibly positive multiplier, or it is inactive (g_i < 0, slack) with multiplier zero. Inactive constraints do not influence the local optimum, so their multipliers vanish.
Constraint qualifications
The KKT conditions are necessary only when a constraint qualification holds, ensuring the constraint gradients behave well. Common ones are linear independence of active constraint gradients (LICQ) and the Slater condition (a strictly feasible point exists) for convex problems. Without a qualification, an optimum may fail KKT.
Role in algorithms
Nearly all constrained solvers, including interior-point and sequential quadratic programming methods, are engines for driving the KKT residual to zero. For convex problems, finding a KKT point is equivalent to finding the global optimum, which is why these conditions are the practical target.
# KKT residual to minimize:
# ||grad_f + G^T mu + H^T nu|| + ||h|| + ||max(g,0)|| + ||mu*g|| , mu >= 0KKT conditions define what an optimal, constraint-respecting design looks like and give solvers a precise convergence criterion.