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

This module needs JavaScript: the numbers are computed in the page rather than recorded.

Worth knowing

At an unconstrained optimum the gradient is zero. At a constrained one it need not be — it only has to point along the constraint's gradient.
∇f = λ ∇g. That proportionality is the whole method.
Geometrically: the level line of the objective is tangent to the constraint. If it crossed, you could slide along and do better.
λ is the shadow price — how much the optimum improves per unit of loosened constraint.

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 g

That 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.

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.

Check yourself

0 of 3

Answer without scrolling back up.

  1. At a constrained optimum, what is true of the level line and the constraint?

  2. What does the multiplier lambda measure?

  3. Why are SVMs sparse?

Cheat sheet

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.

MATHS · vizlearn.in/maths/lagrange_multipliers.html

About the author

Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.