Definition
Lagrange multiplier To optimize subject to , introduce a scalar and look for points where and . The Lagrange multiplier is the factor between the two gradients; at the optimum it equals the rate at which the best achievable changes as the constraint is relaxed.
At a glance
- Notation
- Lagrangian ; several constraints:
- Input → output
- objective and constraints → candidate points with multipliers
- Key property
- , and for the constraint
- Inequalities
- KKT conditions: and (complementary slackness)
- Prerequisites
- derivatives & gradients, Jacobian, convexity
- Used in
- PCA, SVM duals, maximum entropy / softmax, regularization, constrained resource allocation
The intuition
Walk along the constraint curve and watch . At a constrained maximum you can't go higher by moving along the curve, so doesn't change to first order in the direction the curve runs: has no component along the curve. The only direction left is perpendicular to the curve — and that is the direction of , which is always perpendicular to its level set. So the two gradients line up.
Geometrically, the optimum is where a contour of just touches the constraint curve without crossing it. Crossing would mean higher and lower values of on either side, so you could still improve.
The math
- objective to maximize or minimize
- equality constraint; the feasible set is its level set
- Lagrange multiplier, one per constraint
Why parallel. Let be any direction tangent to the constraint at , so . Moving along the constraint changes at rate , which must be zero at an optimum. So is orthogonal to every tangent direction, i.e. it lies in the span of . With constraints the same argument gives , valid when the are linearly independent at (the constraint qualification).
Meaning of λ. For the family , let be the optimal value. Then : the multiplier is the marginal value, or shadow price, of the constraint. means the constraint isn't binding.
Inequality constraints (KKT). For subject to , write with , plus complementary slackness : either the constraint is active () and pushes back with , or it is slack and . For convex problems these conditions are sufficient as well as necessary.
Solving an equality-constrained problem
- 1Write .
- 2Set and : equations in unknowns.
- 3Solve for all candidates ; also check points where the are dependent.
- 4Evaluate at every candidate (or on a compact feasible set, compare them) to pick the max and the min.
See it
point (-0.866, 0.500) · φ = 150°
f = x + y = -0.366
angle(∇f, ∇g) = 105.0°
along-circle part of ∇f = -1.366
best λ = ∇f·∇g / ‖∇g‖² = -0.183
Not optimal: move along the violet arrow to increase f while staying on the circle.
drag the white point around the circle · it snaps to the optima within 2°
Worked example
Minimize subject to . Stationarity of gives and , so ; the constraint then gives , , , and .
Check the shadow price. With constraint , the same steps give , and , so at — exactly . Raising to raises the minimum to about (exactly ).
The viz problem. For on : gives , and the constraint gives . The two candidates are the maximum and the minimum — the method finds both.
In code
1import numpy as np2from scipy.optimize import minimize34f = lambda v: v[0]**2 + 2 * v[1]**25con = {"type": "eq", "fun": lambda v: v[0] + v[1] - 3}6res = minimize(f, x0=[0.0, 0.0], method="SLSQP", constraints=[con])7res.x.round(4), round(res.fun, 4) # (array([2., 1.]), 6.0)89# PCA: grad(v^T S v) = lambda * grad(v^T v) => S v = lambda v10S = np.array([[2.0, 1.0], [1.0, 2.0]])11lam, V = np.linalg.eigh(S)12lam[-1], V[:, -1] # 3.0, ±[0.707, 0.707]: max variance = λWhere it's used
PCA
Maximizing variance subject to gives : the principal directions are eigenvectors, and each multiplier is the variance captured.
Support vector machines
The SVM dual comes from the Lagrangian of the margin constraints; complementary slackness makes only for points on or inside the margin — the support vectors.
Maximum entropy and softmax
Maximizing entropy subject to and a fixed expected score gives : softmax, with the inverse temperature as the multiplier on the score constraint.
Regularization
Ridge regression minimizes squared error subject to ; its Lagrangian is the familiar penalized loss, and the penalty strength is the KKT multiplier for that budget.
Check yourself
Maximize subject to . The optimum and multiplier are…
Check yourself
At the optimum of subject to , the multiplier is . If increases by , the optimal value changes by about…
Remember
- ✓At a constrained optimum : the contour of is tangent to the constraint.
- ✓Solve and together; compare all candidates.
- ✓ — the shadow price of the constraint; means it isn't binding.
- ✓KKT extends this to inequalities with μ ≥ 0 and complementary slackness — the basis of SVMs.