Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 38 · Duality and KKT Conditions

The KKT Conditions

Learn the four Karush-Kuhn-Tucker conditions, why they are necessary and sufficient for convex problems, and write a checker that verifies a candidate solution.

How do you know a point is the answer to a constrained problem? For an unconstrained smooth convex function, the test is ∇f(x) = 0. With constraints, the test gets a few more parts. Together they are called the Karush-Kuhn-Tucker (KKT) conditions. For convex problems that satisfy Slater's condition, they are exactly the conditions for optimality: a point passes them if and only if it is optimal.

This lesson states the four conditions, explains each in plain words, and builds a checker in code.

The four conditions

Take the problem with inequality constraints g_i(x) ≤ 0 and equality constraints h_j(x) = 0. A point x* with multipliers λ* and ν* satisfies the KKT conditions when all four of these hold:

  1. Primal feasibility. g_i(x*) ≤ 0 and h_j(x*) = 0. The point obeys every rule.
  2. Dual feasibility. λ_i* ≥ 0. Inequality fees are non-negative.
  3. Complementary slackness. λ_i* · g_i(x*) = 0 for every i. Either the constraint is active (g_i = 0) or its multiplier is zero. A rule that is not binding costs nothing.
  4. Stationarity. ∇f(x*) + Σ λ_i* ∇g_i(x*) + Σ ν_j* ∇h_j(x*) = 0. At the optimum, the pull of the objective is exactly balanced by the pushes of the active constraints.

Stationarity says x* is a minimizer of the Lagrangian over x. Complementary slackness says the fee is zero wherever it could matter. Together they make d(λ*, ν*) = f(x*), so the duality gap is zero.

If the problem is convex, any point satisfying all four conditions is a global optimum (sufficiency, no extra assumptions needed). If Slater's condition also holds, every optimum satisfies them for some multipliers (necessity).

Picture: balanced forces

Think of the objective as a hill and the constraint as a wall. The ball rolls downhill (direction -∇f) until the wall stops it. At rest, the wall pushes back exactly against the downhill pull. The multiplier λ is the size of the wall's push. An inactive wall (the ball is not touching it) pushes with force zero.

flowchart LR
    A["Objective pull: -∇f(x)"] --> C["Balance at x*"]
    B["Active walls push: λ·∇g(x)"] --> C
    C --> D["∇f + λ∇g = 0"]

At the optimum the forces cancel; walls that are not touching have λ = 0.

A worked example

Text
minimize    f(x) = (x₁ - 2)² + (x₂ - 1)²
subject to  g(x) = x₁ + x₂ - 2 ≤ 0

Without the constraint, the best point is (2, 1), but 2 + 1 = 3 > 2, so it is infeasible. We guess that the constraint is active: x₁ + x₂ = 2.

Stationarity: ∇f = (2(x₁ - 2), 2(x₂ - 1)) and ∇g = (1, 1). So:

Text
2(x₁ - 2) + λ = 0
2(x₂ - 1) + λ = 0
x₁ + x₂ = 2

Subtract the first two equations: x₁ - 2 = x₂ - 1, so x₁ = x₂ + 1. Then 2x₂ + 1 = 2, giving x₂ = 0.5, x₁ = 1.5. From the first equation, λ = -2(1.5 - 2) = 1.

Check: λ = 1 ≥ 0 (dual feasible), the constraint is active (slackness holds), and g = 0 (feasible). All four conditions pass, and the problem is convex, so x* = (1.5, 0.5) is optimal with f(x*) = 0.25 + 0.25 = 0.5.

A KKT checker in code

The function below takes a candidate x, multiplier lam and checks each condition numerically with a tolerance. It works for one inequality constraint; you can extend it with lists.

Python Checking KKT conditions

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Candidate B fails primal feasibility, so it cannot be optimal.

Inactive constraint: lambda is zero

Change the constraint to x₁ + x₂ - 5 ≤ 0. Now (2, 1) has g = -2 < 0, so it is feasible, and it is the unconstrained minimizer. Complementary slackness forces λ = 0, stationarity reduces to ∇f = 0, and the answer is (2, 1). The constraint changes nothing, which is exactly what λ = 0 records.

Let us compare with a general-purpose solver. SciPy's SLSQP method solves the constrained problem numerically. It uses a different algorithm, so agreeing with it is a good independent check.

Python Compare with a numerical solver

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should see (1.5, 0.5) with f = 0.5 for the first case and (2, 1) with f = 0 for the second.

Common mistakes

  • Wrong sign of the multiplier. With the form g ≤ 0 and a minimization problem, λ ≥ 0. If your solver uses c(x) ≥ 0, the sign flips.
  • Forgetting complementary slackness. A point can satisfy stationarity with λ > 0 on an inactive constraint; that violates slackness.
  • Using KKT as sufficient for non-convex problems. For non-convex problems KKT points are only candidates (they may be saddle points or local minima).

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What does complementary slackness require?

    Each inequality is either active (g_i = 0) or has multiplier zero, so the product vanishes.
  2. 2. For a convex problem satisfying Slater's condition, the KKT conditions are

    Convexity makes them sufficient, and Slater's condition guarantees multipliers exist, which makes them necessary.
  3. 3. In the example minimize (x₁-2)² + (x₂-1)² subject to x₁ + x₂ ≤ 2, what is the multiplier at the optimum?

    At x* = (1.5, 0.5), the gradient of f is (-1, -1) and the gradient of g is (1, 1), so stationarity needs λ = 1.
  4. 4. If the unconstrained minimizer of f is strictly feasible, what is λ?

    The constraint is inactive, so complementary slackness forces λ = 0 and the constraint does not change the answer.

Summary

  • KKT = primal feasibility, dual feasibility (λ ≥ 0), complementary slackness (λ g = 0) and stationarity (∇f + Σλ∇g + Σν∇h = 0).
  • For convex problems, a KKT point is globally optimal; with Slater's condition, every optimum is a KKT point.
  • The multiplier is the size of the "push" from a constraint; inactive constraints have multiplier zero.
  • A short numerical checker, plus a solver such as SLSQP, makes a good independent test of a hand solution.

Next: Sensitivity and Shadow Prices