Course contentsShow
← Machine Learning and Deep Learning
Lesson 111 of 3,5381. Mathematical Foundations for Machine LearningFree lesson

KKT Conditions

Karush-Kuhn-Tucker conditions for optimality in problems with inequality constraints.

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:

  1. Be at a peak inside the boundary (constraint inactive), or
  2. 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:

  1. Stationarity: ∇f(x*) + λ∇h(x*) + μ∇g(x*) = 0 (gradient of Lagrangian = 0)
  2. Primal feasibility: h(x*) = 0 and g(x*) ≤ 0 (constraints satisfied)
  3. Dual feasibility: μ ≥ 0 (multipliers for inequalities non-negative)
  4. 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.