Constrained optimization and Lagrange multipliers: study notes

 

1.30 Constrained optimization and Lagrange multipliers: study notes

Learn AI by Story

1. The idea in one sentence

When you want the best value of something but you are not free to choose any input (you must obey a rule such as "use exactly 40 metres of fence"), Lagrange multipliers turn the rule into an extra variable so that you can solve the problem with ordinary calculus, and that extra variable also tells you how much the rule is costing you.

2. The story from the video

Leela has 40 metres of fence and wants a rectangular pen for her goats with the biggest possible area. She tries shapes: 2 by 18 gives 36 square metres, 5 by 15 gives 75, 8 by 12 gives 96, and 10 by 10 gives 100. The square wins. Then she asks the calculus question: at the best point, the direction in which area grows fastest must point the same way as the direction in which the fence grows fastest, otherwise she could slide along the fence budget and do better. That matching of directions, with a scaling factor called lambda, gives x = y = 10 and lambda = 5. And lambda means something: one extra metre of fence buys about 5 extra square metres.

3. Key definitions (glossary)

• Objective function f(x): the quantity you want to make as large or as small as possible. Plain English: the score.
• Decision variables: the inputs you may choose (for the pen: the width x and length y).
• Constraint: a rule the inputs must obey. Plain English: the budget or fence.
• Equality constraint: g(x) = c. The rule must hold exactly (perimeter equals 40).
• Inequality constraint: h(x) <= 0 (or >= 0). The rule is a limit, not an exact value (use at most 40 metres).
• Feasible set (feasible region): all inputs that satisfy every constraint. Plain English: the allowed area of the map. A point inside it is called feasible.
• Constrained optimisation: minimising or maximising f over the feasible set only.
• Unconstrained optimisation: no rules; the optimum has gradient zero (see roadmap 1.24 gradients and 1.25 Jacobian and Hessian).
• Gradient: the vector of partial derivatives; it points in the direction of steepest increase. The gradient of xy is (y, x).
• Level set (contour): all points where a function has the same value, like a contour line on a map. The gradient is perpendicular to the level set.
• Tangent: touching without crossing. At a constrained optimum a level curve of f is tangent to the constraint curve.
• Lagrange multiplier (lambda): the extra number attached to a constraint that makes the gradients line up. Plain English: the exchange rate between the constraint and the objective.
• Lagrangian L(x, lambda): the combined function that includes the objective and the constraint. A common form is L = f(x) - lambda times (g(x) - c). Some books write plus lambda g; the sign of lambda flips but the answer is the same.
• Stationary point of the Lagrangian: where all partial derivatives of L, with respect to x and lambda, are zero. Setting the derivative with respect to lambda to zero gives back the constraint.
• Shadow price (sensitivity): how much the best value changes if the constraint limit changes by one unit; it equals lambda.
• Active and inactive constraint: an inequality that is exactly tight at the solution (active) or has room to spare (inactive).
• KKT conditions (Karush-Kuhn-Tucker): the extension of Lagrange multipliers to inequality constraints: stationarity, primal feasibility, dual feasibility (multipliers of inequalities are not negative in the minimisation convention), and complementary slackness.
• Complementary slackness: for each inequality, multiplier times constraint slack equals zero. Plain English: either the constraint is tight, or its multiplier is zero.
• Primal and dual problem: the original problem and the problem built from the Lagrangian by minimising over x first and then maximising over the multipliers. The dual gives a bound on the primal.
• Penalty method: replace a hard constraint by an extra cost for breaking it.
• Projected gradient descent: take a normal gradient step, then project (snap) the result back onto the feasible set.

4. Step-by-step explanation, from basics to the full picture

Step 1: unconstrained versus constrained. Without rules, the top of a hill is where the gradient is zero. With a rule, you may be forced to stay on a path or inside a fenced region, and the best allowed point is usually not the top of the hill. You might be standing on a hillside path, at the highest point of the path, and the gradient of the hill there is not zero. It simply points off the path, which you are not allowed to leave.

Step 2: the geometric idea. Imagine the contour lines of the objective f (lines of equal area) and the constraint curve g(x) = c (the fence budget). Walking along the constraint curve, f goes up and down. At the best point, f stops improving as you move along the curve, which means the contour of f touches the constraint curve without crossing it. Two curves that touch tangentially have parallel normals, and the normal to a level set is the gradient. So at the optimum, the gradient of f is parallel to the gradient of g.

Step 3: parallel means a multiple. Two vectors being parallel is written grad f = lambda times grad g. That number lambda is the Lagrange multiplier. Together with the constraint equation g(x) = c, this is the whole system: n equations from the gradient condition (one per variable) plus one constraint equation, for n + 1 unknowns (the n variables and lambda). Mathematics for Machine Learning (Deisenroth, Faisal and Ong, section 7.2) presents this through the Lagrangian.

Step 4: the Lagrangian packaging. Define L(x, lambda) = f(x) - lambda times (g(x) - c). Set grad of L with respect to x to zero: that gives grad f = lambda grad g. Set the derivative of L with respect to lambda to zero: that gives g(x) = c. So "find a stationary point of L" encodes both conditions. You have swapped a constrained problem in n variables for an unconstrained-looking problem in n + 1 variables.

Step 5: solve. Solve the n + 1 equations (often by simple substitution). Then check which candidate is a maximum, a minimum or neither, by comparing values or using second-order tests. Remember that the Lagrange conditions find candidates only: stationary points.

Step 6: what lambda means. If you relax the constraint from c to c + delta, the best value changes by roughly lambda times delta (with the sign convention above). So lambda is the marginal value of one more unit of the resource. In the fence story, lambda = 5 means about 5 more square metres of area per extra metre of fence.

Step 7: inequality constraints. Real problems often say "at most". The constraint is either tight (active) or has slack (inactive). If it is inactive, the optimum is just an ordinary unconstrained optimum and the multiplier is zero. If it is active, it behaves like an equality, and the multiplier must have the correct sign (non-negative in the standard minimisation form: the constraint can only push against you, not pull). Mathematics for Machine Learning section 7.2 gives the Lagrangian for inequalities with multipliers lambda >= 0, and Goodfellow et al. (Deep Learning, section 4.4) describes the generalised Lagrangian and the KKT approach.

Step 8: the dual. For a problem to minimise f(x) subject to constraints, define the dual function by minimising the Lagrangian over x for fixed multipliers. This function is always a lower bound on the optimum (weak duality). Maximising it over the multipliers gives the dual problem. For convex problems, with mild conditions, the two optimal values are equal (strong duality). See Boyd and Vandenberghe chapter 5 "Duality", section 5.1 "The Lagrange dual function", and Mathematics for Machine Learning section 7.3.

5. Everything the video skipped

Several constraints. With several equality constraints g_1 = c_1, ..., g_m = c_m, use one multiplier each: L = f - lambda_1 (g_1 - c_1) - ... - lambda_m (g_m - c_m). At the optimum, grad f is a combination of the constraint gradients.

Regularity. The method needs the constraint gradients to be linearly independent at the solution (a "constraint qualification"). Without it the multiplier condition can fail even at a true optimum.

Sign conventions. Some books write L = f + lambda g, others L = f - lambda g. Both give the same x. Only the sign of lambda changes. For inequalities, textbooks agree on a convention in which multipliers are non-negative for a minimisation problem written with constraints h(x) <= 0.

KKT conditions in words. (1) Stationarity: grad f plus the weighted constraint gradients equals zero. (2) Primal feasibility: all constraints hold. (3) Dual feasibility: inequality multipliers are not negative. (4) Complementary slackness: for every inequality, multiplier times constraint value is zero. For convex problems the KKT conditions are necessary and sufficient under regularity assumptions; for non-convex problems they are necessary only (under constraint qualification), so you still need to compare candidates.

Alternatives to Lagrange multipliers. (a) Substitution: solve the constraint for one variable and plug in, as in the box example below. It is simplest when it is possible. (b) Penalty methods: minimise f plus a penalty for violations; weight decay in neural networks can be read as the penalty form of a constraint on the size of the weights. (c) Projections: projected gradient descent moves freely and then projects back onto the feasible set, as in Goodfellow et al. section 4.4 and the Dive into Deep Learning chapter on convexity (section 12.2). (d) Barrier methods and interior-point methods keep you strictly inside the region.

Link between a constraint and a penalty. Constraining the norm of the weights, say the squared length of w is at most r, and adding a penalty alpha times the squared length of w to the loss are two views of the same idea. For a suitable alpha, which plays the role of the multiplier, the two have the same solution (for convex problems). A bigger alpha means a smaller allowed radius. This is why L2 regularisation and weight decay are described as constrained optimisation in disguise.

Support vector machines. The hard-margin SVM minimises the squared length of the weight vector subject to every training point being on the correct side with margin at least 1. Introducing a multiplier for each training point and eliminating the weights gives the dual SVM, where only points with non-zero multipliers (the support vectors) matter and complementary slackness explains why. Mathematics for Machine Learning section 12.3 "Dual Support Vector Machine" derives this. The dual form also enables kernels.

Other AI uses of constraints. Probabilities that must sum to 1, as in a softmax output or a mixture-model weight (equality constraint); maximum-entropy models derived with multipliers; trust-region methods in reinforcement learning (limit how far the policy changes); constrained generation and fairness constraints; norm-bounded adversarial examples (stay within a small ball around the original image); and clipped or normalised weights.

Limitations. Lagrange conditions only find stationary points. In non-convex problems there may be many, and some are saddle points. Deep network training is almost never solved with explicit multipliers, because the constraints are handled by penalties or projections. If the constraint set is not smooth (corners), you need KKT rather than plain Lagrange.

Background (history). The method is named after Joseph-Louis Lagrange, an eighteenth-century mathematician who developed it while studying mechanics with constraints. The extension to inequalities appeared in the twentieth century: Karush's 1939 master's thesis and the 1951 paper by Kuhn and Tucker, hence the name KKT. (These are standard historical facts, not taken from the sources listed below.)

Roadmap links. Before: 1.24 and 1.25 (gradients, Jacobian and Hessian), 1.29 numerical stability. After: 1.31 Convex sets and functions (convexity is what makes constrained problems safe to solve and makes strong duality work), 1.32 Gradient descent convergence, and later 2.05 loss functions, regularisation, logistic regression and SVMs.

6. Worked examples with real numbers

All arithmetic below was checked with Python.

Example A: Leela's goat pen. Maximise area f(x, y) = xy subject to perimeter 2x + 2y = 40.

1. Try shapes first: 2 by 18 has area 36, 5 by 15 has area 75, 8 by 12 has area 96, 10 by 10 has area 100.
2. Gradients: grad f = (y, x), and the gradient of g = 2x + 2y is (2, 2).
3. Condition grad f = lambda grad g gives y = 2 lambda and x = 2 lambda. So x = y: the best rectangle is a square.
4. Constraint: 2x + 2x = 40, so x = 10, y = 10, and lambda = 5.
5. Area = 100 square metres.
6. Meaning of lambda: with 41 metres of fence, the square has side 10.25 and area 10.25 squared = 105.0625. The gain is 5.0625, which is close to lambda = 5. (Exactly: the best area with perimeter P is P squared over 16; the derivative with respect to P at P = 40 is 2P over 16 = 5.)

Example B: closest point to the origin on the line x + y = 1. Minimise f(x, y) = x squared + y squared subject to x + y = 1.

1. grad f = (2x, 2y), grad g = (1, 1).
2. Condition: 2x = lambda and 2y = lambda, so x = y = lambda over 2.
3. Constraint: x + y = 1 gives x = y = 0.5 and lambda = 1.
4. Minimum value = 0.25 + 0.25 = 0.5 (the point is at distance about 0.707 from the origin).
5. Sensitivity check: if the constraint becomes x + y = 1.1, then the best point is x = y = 0.55 and the value is 2 times 0.55 squared = 0.605. The change is 0.105 for a change of 0.1 in the constraint, close to lambda = 1 (exactly, the best value for x + y = c is c squared over 2, whose derivative at c = 1 is 1).
6. Notice that here the result is a minimum, not a maximum; the method gave the stationary point and we checked it by comparing with other points on the line (for example x = 1, y = 0 gives 1, which is bigger than 0.5).

Example C: open-top box with fixed volume (substitution method). A square-based open box must hold 32 cubic units. Minimise the material area A = x squared + 4xh, where x is the base side and h is the height.

1. Volume constraint: x squared times h = 32, so h = 32 over x squared.
2. Substitute: A(x) = x squared + 128 over x.
3. Set the derivative to zero: 2x - 128 over x squared = 0, so x cubed = 64 and x = 4.
4. Then h = 32 over 16 = 2, and A = 16 + 32 = 48.
5. Check neighbours: x = 3 gives A about 51.7 and x = 5 gives A = 50.6, both larger than 48, so 48 is the minimum.
6. Lesson: when the constraint can be solved for one variable, substitution is just as valid; Lagrange multipliers become important when it cannot, or when you want the sensitivity lambda.

Example D: an inequality constraint. Minimise (x - 3) squared subject to x <= 1. The unconstrained minimum is x = 3, which is not allowed. So the constraint is active: the answer is x = 1 with value 4. Using the Lagrangian L = (x - 3) squared + mu (x - 1) with mu >= 0: setting the derivative to zero gives 2(x - 3) + mu = 0, so at x = 1 we get mu = 4 (positive, as required). Compare with a loose constraint, x <= 5: the minimum x = 3 is allowed, the constraint is inactive, and complementary slackness forces mu = 0.

7. Comparison tables

Table 1: unconstrained versus constrained

Property	Unconstrained	Equality constrained	Inequality constrained
Condition at the optimum	gradient of f is zero	gradient of f equals lambda times gradient of g, and g = c	KKT conditions
Multiplier sign	none	any real number	non-negative in the standard form
Extra variables	none	one multiplier per constraint	one multiplier per constraint, may be zero
Typical example	least squares	fence and area	SVM margin, weights norm at most r

Table 2: ways to handle constraints

Method	Idea	Pros	Cons
Substitution	solve constraint for one variable	simple, exact	only when the constraint can be solved
Lagrange multipliers	add multiplier variables	general, gives sensitivity	gives candidates only, more equations
KKT	multipliers plus slackness for inequalities	handles limits	need to check which constraints are active
Penalty (for example weight decay)	add cost for violating	easy with gradient descent	constraint only softly satisfied
Projected gradient descent	step then project back	keeps the constraint exactly	needs an easy projection

Table 3: reading the multiplier

Value of lambda	Meaning
large	the constraint is expensive; relaxing it would help a lot
near zero	the constraint hardly matters
exactly zero (inequality)	the constraint is inactive, there is slack
equals 5 in the fence story	one more metre of fence adds about 5 square metres

8. Common mistakes and myths

• Mistake: setting grad f = 0 and ignoring the constraint. For the fence, grad f = (y, x) is zero only at x = y = 0, which has area 0 and is useless.
• Mistake: forgetting the constraint equation. The gradient condition alone gives only x = y; you still need the fence length to find x = 10.
• Myth: "lambda is just a trick with no meaning." It is the shadow price: the sensitivity of the best value to the constraint.
• Mistake: assuming the stationary point is the maximum. It may be a minimum or a saddle; compare values or check second-order conditions.
• Mistake: sign errors with inequalities. In the standard minimisation form with h(x) <= 0, the multiplier must be non-negative. A negative multiplier means that constraint should not be active at the candidate.
• Myth: "the constraint is always tight." Only active constraints are; inactive ones have zero multiplier.
• Mistake: mixing up sign conventions between books and then thinking an answer of lambda = minus 5 is wrong; it may just be L = f + lambda g.
• Myth: "Lagrange multipliers are only for textbooks." They sit under SVMs, regularisation, maximum-entropy models and many optimisation libraries.
• Mistake: using the method with dependent constraints or at a point where the constraint gradient is zero.

9. Real-life and AI uses

• Support vector machines: the dual form uses one multiplier per training example; support vectors are the examples with non-zero multipliers.
• Regularisation: weight decay is the penalty version of limiting the size of the weights; the strength of the penalty plays the role of lambda.
• Projected gradient descent: used when parameters must stay in a set, such as non-negative weights, a ball of limited norm, or probabilities that sum to 1.
• Reinforcement learning: trust-region and constrained policy methods limit how much the policy may change per step.
• Probability and statistics: maximum-entropy distributions, normalisation constraints in mixture models.
• Economics and operations: maximise profit under a budget (lambda is the marginal value of money), production planning, portfolio selection.
• Engineering and physics: minimising material for a given volume, mechanics with constraints (the original use).
• Adversarial robustness: find the worst-case input inside a small allowed perturbation ball.

10. Self-check questions with answers

1. What is a constrained optimisation problem? Optimising an objective over only those inputs that satisfy given rules (constraints).
2. At the optimum of an equality-constrained problem, how do grad f and grad g relate? They are parallel: grad f = lambda grad g.
3. Why parallel? If they were not parallel, you could slide along the constraint curve in a direction that improves f, so you would not be at the optimum.
4. Write the Lagrangian for maximising xy with 2x + 2y = 40. L = xy - lambda (2x + 2y - 40).
5. Solve it. x = y = 10, lambda = 5, area 100.
6. What does lambda = 5 tell Leela? One extra metre of fence gains about 5 square metres; 41 metres gives 105.06, a gain of 5.06.
7. Solve: minimise x squared + y squared with x + y = 1. x = y = 0.5, lambda = 1, value 0.5.
8. What do KKT conditions add? Handling of inequality constraints: multipliers not negative, and complementary slackness (either the constraint is tight or its multiplier is zero).
9. How is weight decay related to constraints? Adding a penalty on the squared weight norm is the penalty form of constraining the weight norm; the penalty strength corresponds to the multiplier.
10. When is substitution better than multipliers? When the constraint can easily be solved for one variable, as with the box volume, since it reduces the problem to ordinary calculus.

11. Key takeaways, go deeper, next

Key takeaways

• A constraint limits which inputs you may choose; the best allowed point is usually not where the gradient is zero.
• At a constrained optimum the objective's gradient is a multiple (lambda) of the constraint's gradient.
• The Lagrangian combines both conditions into one function whose stationary points are the candidates.
• Lambda is the shadow price: how much the best value changes per unit relaxation of the constraint.
• Inequalities lead to KKT: non-negative multipliers and complementary slackness.
• In AI this shows up in SVMs, regularisation, projections and trust regions.

Go deeper

• Work through section 7.2 of Mathematics for Machine Learning and the SVM dual in section 12.3.
• Redo the fence problem with a different perimeter and check that lambda equals the area gain per metre.
• Read the constraints and projections part of the d2l.ai convexity chapter.
• Try minimising x squared + y squared + z squared on the plane x + y + z = 3 (by symmetry the solution is 1, 1, 1; verify with Lagrange).

Next on the roadmap: 1.31 Convex sets and functions.

12. Sources and further reading

• Deisenroth, Faisal and Ong, Mathematics for Machine Learning (2020), section 7.2 "Constrained Optimization and Lagrange Multipliers", section 7.3 "Convex Optimization", and section 12.3 "Dual Support Vector Machine". https://mml-book.github.io/book/mml-book.pdf
• Goodfellow, Bengio and Courville, Deep Learning (2016), chapter 4 "Numerical Computation", section 4.4 "Constrained Optimization" (feasible points, norm constraints, projected gradient descent, generalised Lagrangian and KKT). https://www.deeplearningbook.org
• Boyd and Vandenberghe, Convex Optimization (2004), chapter 5 "Duality", especially section 5.1 "The Lagrange dual function". https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf
• Zhang et al., Dive into Deep Learning, section 12.2 "Convexity" (constraints and the Lagrangian, penalties, projections). https://d2l.ai/chapter_optimization/convexity.html

Accuracy note: the numbers in the examples (areas, lambda, the 41 metre check, the x + y = 1 and box examples) were verified with Python on 2026-11-03; the historical remarks and the sign-convention commentary are standard background rather than drawn from the pages listed above.