1.4 Convexity, Lagrange multipliers and duality
Convexity is what makes a local minimum global, a Lagrange multiplier is the price of a constraint, and the same geometry explains the SVM dual and why an L1 penalty sets weights exactly to zero.
01Convex sets and convex functions
Picture a disc and a crescent (a disc with a bite taken out). Pick any two points of the disc and the straight segment between them never leaves it; in the crescent, the segment between the two horns crosses the bite. That is the whole idea: a set is convex if the segment between any two of its points stays inside it: implies for every . Balls in any norm, half-spaces , affine sets and every intersection of convex sets are convex. A circle is not: the chord between two of its points runs through the inside.
A function is convex if its domain is convex and every chord of its graph lies on or above the graph:
Try it in one dimension first. Drag the endpoints and along the curve and slide : on , and the gap between chord and curve never turns negative. Switch to the double well and put and on either side of the hump at 0 (try , ): the chord lies flat at while the curve rises to between them, and the gap turns rose.
The viewport draws the convex bowl , with height proportional to so the drawn chord is the inequality itself. Two emerald points drift over the surface; the white curve is restricted to the segment between them and the straight emerald line is the chord. The ribbon between them stays emerald wherever the endpoints go, and the HUD's min chord − f never drops below 0.
The white curve is the key to the definition: is convex exactly when its restriction to every line is a convex function of one variable. Equivalently, the region on and above the graph, the epigraph ("epi" means above: every point at height at least ), is a convex set: a bowl you could fill with water without it spilling over a ridge.
Convex Optimization, Boyd & Vandenberghe, Sec. 2.1 to 2.3 and 3.1
Mathematics for Machine Learning, Deisenroth, Faisal & Ong, Sec. 7.3, convex sets and functions
02Curvature tests, and why every local minimum is global
For differentiable functions two tests replace the chord definition. First order: is convex if and only if every tangent plane lies below the graph, for all . Hover to draw the tangent plane at the moving point. Second order: a twice-differentiable is convex if and only if its Hessian is positive semi-definite everywhere, . Positive semi-definite (written ) means every eigenvalue is (lesson 1.1): the surface curves up, or stays flat, along every direction through ; it is the matrix version of in the strip under the widget above. For the bowl of the previous step the Hessian is the constant with eigenvalues and .
The viewport now shows a tilted double well, . Its Hessian is , which has a negative eigenvalue in the rose strip . The chord turns rose whenever its endpoints sit on opposite sides of the strip, because it then passes under the hump. Three critical points have : the global minimum with , a saddle with and Hessian eigenvalues and , and a local minimum with .
- 1
Take a local minimum w̄ with neighbourhood radius r > 0, and assume some point y is strictly better.
The double well breaks the argument at step 3: the chord from the local minimum toward the global one passes below the hump. Hover to release four balls that follow : the two that start left of the saddle reach the global minimum, the two that start right of it stop in the local minimum, higher, with zero gradient and no local signal that anything better exists.
Convex Optimization, Boyd & Vandenberghe, Sec. 3.1.3, 3.1.4 and 4.2.2
Mathematics for Machine Learning, Deisenroth, Faisal & Ong, Sec. 7.3
03Equality constraints and Lagrange multipliers
From here on the objective is a least-squares bowl, with unconstrained minimiser . has eigenvalue along the long axis of the contours, which points at , and across it. The cyan circle is the constraint with ; is off the circle, at distance from the origin.
A constraint turns a 2-D search into a 1-D one: on the circle, the only freedom left is the angle . Drag the point around the circle below and watch along the way on the right. The lowest point of that curve is the constrained minimum, the highest is the constrained maximum, and at both the slope of is zero.
At a constrained minimum, moving along the circle cannot lower to first order. The tangent of the circle is perpendicular to , so must be perpendicular to that tangent as well: the two gradients are parallel, and the level set of through the point touches the circle instead of crossing it.
Warm-up with friendly numbers. Minimise (the squared distance to the origin) subject to , so . Parallel gradients means is a multiple of : and . So , and the constraint gives , and . Check the price interpretation of the callout below: with the constraint the optimum is and , whose slope at is . Three equations, three unknowns, no geometry needed; the derivation shows why it always works.
- 1
d is a direction tangent to the constraint; to first order, moving along it changes f by the directional derivative.
n variables and m equality constraints. It is symmetric but indefinite (it has m negative eigenvalues), so solve it with a general solver such as np.linalg.solve, not a Cholesky factorisation.
The emerald point starts just past the constrained maximum and is pushed along the circle by the tangential part of ; the emerald ellipse is the level set through it. While the point moves, that ellipse crosses the circle and the angle between the amber and the cyan is not . The point settles at , where the ellipse is tangent to the circle, the arrows are anti-parallel, and . Hover to redraw the cyan arrow as : at it exactly cancels .
Grow the circle past : set , larger than .
Mathematics for Machine Learning, Deisenroth, Faisal & Ong, Sec. 7.2, constrained optimization and Lagrange multipliers
Convex Optimization, Boyd & Vandenberghe, Sec. 5.1, 5.5.3 and 10.1, the KKT system
The rest of this lesson is in Pro
- 04Inequality constraints and the KKT conditions
- 05Duality: a lower bound from the Lagrangian
- 06L1 and L2 regularisation as constraints: why L1 gives zeros
- 07Convex problems in ML, and the deep nets that are not
- Python challenge: Solve constrained problems: KKT systems and projections
- Knowledge check, 4 questions
Pro opens all 45 lessons, every graded Python challenge and the full 3D labs.
The Python challenge and knowledge check for this lesson are part of Pro.
Questions learners ask
- What does a Lagrange multiplier mean?
- At the solution of a constrained problem the gradient of the objective is balanced by the gradient of the constraint, and the multiplier is the balancing weight. It also measures sensitivity: it is the rate at which the optimal objective improves when the constraint is relaxed by one unit, which is why economists call it a shadow price. A multiplier of zero means the constraint is not limiting the solution.
- Why does L1 regularization produce sparse models but L2 does not?
- Written as a constraint, L1 regularization restricts the weights to a diamond whose corners lie on the coordinate axes, while L2 restricts them to a round ball. The solution is where the smallest reachable contour of the loss first touches the set. A corner touches for a whole range of contour orientations, and at a corner some weights are exactly zero. A round ball has no corners, so its touching point lands on an axis only by coincidence and L2 shrinks weights without zeroing them.
- What is convex optimization and why does it matter in machine learning?
- A problem is convex when the objective is a convex function and the feasible set is a convex set. Then every local minimum is a global minimum, gradient-based solvers cannot get trapped, and duality gives a certificate of how close a solution is to optimal. Least squares, ridge, lasso, logistic regression and support vector machines are convex. Neural networks are not, which is why their training depends on initialization, learning rate schedules and luck in ways the convex models do not.
Next in Mathematical Foundations
1.5Entropy, cross-entropy and KL divergenceSurprise, measured in bits: why cross-entropy is the classification loss, what KL divergence costs, and where mutual information shows up.Sources
- Mathematics for Machine Learning, Deisenroth, Faisal & Ong
- Introduction to Linear Algebra, Gilbert Strang
- Convex Optimization, Boyd & Vandenberghe
- The Elements of Statistical Learning, Hastie, Tibshirani & Friedman
- Maths, CS & AI Compendium, Henry Ndubuaku