lagrangian

Parent: math

The device that turns a constrained optimization into a stationarity condition. Minimize the objective f(x) subject to equality constraints hᵢ(x)=0 and inequality constraints gⱼ(x)≤0, with x ∈ ℝⁿ.

Why multipliers appear — the geometry (equality case)

Take just equalities: the feasible set is the surface M = {x : hᵢ(x)=0}. At a regular point (the ∇hᵢ are linearly independent), the directions you may move and stay feasible are the tangent space

$$T_xM=\{\,d:\ \nabla h_i(x)\cdot d=0\ \ \forall i\,\}.$$

Let x* be a local min of f on M. Along any feasible curve through x*, f is stationary, so

$$\nabla f(x^\ast)\cdot d=0\qquad\text{for every } d\in T_xM .$$

That says ∇f(x*) is orthogonal to the tangent space, i.e. it lies in the span of the constraint gradients:

$$\nabla f(x^\ast)=-\sum_i \lambda_i\,\nabla h_i(x^\ast).$$

The coefficients λᵢ are exactly the Lagrange multipliers — and by linear independence they're unique. Intuition: at the optimum you can't push f downhill without some constraint pushing back; ∇f is a combination of the forces ∇hᵢ that hold you on the surface.

The Lagrangian packages this into one stationarity condition

Lagrangian

Fold every constraint into the objective, each weighted by its own multiplier — λᵢ (free sign) for each equality hᵢ, μⱼ≥0 for each inequality gⱼ:

$$L(x,\lambda,\mu)=f(x)+\sum_i \lambda_i\, h_i(x)+\sum_j \mu_j\, g_j(x).$$

Now the optimum is just a stationary point of L:

• $\nabla_x L=0$ reproduces the condition above ($\nabla f=-\sum\lambda_i\nabla h_i$);
• $\partial L/\partial\lambda_i=0$ reproduces the constraint hᵢ=0.

So the constrained problem becomes: solve ∇L=0 — n+m equations in the n+m unknowns (x, λ). The constraint hasn't vanished; it's been turned into stationarity in the extra variables λ.

What the multiplier means: shadow price (sensitivity)

Relax constraint i to hᵢ(x)=bᵢ and let p*(b) be the resulting optimal value. Differentiate: with ∇hⱼ·(∂x*/∂bᵢ)=δᵢⱼ and ∇f=-Σλₖ∇hₖ,

$$\frac{\partial p^\ast}{\partial b_i}=\nabla f\cdot\frac{\partial x^\ast}{\partial b_i}=-\sum_k \lambda_k\,\nabla h_k\cdot\frac{\partial x^\ast}{\partial b_i}=-\lambda_i .$$

So λᵢ is the marginal change in the optimum per unit relaxation of constraint i — its shadow price. A tight constraint with a big multiplier is "expensive"; a multiplier of 0 means the constraint isn't binding.

Worked micro-example

Minimize x²+y² s.t. x+y=1. Then L=x²+y²+λ(x+y−1), so ∇ₓL=0 gives 2x+λ=0, 2y+λ=0 ⟹ x=y, and the constraint gives x=y=½, λ=−1. Optimal value ½. Check sensitivity: with x+y=b the value is p*(b)=b²/2, so dp*/db=b=1=−λ. ✓

Full representative computation (min and max, geometric + shadow-price checks): lagrangian-worked-example.

Inequality constraints → μ≥0 and complementary slackness

An inequality gⱼ≤0 only blocks motion one way, so its multiplier is sign-constrained, μⱼ≥0 (it can only push you back into the feasible region). And if a constraint is slack at the optimum (gⱼ<0, not touching), it exerts no force, so μⱼ=0 — complementary slackness μⱼgⱼ=0. Equality (free λ) + inequality (μ≥0 + slackness) together are the kkt conditions.

The min–max (saddle) view → duality

L couples the primal x and the dual (λ,μ). Maximizing out the multipliers reproduces the constrained problem:

$$\min_x\ \max_{\mu\ge 0,\ \lambda}\ L(x,\lambda,\mu)\ =\ \big(\text{primal optimum}\big),$$

because a violated constraint lets the inner max drive L→∞. Swapping the order gives the dual $\max_{\mu\ge0} \min_x L$, always ≤ primal (weak duality), with equality under convexity + Slater. Full duality → kkt and classical-optimization.