THE KKT CONDITIONS

Every constrained optimum carries a four-part certificate. For min f(x) subject to g(x) ≤ 0, a point is optimal only if it satisfies stationarity, primal feasibility, dual feasibility, and complementary slackness at once. This instrument builds one convex QP with a known minimizer, one active and one inactive constraint, and checks all four to 1e-9 — rendered, not quoted.

source Karush, Minima of Functions of Several Variables with Inequalities as Side Constraints, MSc thesis, Univ. Chicago (1939); Kuhn & Tucker, Nonlinear Programming, Proc. 2nd Berkeley Symp. (1951), 481–492. ref ↗ no stable primary link — AMBER secondary cite

Blue Team · builds & defends
3

The Model

A strictly-convex quadratic in two variables with two linear inequality constraints. Closed-form everything.

minimize f(x,y) = ½(x−2)² + ½(y−2)² subject to g₁(x,y) = x + y − 2 ≤ 0 g₂(x,y) = x − 5 ≤ 0

Unconstrained minimum sits at (2,2), which violates g₁. So g₁ binds (active); g₂ has room to spare (inactive). The constrained optimum is x* = (1,1), f* = 1, found in closed form by symmetry on the line x+y=2.

5

The Lineage

the-lagrange-multiplier, extended to inequalities. Lagrange handles equalities with free-sign multipliers; KKT adds two things inequalities force:

• dual feasibility — multipliers must be ≥ 0 (a constraint can only push one way);
• complementary slackness — λᵢgᵢ = 0 decides which constraints bite: a slack constraint gets λ=0, a tight one may get λ>0.

This is the exact optimality certificate a convex solver returns.

7

The Witness

Live re-check. The verifier is asked whether the off-optimum vertex (5,−3) — a KKT-stationary point with a negative multiplier — is wrongly certified as optimal.

…
The Machine
4

Data In in ↓

The candidate optimum and its multipliers, to be certified:

x*(1, 1)
λ = (λ₁, λ₂)(1, 0)
active set{ g₁ }
▾   certify   ▾
0

The Panel LIT

Four conditions, each computed live at the point above:

KKT is sufficient here: the problem is convex, so this KKT point equals the global optimum from a brute-force sweep.

▾   result   ▾
8

Data Out out ↓

…
Red Team · attacks & breaks
1

The Adversary WALL

Stationarity alone is not optimality. Many points satisfy ∇f + Σλ∇g = 0 — maxima, saddles, and off-face vertices among them. The vertex (5,−3) where both constraints are tight solves the stationarity system exactly, yet f there is 17, not 1. Without dual feasibility and a constraint qualification, the certificate is worthless.
2

The Graveyard

  • “Set the gradient to zero — that's the optimum.”
    Only unconstrained. With constraints the gradient need not vanish; it is balanced by active-constraint forces λ∇g.
  • “Any λ that closes the stationarity equation works.”
    A negative λ means the constraint is pulling the wrong way — that's a point you can still improve from. Sign matters.
  • “KKT proves it's a minimum.” AMBER
    Necessary in general (under a constraint qualification); sufficient only when convex. Here f is convex and g are linear, so it holds — that assumption is doing real work.
6

The Tamper

Planted void: drop the dual-feasibility check (allow λ < 0). The non-optimal vertex (5,−3), with multipliers (5,−8), then passes stationarity + primal feasibility + complementary slackness — and is mis-certified as the optimum. The Witness (7) catches it.