Beneath every minimization lies a maximization that reaches up to touch it. Attach a price λ ≥ 0 to each constraint and the Lagrange dual function g(λ) = infx L(x,λ) is born — and it is runnable: for every λ it is a certified lower bound on the answer, and when the problem is convex the two meet exactly. Down the center, data flows: the problem goes in, the dual is solved, the gap comes out. The blue team builds and defends it; the red team tries to break it.
source Lagrangian duality (von Neumann, minimax) — secondary: Boyd & Vandenberghe, Convex Optimization (2004), ch. 5 — web.stanford.edu/~boyd/cvxbook. Cited, not claimed. Rendered, not quoted.
Take the constrained problem min f₀(x) s.t. fᵢ(x) ≤ 0. Fold each constraint into the objective with a price:
L(x,λ) = f₀(x) + ∑λᵢ fᵢ(x), λ ≥ 0. The dual function g(λ) = infx L(x,λ) minimizes over x with the prices fixed.
Two facts fall out for free. Weak duality: because a feasible x has fᵢ≤0, L(x,λ)≤f₀(x), so g(λ) is always below the primal optimum p*. Concavity: g is an infimum of functions affine in λ — so g is concave, and maximizing it is itself a convex problem, even when the primal is not.
Live for the panel’s convex QP: at λ=, g(λ)= ≤ p*=, gap= = (λ−b/2)² ≥ 0.
The optimal λ* is exactly the-lagrange-multiplier’s shadow price — how much p* would move if the constraint loosened. The dual is the shadow problem that prices it.
When the-kkt-conditions hold, they certify the lower bound is tight: primal and dual meet, gap = 0. This same structure is the machinery beneath the SVM’s dual (support vectors are the active constraints) and linear-programming duality. Each sphere is the next one’s premise.
The blue team’s live check: re-verify weak duality on a grid, strong duality at λ*, and re-derive the non-convex gap from first principles. If red falsely claims strong duality, this badge is where it shows.
A constructed convex QP with a strictly feasible (Slater) point, so every quantity is closed-form:
Objective is strictly convex (Q = I), one price λ ≥ 0. The minimizer, the dual function, the multiplier and the gap all have exact forms — nothing is fitted, everything below is derived. Feed it to the panel.
Slide λ: the dual g(λ) rises, touches p* at λ*=b/2, then falls. It never crosses above p* — that is weak duality, live.
Every number is computed from the closed forms on the spot — p*=b²/4, g(λ)=−λ²+bλ, λ*=b/2 — never looked up.
What the machine proves. For the convex QP: primal p* = b²/4 at x*=(b/2, b/2); dual optimum d* = b²/4 at λ*=b/2 — the optimal duality gap is 0 (Slater ⇒ strong duality). For every λ≥0 the gap is (λ−b/2)² ≥ 0 — weak duality, exact and universal.
The blue witness (left) confirms these live; the red team (right) shows the gap can be real — and gets caught claiming otherwise.
Integer programs, general non-convex QPs, MAXCUT — their Lagrangian duals leave a gap that no amount of pricing closes. Duality does not make hard problems easy; it certifies bounds. Believing the dual always equals the primal is the classic error.
“The dual optimum always equals the primal.” Cut. Only under convexity + a constraint qualification. The panel’s tamper builds a problem where d* = −5 < 0 = p* — a gap of 5.
“Weak duality needs convexity too.” Cut. Weak duality g(λ)≤p* is universal — it holds for any problem, convex or not. That is why the dual is always a valid bound.
“λ is just an algebraic trick.” Kept, corrected. λ* is the shadow price — the marginal cost of the constraint, and the SVM’s support weights.
The red team’s move: take a non-convex two-point problem (x ∈ {0, 2}) whose real gap is 5, and falsely claim strong duality — assert its gap is 0. The blue witness (window 7) re-derives the true gap and is watching.
Assert strong duality where convexity fails and the reported gap flips to 0, but p*=0 while d*=−5. The witness recomputes 5, disagrees, and turns red. Nothing is faked; the attack is real and it is caught.