TheoremProved

Karush–Kuhn–Tucker conditions

Statement

For the problem $\min f(x)$ subject to $g_i(x) \le 0\ (i=1,\dots,m)$ and $h_j(x)=0\ (j=1,\dots,p)$ , with $f, g_i, h_j$ differentiable, if $x^*$ is a local minimum satisfying a constraint qualification, then there exist multipliers $\mu_i \ge 0$ , $\lambda_j$ such that: (stationarity) $\nabla f(x^*) + \sum_i \mu_i \nabla g_i(x^*) + \sum_j \lambda_j \nabla h_j(x^*) = 0$ ; (primal feasibility) $g_i(x^*)\le 0,\ h_j(x^*)=0$ ; (dual feasibility) $\mu_i \ge 0$ ; (complementary slackness) $\mu_i g_i(x^*) = 0$ for every $i$ . For convex problems these conditions are also sufficient for global optimality.

Why is it true?

At a constrained optimum you cannot improve the objective by any small feasible move. Stationarity says the gradient of $f$ is exactly cancelled by a nonnegative combination of the active constraints' gradients — you are 'pinned' against the boundary of the feasible region by forces (multipliers) that only push inward. Complementary slackness says a constraint only exerts force ( $\mu_i>0$ ) when it is actually active ( $g_i(x^*)=0$ ); slack constraints contribute nothing.

Proof sketch

Under a constraint qualification (e.g. linear independence of active constraint gradients, or Slater's condition for convex problems), the set of feasible directions at $x^*$ coincides with the linearized cone of the active constraints. Since $x^*$ is a local minimum, $\nabla f(x^*)$ cannot have negative inner product with any feasible direction, so $-\nabla f(x^*)$ lies in the cone generated by the active constraints' gradients — this is exactly Farkas' lemma applied to the linearized system, giving the multipliers $\mu_i, \lambda_j$ .

Topics that use this theorem

Convex optimization

Related theorems

Strong duality in linear programming Local minima of convex functions are global

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Stephen Boyd, Lieven Vandenberghe (2004). Convex Optimization
Mokhtar S. Bazaraa, Hanif D. Sherali, C. M. Shetty (2006). Nonlinear Programming: Theory and Algorithms