Lagrangian Duality

Hard constraints become prices. The Lagrangian adds each violation times its price, and the best prices certify how good any solution can be.

$Priced constraints produce a dual best of 8.0 under the primal 8.2, leaving a 0.2 gap that convexity would close$

Priced constraints produce a dual best of 8.0 under the primal 8.2, leaving a 0.2 gap that convexity would close

Why Does This Exist?

Constrained problems are hard to solve and harder to certify: "8.2 is optimal" needs proof no feasible 8.1 exists. Enumerating feasibility is hopeless at scale. Duality manufactures certificates cheaply: any dual-feasible price vector yields a lower bound, no enumeration needed.

Form $L(x, \\lambda, \\nu) = f_0(x) + \\sum \\lambda_i f_i(x) + \\sum \\nu_j h_j(x)$ with $\\lambda \\geq 0$ . Dual $g(\\lambda, \\nu) = \\inf_x L$ ; dual problem maximizes $g$ . Weak duality $d^\\star \\leq p^\\star$ always; strong ( $=$ ) under convexity plus Slater. It generalizes Lagrange multipliers and duality toward the algorithms in convex optimization.

The one idea you need first

Pricing a violation means charging $\\lambda_i > 0$ per unit of $f_i(x) > 0$ . Feasible points pay nothing extra; infeasible ones pay up. The dual searches prices making even the cheapest $x$ expensive.

Think of It Like This

Parking fines versus gates

A lot owner can gate every spot (primal: enforce) or set fines so circling elsewhere beats violating (dual: price). Any fine schedule yields a revenue lower bound without checking each car.

Well-set fines empty violations exactly (strong duality); weak fines leave a gap of tolerated cheating. Where it stops: fines need collection power (constraint qualification). Ungoverned lots ignore prices.

How It Actually Works

Always: $g(\\lambda, \\nu) \\leq p^\\star$ for dual-feasible prices, so $d^\\star \\leq p^\\star$ . Saddle view: $\\sup_{\\lambda \\geq 0,\\nu} \\inf_x L \\leq \\inf_x \\sup_{\\lambda \\geq 0,\\nu} L$ . Slater (strictly feasible convex point) closes to equality; then KKT holds and complementary slackness prices exactly the active walls. Dual ascent, ADMM, and decomposition methods climb $g$ when the primal is block-separable.

Worked example

Minimize $x^2$ subject to $x \\geq 2$ (write $-x + 2 \\leq 0$ ). Primal $p^\\star = 4$ at $x = 2$ . Lagrangian $L = x^2 + \\lambda(2 - x)$ . Inf over $x$ : $x = \\lambda/2$ , value $g(\\lambda) = 2\\lambda - \\lambda^2/4$ . Maximize: $g' = 2 - \\lambda/2 = 0$ gives $\\lambda^\\star = 4$ , $d^\\star = 8 - 4 = 4$ . Gap zero, price 4 per unit of bound relaxation: loosening to $x \\geq 1.9$ drops optimum by about $4 \\times 0.1 = 0.4$ (check: $1.9^2 = 3.61$ vs $4$ ).

Code

1import numpy as np2
3lam = np.linspace(0, 8, 9)4g = 2 * lam - lam**2 / 4  # dual function5print(round(float(g.max()), 2))  # -> 4.06print(round(float(lam[g.argmax()]), 1))  # -> 4.0

Dual peak 4.0 at price 4.0 matches the primal 4.0. The grid search certifies without touching constraints.

Watch Out For

Assuming zero gap without convexity

On non-convex problems the dual can sit far below the primal (e.g. integer programs with gaps of 2x). Rounding the dual up as "optimal" ships infeasible or suboptimal points certified by nothing.

Quote $d^\\star$ as a bound only, and measure the gap. If it will not close, switch to branch-and-bound or convex relaxations with gap tracking.

Dualizing away the structure you needed

Moving coupling constraints into prices can destroy separability the solver exploited, or create nonsmooth duals needing bundle methods. Naive dual ascent then crawls or diverges on step sizes.

Match algorithm to dual smoothness: subgradient for nonsmooth, augmented Lagrangian/ADMM for stabilized steps. If dual values oscillate, the stepsize is the bug.

The Quick Version

Lagrangian prices violations; the dual maximum lower-bounds the primal minimum, always.
Example $x^2$ above 2: primal 4, dual 4 at price 4, zero gap.
Convex plus Slater closes the gap; KKT then holds with priced active walls.
Prices are sensitivities: $\\lambda_i$ values relaxing the wall.
Non-convex gaps stay open; report bounds with measured gaps.
Climb nonsmooth duals with stabilized methods, not raw ascent.