KKT Conditions

Optimization · Axiom Academy

LESSON Karush-Kuhn-Tucker (KKT) Conditions Understanding the necessary conditions for optimality in constrained optimization problems 1. The General Constrained Problem Consider the optimization problem: We seek to minimize an objective function f(x) subject to: Equality constraints: h(x) = 0 (must be satisfied exactly) Inequality constraints: g(x) ≤ 0 (define a feasible region) 2. Stationarity: Balancing Gradients The first KKT condition requires that the gradient of the objective function equals a linear combination of constraint gradients: Geometric meaning: At an optimal point, the objective gradient must lie in the span of the constraint gradients. Any feasible direction either increases the objective or violates a constraint. 3. Primal Feasibility: Satisfying Constraints The solution must satisfy all original constraints: Geometric meaning: The optimal point must lie within the feasible region. Equality constraints define surfaces that must contain the solution, while inequality constraints define half-spaces. 4. Dual Feasibility & Complementary Slackness For inequality constraints, two additional conditions apply: Dual feasibility (μ ≥ 0): Multipliers for inequality constraints must be non-negative. Complementary slackness (μᵢgᵢ(x) = 0): Either the constraint is active (gᵢ = 0) with μᵢ > 0, or inactive (gᵢ < 0) with μᵢ = 0. A point x* is a KKT point if there exist multipliers λ and μ such that all four conditions hold simultaneously:

This is the written version of the interactive lesson above. See the full Optimization course.