Learning path

Full curriculum

Full curriculum

Arrows go from each prerequisite to the units that depend on it. Hover or focus a unit to highlight its path.

Unit content

Inequality constraints and Karush-Kuhn-Tucker conditions

For inequality-constrained optimization, a constraint such as

$$g_i(x)\le0$$

may be inactive at the optimum or may be active with $g_i(x_*)=0$.

The Karush-Kuhn-Tucker conditions extend Lagrange multipliers to this setting. For

$$\min f(x)\quad\text{subject to}\quad g_i(x)\le0,$$

candidate optima satisfy, under suitable regularity conditions,

$$\nabla f(x_)+\sum_i\lambda_i\nabla g_i(x_)=0,$$

with

$$g_i(x_)\le0,\qquad \lambda_i\ge0,\qquad \lambda_i g_i(x_)=0.$$

The last equation is complementary slackness: an inactive constraint has zero multiplier, while a positive multiplier can occur only for an active constraint.

For convex problems satisfying appropriate constraint qualifications, KKT conditions can characterize global optima rather than merely local candidates.