Skip to content
LearnMLByDoing
Free

1.4 Convexity, Lagrange multipliers and duality

34 minProadvancedMMLStrangBoydESLCompendium

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 CC is convex if the segment between any two of its points stays inside it: a,b∈Ca,b\in C implies θa+(1−θ)b∈C\theta a+(1-\theta)b\in C for every θ∈[0,1]\theta\in[0,1]. Balls ∥w∥≤t\|w\|\le t in any norm, half-spaces a⊤w≤ca^\top w\le c, affine sets {w:Aw=b}\{w: Aw=b\} and every intersection of convex sets are convex. A circle ∥w∥2=t\|w\|_2=t 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:

f(θa+(1−θ)b)  ≤  θf(a)+(1−θ)f(b),θ∈[0,1]\tok{objective}{f}\big(\theta a+(1-\theta)b\big)\;\le\;\tok{chord}{\theta f(a)+(1-\theta)f(b)},\qquad \theta\in[0,1]
The chord definition. With strict inequality for a ≠ b and 0 < θ < 1, f is strictly convex.

Try it in one dimension first. Drag the endpoints aa and bb along the curve and slide θ\theta: on x2x^2, ∣x∣|x| and exe^x the gap between chord and curve never turns negative. Switch to the double well x4−2x2x^4-2x^2 and put aa and bb on either side of the hump at 0 (try a=−1a=-1, b=1b=1): the chord lies flat at −1-1 while the curve rises to 00 between them, and the gap turns rose.

Loading figure
The strip under the axis is the sign of f′′f'': wherever it is rose the curve bends down there, and a chord across that region can dip below the curve.

The viewport draws the convex bowl f(w)=0.22w12+0.12w1w2+0.3w22f(w)=0.22w_1^2+0.12w_1w_2+0.3w_2^2, with height proportional to ff so the drawn chord is the inequality itself. Two emerald points drift over the surface; the white curve is ff 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: ff is convex exactly when its restriction θ↦f(a+θ(b−a))\theta\mapsto f(a+\theta(b-a)) to every line is a convex function of one variable. Equivalently, the region on and above the graph, the epigraph {(w,s):s≥f(w)}\{(w,s): s\ge f(w)\} ("epi" means above: every point at height ss at least f(w)f(w)), 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: ff is convex if and only if every tangent plane lies below the graph, f(y)≥f(x)+∇f(x)⊤(y−x)f(y)\ge f(x)+\tok{grad_f}{\nabla f(x)}^\top(y-x) for all x,yx,y. Hover ∇f\nabla f to draw the tangent plane at the moving point. Second order: a twice-differentiable ff is convex if and only if its Hessian is positive semi-definite everywhere, ∇2f(x)⪰0\tok{hessian}{\nabla^2 f}(x)\succeq0. Positive semi-definite (written ⪰0\succeq0) means every eigenvalue is ≥0\ge0 (lesson 1.1): the surface curves up, or stays flat, along every direction through xx; it is the matrix version of f′′≥0f''\ge0 in the strip under the widget above. For the bowl of the previous step the Hessian is the constant [0.440.120.120.6]\begin{bmatrix}0.44&0.12\\0.12&0.6\end{bmatrix} with eigenvalues 0.3760.376 and 0.6640.664.

The viewport now shows a tilted double well, f(w)=0.08(w12−4)2+0.25w1+0.3w22f(w)=0.08(w_1^2-4)^2+0.25w_1+0.3w_2^2. Its Hessian is diag⁡(0.96w12−1.28, 0.6)\operatorname{diag}(0.96w_1^2-1.28,\ 0.6), which has a negative eigenvalue in the rose strip ∣w1∣<1.155|w_1|<1.155. 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 ∇f=0\nabla f=0: the global minimum (−2.091, 0)(-2.091,\,0) with f=−0.512f=-0.512, a saddle (0.197, 0)(0.197,\,0) with f=1.305f=1.305 and Hessian eigenvalues −1.243-1.243 and 0.60.6, and a local minimum (1.894, 0)(1.894,\,0) with f=0.487f=0.487.

For a convex f, every local minimum is global1/4
  1. 1
    f(wˉ)≤f(w)  for all ∥w−wˉ∥≤r,and suppose f(y)<f(wˉ)f(\bar w)\le f(w)\ \ \text{for all } \|w-\bar w\|\le r,\qquad\text{and suppose } f(y)<f(\bar w)

    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 w⋆\tok{xstar}{w^\star} to release four balls that follow −∇f-\nabla f: the two that start left of the saddle reach the global minimum, the two that start right of it stop in the local minimum, 0.9990.999 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, f(w)=12(w−w^)⊤H(w−w^)\tok{objective}{f}(w)=\tfrac12(w-\hat w)^\top H(w-\hat w) with unconstrained minimiser w^=(0.9, −2.0)\hat w=(0.9,\,-2.0). HH has eigenvalue 0.250.25 along the long axis of the contours, which points at φ=30∘\varphi=30^\circ, and 11 across it. The cyan circle is the constraint g(w)=w12+w22−t2=0\tok{constraint}{g}(w)=w_1^2+w_2^2-t^2=0 with t=1.5t=1.5; w^\hat w is off the circle, at distance ∥w^∥2=2.193\|\hat w\|_2=2.193 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 θ\theta. Drag the point around the circle below and watch ff 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 f(θ)f(\theta) is zero.

Loading figure
Arrows show directions only (both drawn the same length). At the minimum, θ≈297∘\theta\approx297^\circ, the readouts give w=(0.681, −1.337)w=(0.681,\,-1.337), ∠(∇f,∇g)≈180∘\angle(\nabla f,\nabla g)\approx180^\circ and λ=0.228\lambda=0.228; at the maximum, θ≈119∘\theta\approx119^\circ, the angle is about 0∘0^\circ and λ=−1.227\lambda=-1.227. The widget follows the cockpit's tt and φ\varphi.

At a constrained minimum, moving along the circle cannot lower ff to first order. The tangent of the circle is perpendicular to ∇g\nabla g, so ∇f\nabla f must be perpendicular to that tangent as well: the two gradients are parallel, and the level set of ff through the point touches the circle instead of crossing it.

Warm-up with friendly numbers. Minimise f(x,y)=x2+y2f(x,y)=x^2+y^2 (the squared distance to the origin) subject to x+y=1x+y=1, so g(x,y)=x+y−1g(x,y)=x+y-1. Parallel gradients means ∇f=(2x, 2y)\nabla f=(2x,\,2y) is a multiple of ∇g=(1, 1)\nabla g=(1,\,1): 2x+λ=02x+\lambda=0 and 2y+λ=02y+\lambda=0. So x=yx=y, and the constraint gives x=y=12x=y=\tfrac12, λ=−1\lambda=-1 and p⋆=14+14=12p^\star=\tfrac14+\tfrac14=\tfrac12. Check the price interpretation of the callout below: with the constraint x+y=bx+y=b the optimum is x=y=b/2x=y=b/2 and p⋆=b2/2p^\star=b^2/2, whose slope at b=1b=1 is 1=−λ1=-\lambda. Three equations, three unknowns, no geometry needed; the derivation shows why it always works.

From tangency to the Lagrangian1/4
  1. 1
    ∇g(w)⊤d=0⇒f(w+ϵd)≈f(w)+ϵ ∇f(w)⊤d\nabla g(w)^\top d=0\quad\Rightarrow\quad f(w+\epsilon d)\approx f(w)+\epsilon\,\nabla f(w)^\top d

    d is a direction tangent to the constraint; to first order, moving along it changes f by the directional derivative.

KKT matrix[,]

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 (−0.728, 1.311)(-0.728,\,1.311) and is pushed along the circle by the tangential part of ∇f\nabla f; the emerald ellipse is the level set through it. While the point moves, that ellipse crosses the circle and the angle between the amber ∇f\nabla f and the cyan ∇g\nabla g is not 180∘180^\circ. The point settles at w⋆=(0.681, −1.336)w^\star=(0.681,\,-1.336), where the ellipse is tangent to the circle, the arrows are anti-parallel, f=0.2365f=0.2365 and λ=−∇f⊤∇g/∥∇g∥2=0.228\lambda=-\nabla f^\top\nabla g/\|\nabla g\|^2=0.228. Hover λ\lambda to redraw the cyan arrow as λ∇g\lambda\nabla g: at w⋆w^\star it exactly cancels ∇f\nabla f.

Grow the circle past w^\hat w: set t=2.5t=2.5, larger than ∥w^∥2=2.193\|\hat w\|_2=2.193.

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.

Compiling scene

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