KKT conditions

Parent: math · Prereq: lagrangian

Necessary conditions for an optimum x* of a constrained problem, stated on the lagrangian L(x,λ,μ).

KKT

At an optimum x* (under a constraint qualification):

• stationarity — $\nabla_x L=0$ (the objective's gradient is cancelled by the active constraints');
• primal feasibility — hᵢ=0, gⱼ≤0;
• dual feasibility — μⱼ≥0;
• complementary slackness — μⱼgⱼ=0: each inequality is either tight (gⱼ=0) or inactive (μⱼ=0).

For convex problems KKT is also sufficient (a KKT point is a global optimum). We used exactly this in the Holmström derivation.

Fully worked end-to-end (case split + shadow price + dual): kkt-worked-example.