The KKT Conditions

Lagrange multipliers meet complementary slackness: four conditions that certify an optimum.

The idea

The Karush-Kuhn-Tucker conditions characterize the solutions of a differentiable convex optimization problem. Take a problem with objective $f_{0}$, inequality constraints $f_{i}(x) \le 0$ and equality constraints $h_{j}(x) = 0$.

Definition (KKT conditions).

A point $x$ together with multipliers $\lambda$ and $\nu$ satisfies the KKT conditions when four things hold at once: $x$ is feasible; every $\lambda_{i} \ge 0$; every product $\lambda_{i} f_{i}(x) = 0$; and $\nabla f_{0}(x) + \sum_{i} \lambda_{i} \nabla f_{i}(x) + \sum_{j} \nu_{j} \nabla h_{j}(x) = 0.$

Theorem (KKT conditions for convex problems).

If every $f_{i}$ is convex and every $h_{j}$ is affine, then any point that satisfies the KKT conditions with some multipliers is optimal. If in addition Slater's condition holds, every optimal point satisfies the KKT conditions with some multipliers.

For a convex problem the conditions are therefore a complete recipe for solving it: write them down and solve them.

Two of the four are already familiar. In Lagrange Multipliers an equality constraint gave the last condition, that at an optimum the objective's gradient is a combination of the constraint gradients. In Complementary Slackness a linear program gave the third, that a constraint with slack carries a zero multiplier.

What the inequality constraints add is the sign restriction $\lambda_{i} \ge 0$, and the sign carries the geometric content. An equality constraint pins a point to a surface and can push it off that surface in either direction, so its multiplier is free in sign; an inequality constraint can only push inward, away from its own boundary, and a multiplier of the wrong sign would describe a push the constraint cannot deliver.

Ways to work on it

• Walkthrough. State the four conditions, let complementary slackness split the problem into cases, and solve one end to end.
• Proof. Complementary slackness derived from a zero gap, and why KKT is sufficient for a convex problem with no constraint qualification.
• Practice. Test candidate points against the KKT conditions on a small quadratic program.
• Hardest. Turn a power-allocation problem into an algorithm by solving the KKT equations directly.

Not sure where to start? Take the ten-question placement test.