Lagrange Multipliers
Optimise something while a constraint holds. The answer is where the level lines just graze the constraint, and lambda is what that costs.
Overview
Why the usual rule stops working
Unconstrained: find where the gradient is zero.
Constrained: that rule fails immediately, because the unconstrained optimum is usually somewhere the constraint forbids. On the circle above, the objective increases forever in one direction and its gradient is never zero anywhere.
Lagrange Multipliers
Worth knowing
∇f = λ ∇g. That proportionality is the whole method.Lagrange Multipliers
Optimising under a constraint, and the multiplier that turns out to be worth as much as the answer.
The condition
Look at where the level lines meet the circle.
At most points they cross. Crossing means you can slide along the circle and move to a better level line, so you are not at the optimum.
At the optimum they are tangent — touching without crossing. Sliding either way makes things worse.
Tangency means the two gradients are parallel:
grad f = lambda * grad gThat is the method entire. Solve it together with the constraint itself and you have the candidate points.
Drag the objective weights and watch the marked point travel around the circle, staying exactly where the family of parallel lines grazes it.
The multiplier is the interesting part
lambda looks like bookkeeping. It is not: it is the shadow price of the constraint — the rate at which the optimal value improves as the constraint is relaxed.
Drag the radius control. The optimum's value rises, and the readout's lambda says how fast per unit of radius.
In economics that is literally a price: how much more profit one more unit of capacity is worth, and therefore what you should be willing to pay for it. In machine learning it is the same quantity under different names — the regularisation strength in ridge regression, and the dual variables in an SVM that identify exactly which points are support vectors.
A lambda of zero says the constraint is not binding: you would have chosen that point anyway, and loosening it buys nothing.
Where it shows up
Ridge regression. "Minimise error subject to the coefficients being small" is a constrained problem; the penalised form everyone actually writes is its Lagrangian, and the penalty weight is lambda.
Support vector machines. The dual formulation is Lagrangian, the multipliers are per-training-point, and the ones that come out non-zero *are* the support vectors.
Maximum entropy. Finding the distribution with the most entropy subject to matching known moments produces the exponential family, and the multipliers become its natural parameters.
PCA. Maximising variance subject to unit-length direction gives Cv = lambda v — the multiplier turns out to be the [eigenvalue](eigenvalues_and_eigenvectors.html).
Physics and economics throughout, wherever something is optimised under a budget.
Inequalities
Real constraints are often g(x) <= c rather than g(x) = c, and the extension is the KKT conditions. The addition worth remembering is *complementary slackness*: for each constraint, either it is tight and its multiplier may be non-zero, or it is slack and its multiplier is zero.
That is what makes SVMs sparse. Points comfortably on the correct side of the margin have slack constraints, so their multipliers are zero, so they contribute nothing to the solution. Only the points pressed against the margin survive.
The shadow price, worked
The claim that lambda is a price is easiest to trust on a case you can check by hand. Minimise x² + y² — distance-squared from the origin — subject to 3x + 4y = c. The constraint is a line, and the closest point on a line 3x + 4y = c to the origin is at distance c/5 (because √(3²+4²) = 5), so the minimum value is (c/5)².
Now watch what one unit of c buys:
| c | minimum x²+y² | change |
|---|---|---|
| 24 | 23.04 | |
| 25 | 25.00 | +1.96 |
| 26 | 27.04 | +2.04 |
The optimum rises by about 2 per unit of c, and the multiplier the method returns is lambda = 2c/25 = 2 at c = 25. The two agree: lambda *is* the rate at which the optimal value changes as the constraint moves — the price of one more unit of the resource. The small gap between 1.96 and 2.04 is the curvature of that price across the step; in the limit of an infinitesimal change it is exactly lambda. This is why, in a real problem, the multiplier is often worth more than the optimum: it tells you what relaxing the constraint is worth before you pay to relax it.
This is why the multiplier reappears under other names across machine learning: it is the regularisation strength in ridge regression (the price of the coefficient-size budget), and it is the per-point dual variable in an SVM, where the points whose multiplier comes out non-zero are exactly the support vectors. In every case lambda answers the question the optimum cannot: not "what is the best value" but "what is the constraint costing me", which is usually the number a decision actually turns on.
A multiplier of zero carries its own message: the constraint is not binding, you would have chosen that point anyway, and relaxing it buys nothing — which is as useful to know as a large multiplier that says the constraint is expensive and worth paying to loosen.
For inequality constraints the same idea extends to the KKT conditions, whose complementary slackness says each constraint is either tight with a possibly non-zero multiplier or slack with a zero one — which is precisely what makes an SVM sparse, since points comfortably inside the margin contribute nothing.
Where it goes wrong
Forgetting it finds stationary points, not maxima. The condition holds at constrained minima and saddles too. Check which you have.
Assuming a solution exists. An unbounded objective on an unbounded constraint set has none.
Reading lambda's sign carelessly. It depends on how the Lagrangian was written, and the sign convention differs between texts.
Skipping the constraint qualification. The method assumes the constraint gradients are well behaved at the solution; at a cusp or where constraints are degenerate it can fail.
Optimise with a rule you are not allowed to break
The closest point on a line to the origin, found three ways: by brute force, by substitution, and by the multiplier condition. All three agree, and the multiplier turns out to mean something.
Check yourself
0 of …Answer without scrolling back up.
At a constrained optimum, what is true of the level line and the constraint?
What does the multiplier lambda measure?
Why are SVMs sparse?
Lagrange Multipliers
Constrained: that rule fails immediately, because the unconstrained optimum is usually somewhere the constraint forbids. On the circle above, the objective increases forever in one direction and its gradient is never zero anywhere.