KKT Conditions
What you'll learn: How the Karush-Kuhn-Tucker (KKT) conditions extend optimality conditions to constrained problems with inequalities.
The Core Idea
You've learned about Lagrange multipliers for equality-constrained optimization. But what if your constraints are inequalities (like "x ≥ 0" or "budget ≤ 100")? The KKT conditions provide the necessary conditions for optimality when your problem includes inequality constraints.
Think of it this way: if you're hiking and want to reach the highest point but must stay within park boundaries (inequalities), you'll either:
- Be at a peak inside the boundary (constraint inactive), or
- Be pressed against a boundary fence at the highest point along it (constraint active)
The KKT conditions mathematically capture both scenarios.
The Mathematical Framework
For a problem minimizing f(x) subject to:
- Equality constraints: h(x) = 0
- Inequality constraints: g(x) ≤ 0
At an optimal point x*, the KKT conditions require:
- Stationarity: ∇f(x*) + λ∇h(x*) + μ∇g(x*) = 0 (gradient of Lagrangian = 0)
- Primal feasibility: h(x*) = 0 and g(x*) ≤ 0 (constraints satisfied)
- Dual feasibility: μ ≥ 0 (multipliers for inequalities non-negative)
- Complementary slackness: μ · g(x*) = 0 (either constraint is active OR multiplier is zero)
Complementary slackness is key: if you're not touching a boundary (g(x*) < 0), that constraint doesn't influence your solution (μ = 0).
Why This Matters
KKT conditions underpin support vector machines (SVMs), where finding the maximum-margin hyperplane becomes a constrained optimization problem. They're the foundation for understanding why only certain data points (support vectors) matter.
Key Takeaway: The KKT conditions generalize optimality conditions to inequality constraints, ensuring a point is optimal only if gradients balance correctly and inactive constraints have zero influence.