Reference 0014

Lagrangian Recipe Card

How to move any constraint into the objective: replace the wall with its price. The multiplier is the rent at which the optimizer obeys voluntarily.

The Recipe

1. normalize:  write every inequality as  g_i(w) <= 0
               write every equality  as  h_j(w) = 0
2. price:      L(w, λ, ν) = f0(w) + Σ λ_i g_i(w) + Σ ν_j h_j(w)
3. signs:      λ_i >= 0  (inequality rents),  ν_j free  (equality rents)
4. read:       violation costs, slack credits; each wall has its own rent

The Three Readings of λ

Price

λ_i is the per-unit toll for violating constraint i. At λ* the optimizer stops exactly at the wall, by self-interest: λ* = the push at the wall.

Sensitivity

λ*_i = objective improvement per unit of constraint relaxation, locally. The solver's dual output. Zero on slack constraints (complementary slackness).

Certificate

For any λ >= 0: min_w L(w, λ) <= constrained optimum (weak duality). Best floor = optimum under convexity (strong duality).

Course Example (bowl f0' = 0.30w - 0.30, cap w <= c)

L(w, λ) = f0(w) + λ(w - c)
renter's choice:  w(λ) = 1 - λ/0.30
wall rent:        λ* = 0.30(1 - c)      (= 0 if c >= 1: slack)

λ < λ*  cheats past wall     λ = λ*  obeys voluntarily
λ > λ*  over-complies        loose wall  rent zero

The Grouping Trick (penalty ↔ budget)

L(w, λ) = f0(w) + λ(cost(w) - budget)
         = [ f0(w) + λ cost(w) ] - λ · budget
              penalty problem         constant, moves nothing

budget with dual λ*  =  penalty with fee λ*   (Reference 0013)

Whiteboard Traps

wrong sign:      g must be <= 0 form BEFORE pricing
missing λ >= 0:  negative inequality rents break weak duality
equality vs ineq: equality rents (ν) may take any sign
non-convex:      floor may never reach ceiling (duality gap)

Use this page with Lesson 0014 (the toll story and lab), Reference 0004 (KKT checks), and Reference 0013 (budget–penalty bridge). Formal source: Boyd & Vandenberghe §5.1–5.2.