Constrained optimisation — the Lagrangian and duality

The Lagrangian transforms constrained optimisation into an unconstrained problem in more variables. Duality theory then gives an entirely new perspective: every constrained problem has a 'dual' problem whose solution provides a lower bound, and under convexity the two are equal. This is the deepest machinery in optimisation and the source of the shadow-price economics every analyst already half-knows.

The Lagrangian

minimize    f(x)
subject to  g_i(x) ≤ 0,  h_j(x) = 0

L(x, λ, ν) = f(x) + Σᵢ λᵢ g_i(x) + Σⱼ νⱼ h_j(x)
λᵢ ≥ 0,  ν unrestricted

λ are the inequality multipliers (KKT multipliers, dual variables); ν are equality multipliers. They effectively price violations of the constraints into the objective.

Lagrange dual function

g(λ, ν) = inf_x L(x, λ, ν)

Minimise L over x for fixed (λ, ν). g is always concave (infimum of affine functions in (λ, ν)). The dual problem is to maximise g subject to λ ≥ 0.

Weak duality

For any λ ≥ 0 and any feasible x: g(λ, ν) ≤ f(x). Therefore max_{λ,ν} g ≤ min_x f. The dual optimal value is always a lower bound on the primal optimal value. Duality gap = primal − dual ≥ 0.

Strong duality

When the duality gap is zero, primal and dual are equal. For convex problems satisfying Slater's condition (there exists a strictly feasible point in the inequalities), strong duality holds. This is the workhorse fact.

Shadow prices and sensitivity

Suppose we perturb a constraint g_i(x) ≤ b_i (replacing 0 with b_i). Then ∂p*(b)/∂b_i = -λᵢ* — the optimal Lagrange multiplier gives the rate at which the optimum improves as the constraint is relaxed. Every economist's 'marginal value of relaxing constraint X' is, literally, a Lagrange multiplier.

Minimum-variance with budget — the dual treatment

Primal: min (1/2) wᵀΣw s.t. 1ᵀw = 1. Lagrangian: L = (1/2) wᵀΣw - ν(1ᵀw - 1). ∂L/∂w = Σw - ν 1 = 0 ⟹ w = ν Σ⁻¹ 1. Plugging into the constraint: 1 = ν 1ᵀΣ⁻¹1, so ν = 1/(1ᵀΣ⁻¹1). Substituting back: w_MV = Σ⁻¹1 / (1ᵀΣ⁻¹1). The shadow price ν tells you: a small increase in the budget would reduce variance by ν per unit relaxation — but for the trivial 'budget = 1' problem this is mostly mathematical formalism. The shadow-price machinery becomes essential when more interesting constraints appear (factor exposures, sector caps).

Conjugate function and the dual

The convex conjugate f*(y) = sup_x (yᵀx - f(x)) is the second-most-useful object in convex analysis after the Lagrangian. Many problems are simpler in the conjugate dual: SVM duals, exponential families' log-partition functions, Fenchel-Rockefeller-style strong duality.

Saddle-point interpretation

The Lagrangian L(x, λ, ν) has primal optimum p* = min_x sup_{λ≥0, ν} L and dual optimum d* = sup_{λ≥0, ν} min_x L. Under strong duality, p* = d* and (x*, λ*, ν*) is a saddle point — a min in x, max in (λ, ν).