The Math Behind the Machine/ Unit 11 · Optimization II Checks 0/20
Unit 11 of 16 · by Prof. Saurabh

Optimization II — Five Ways Down One Valley

Unit 10 fixed the ground: change the units and the canyon becomes a bowl. This unit fixes the walker. Your feet can feel the tilt where you stand — they cannot feel where the tilt is about to change, and that one blindness is why a single stride is always wrong for somebody. So we hand the walker three instincts: memory, so steps that agree stack up and steps that flip cancel; a private stride for every knob, learned from that knob's own history; and forgetting, so the history does not become a life sentence. Momentum, AdaGrad, RMSProp and Adam are those three instincts in four combinations, and you will watch all five walkers race the same valley above. Then we do the thing no amount of walking can survive: we build a wall. The answer moves onto the wall, the slope there is not zero, and every test you have learned stops working — so we build a new one.

≈ 110 min read + play 15 interactive widgets · 4 in 3D · a wall you can slide and price 20 inline checks 🧾 23 proofs, folded away — open "if you want the algebra" when you are ready ✍ 14 solved practice problems
drag the landscape to orbit
1

Your feet feel the tilt, not the turn

Walking a hill blindfolded

Blindfold yourself on a hillside. You can still feel one thing perfectly: how steeply the ground tilts under your boots. So you lean into the downhill direction and take a stride. Here is what your feet cannot tell you — how long that tilt lasts. A one-in-three slope that runs for fifty metres and a one-in-three slope that stops dead after five centimetres feel exactly the same underfoot. Take a long confident stride on the second one and you have walked off a ledge. Push the walker around and watch it happen:

Your feet feel the tilt, not the turnOne stride for two directions that differ ten-fold — and a cliff that the slope under your boot has no word for. Drag to orbit.

Try: set η=0.2\eta=0.2 on the valley tab and press ▶ — w2w_2 flips +1,−1,+1,…+1,-1,+1,\dots for ever while w1w_1 crawls; the per-step factor 1−10η1-10\eta is exactly −1-1.

drag the picture to orbit

0.1
12
—

J(w)=12w12+5w22J(\mathbf w)=\tfrac12 w_1^2+5w_2^2 has ∇J=(w1, 10w2)\nabla J=(w_1,\,10w_2): one step multiplies w1w_1 by 1−η1-\eta and w2w_2 by 1−10η1-10\eta. No single η\eta is right for both — below 0.20.2 the steep direction settles and the gentle one crawls; above it the steep one explodes. The second derivative would warn you, and costs d2d^2 numbers a step.

That is the honest limit of a gradient. A gradient is a local measurement: it reports the tilt at one point and says nothing about the next point. The information you actually wanted — how fast the tilt itself is changing — lives in the second derivatives, the Hessian, and that is a whole square table of numbers. For a model with a million knobs that is a trillion numbers per step. Nobody computes it.

So we are stuck with the tilt. Now look at the valley tab, where the same blindness costs you in a quieter way. The loss is J=12w12+5w22J=\tfrac12w_1^2+5w_2^2 — gentle along w1w_1, steep along w2w_2 — and the tilt at the start [1,1][1,1] reads (1, 10)(1,\,10). One direction pushes ten times harder than the other, and a single stride η\eta has to serve both. Multiply out what one step does to each coordinate on its own and the whole problem becomes arithmetic you can do in your head.

The realization

w1←(1−η) w1,w2←(1−10η) w2w_1\leftarrow(1-\eta)\,w_1,\qquad w_2\leftarrow(1-10\eta)\,w_2

Each direction is quietly multiplied by its own number every step, and the two numbers share one η\eta. At η=0.1\eta=0.1 the steep coordinate is annihilated in a single step (1−10η=01-10\eta=0) while the gentle one only shrinks by a tenth — it needs 44 steps to get within 1 % of zero. Raise η\eta to hurry it along and at η=0.2\eta=0.2 the steep factor hits exactly −1-1: w2w_2 flips +1,−1,+1,−1+1,-1,+1,-1 for ever, never diverging, never arriving. Past that it explodes. There is no η\eta that suits both. Not a bad choice of η\eta — no choice at all.

Unit 10 attacked that by rebuilding the landscape: standardise the columns, the ten-to-one becomes one-to-one, one stride fits everybody. That fix is real and it is the first thing to try. But it only reaches as far as your data does. The stiffness of a deep network comes from the layers, not just the inputs, and it drifts while you train. You cannot restandardise your way out of that.

So the rest of this act takes the other road. Leave the landscape alone. Change the walker. Everything that follows is one of three instincts bolted onto the same plain step — and each instinct is one line of arithmetic.

Pause & predict

On J=12w12+5w22J=\tfrac12w_1^2+5w_2^2 you set η=0.2\eta=0.2 exactly. What does the steep coordinate w2w_2 do?

If you want the algebra · 2 proofs, step by step
Prove it · one stride, one factor per direction

Claim. On J=12∑iλiwi2J=\tfrac12\sum_i\lambda_iw_i^2, one step of plain descent multiplies each coordinate by 1−ηλi1-\eta\lambda_i; the walk converges in every direction exactly when 0<η<2/λmax⁡0<\eta<2/\lambda_{\max}; and on J=12w12+5w22J=\tfrac12w_1^2+5w_2^2 at η=0.1\eta=0.1 the gentle coordinate needs 4444 steps to fall inside 1 %1\,\% of zero.

1
The gradient separates, because the loss does: ∂J/∂wi=λiwi\partial J/\partial w_i=\lambda_iw_i, with no other coordinate in it. A diagonal quadratic is dd one-dimensional problems wearing one coat. Everything below is a statement about one coordinate.
2
So one step is a multiplication: wi←wi−ηλiwi=(1−ηλi) wi,wi(k)=(1−ηλi)k wi(0).\begin{aligned}w_i&\leftarrow w_i-\eta\lambda_iw_i=(1-\eta\lambda_i)\,w_i,\\[2pt] w_i^{(k)}&=(1-\eta\lambda_i)^k\,w_i^{(0)}.\end{aligned} No approximation anywhere — this is the exact iterate after kk steps.
3
A geometric sequence shrinks to zero exactly when its ratio is strictly inside (−1,1)(-1,1): ∣1−ηλi∣<1  ⟺  0<ηλi<2  ⟺  0<η<2λi.|1-\eta\lambda_i|<1\iff 0<\eta\lambda_i<2\iff 0<\eta<\frac{2}{\lambda_i}. All directions survive only if the tightest bound holds, so η<2/λmax⁡\eta<2/\lambda_{\max}. The stiffest direction alone sets the speed limit. Every other direction is then travelling slower than it could.
4
Here λ=(1,10)\lambda=(1,10), so η<0.2\eta<0.2. At η=0.1\eta=0.1 the factors are 0.90.9 and 00: the steep coordinate is annihilated in one step, and for the gentle one 0.9 k≤0.01  ⟺  k≥ln⁡0.01ln⁡0.9=43.7 ⇒ k=44.0.9^{\,k}\le0.01\iff k\ge\frac{\ln 0.01}{\ln 0.9}=43.7\ \Rightarrow\ k=44. At η=0.2\eta=0.2 the second factor is exactly −1-1, so w2w_2 alternates ±1\pm1 for ever: no convergence, no divergence. ∎ One step for one coordinate, forty-four for the other, from the same η\eta. That ratio is the condition number κ=10\kappa=10.
Prove it · what your feet could not tell you, written down

Claim. If ∇f\nabla f does not change faster than a rate LL (that is, ∥∇f(u)−∇f(v)∥≤L∥u−v∥\|\nabla f(\mathbf u)-\nabla f(\mathbf v)\|\le L\|\mathbf u-\mathbf v\|), then one step guarantees f(w−η∇f)≤f(w)−η(1−ηL2)∥∇f∥2f(\mathbf w-\eta\nabla f)\le f(\mathbf w)-\eta\big(1-\tfrac{\eta L}{2}\big)\|\nabla f\|^2 — so progress is guaranteed exactly while η<2/L\eta<2/L, and is largest at η=1/L\eta=1/L.

1
A Lipschitz gradient bounds the Taylor remainder: for any u,v\mathbf u,\mathbf v, f(v)≤f(u)+∇f(u) ⁣⊤(v−u)+L2∥v−u∥2.f(\mathbf v)\le f(\mathbf u)+\nabla f(\mathbf u)^{\!\top}(\mathbf v-\mathbf u)+\frac{L}{2}\|\mathbf v-\mathbf u\|^2. This is the only place the missing second-order information enters — as a worst case, not a measurement. LL is how sharply the tilt is allowed to turn.
2
Put v=w−η∇f(w)\mathbf v=\mathbf w-\eta\nabla f(\mathbf w) and u=w\mathbf u=\mathbf w, writing g=∇f(w)\mathbf g=\nabla f(\mathbf w): f(w−ηg)≤f(w)−η∥g∥2+Lη22∥g∥2=f(w)−η(1−ηL2)∥g∥2.\begin{aligned}f(\mathbf w-\eta\mathbf g)&\le f(\mathbf w)-\eta\|\mathbf g\|^2+\frac{L\eta^2}{2}\|\mathbf g\|^2\\ &=f(\mathbf w)-\eta\Big(1-\frac{\eta L}{2}\Big)\|\mathbf g\|^2.\end{aligned} The first correction pays you η∥g∥2\eta\|\mathbf g\|^2; the second charges you 12Lη2∥g∥2\tfrac12L\eta^2\|\mathbf g\|^2. One is linear in the stride, the other quadratic, so the charge wins eventually.
3
The bracket is positive exactly when η<2/L\eta<2/L, and η(1−ηL/2)\eta(1-\eta L/2) is largest at η=1/L\eta=1/L, where the guaranteed drop is ∥g∥2/(2L)\|\mathbf g\|^2/(2L). ∎ Read it as the blindfold argument, quantified: the safe stride is set by how fast the tilt can turn, and your feet never measured that. On a quadratic L=λmax⁡L=\lambda_{\max} and this reproduces the bound above.
In one sentence: A gradient tells you the tilt and nothing about how long it lasts, so one shared stride multiplies each direction by its own factor 1−ηλi1-\eta\lambda_i — and when those factors differ tenfold, no single stride can serve them all.
2

Momentum — give the walker mass

The loaded trolley

Swap the walker for a loaded supermarket trolley. Two things change at once. The trolley has a wonky wheel that jerks it left, then right, then left — and you barely notice, because a jerk one way followed by a jerk the other way cancels out in something heavy. And the trolley has a direction: once it is rolling down the aisle, every small push in that same direction adds to the roll, and it goes faster and faster. There is a price, and you know it already: at the till you cannot stop it. Roll the trolley down the same valley and watch both halves:

The loaded trolleyGive the walker mass: pushes that agree stack, pushes that alternate cancel — and the loss is allowed to rise on the way

Try: push β\beta to 0.970.97 and press ▶ — the trolley sails through the bottom twice before it settles, and the w1w_1 bars stack while the w2w_2 bars cancel.

0.9
0.1
14
—

v←βv−η∇J\mathbf v\leftarrow\beta\mathbf v-\eta\nabla J, w←w+v\mathbf w\leftarrow\mathbf w+\mathbf v. A push from kk steps ago still counts βk\beta^k, so a run of agreeing pushes sums to 1/(1−β)1/(1-\beta) times one push, and a run of alternating pushes very nearly cancels. Speed along the trough, quiet across it — at the price of an overshoot.

The panel of bars is the entire idea. Look at the two strips. Along the gentle direction w1w_1, every step's push points the same way, so the bars stack into one long bar — and the trolley moves further per step than the walker ever could. Along the steep direction w2w_2, the pushes alternate in sign, so the bars cancel and almost nothing survives. The trolley did not learn which direction was which. It simply added up recent pushes, and adding up is what separates a consistent direction from a flapping one.

Writing it down takes one extra vector. Call it the velocity v\mathbf v: it is what is left of the last move.

The realization

v←β v−α∇J,w←w+v,v0=0\mathbf v\leftarrow\beta\,\mathbf v-\alpha\nabla J,\qquad \mathbf w\leftarrow\mathbf w+\mathbf v,\qquad \mathbf v_0=\mathbf 0

"New move = a faded copy of the last move, plus a fresh downhill push." The dial β∈[0,1)\beta\in[0,1) is how much of the last move survives — the friction. At β=0\beta=0 you get the plain walker back, exactly. At β=0.9\beta=0.9, a direction that keeps getting the same push builds up until each step is 1/(1−β)=101/(1-\beta)=\mathbf{10} times the plain step, while a direction that keeps flipping cancels itself to nothing.

Now the price. Run the defaults and read the loss: 5.5→0.405→4.3095.5\to0.405\to\mathbf{4.309}. It went up. At step 1 the steep coordinate landed exactly on the floor, so its fresh push is zero — but the velocity still says "you were plunging, keep going", and it carries w2w_2 straight through the bottom to −0.9-0.9. That is not a bug and it is not a bad β\beta. It is a rolling object doing what rolling objects do. Momentum is not a method that lowers the loss every step; it is a method that lowers the loss over a stretch of steps, and pays for speed with overshoot on the way.

One warning the picture makes obvious: never set β≥1\beta\ge1. Friction is the only thing draining the extra energy out of the swing. With none, the trolley rings for ever or flies apart.

Pause & predict

After one momentum step the walker sits at w2=0w_2=0, exactly at the floor of the steep direction, where the fresh slope is 00. What does step 2 do to w2w_2?

Pause & predict

A direction receives the same gradient gg at every step. With β=0.9\beta=0.9 and stride α\alpha, how big does each step eventually become?

If you want the algebra · 2 proofs, step by step
Prove it · the speed-up is 1/(1−β)1/(1-\beta)

Claim. If a direction receives the same gradient gg at every step, momentum's step size rises from αg\alpha g to αg/(1−β)\alpha g/(1-\beta) — a factor of 1010 at β=0.9\beta=0.9.

1
Unroll the velocity from v0=0v_0=0 with gg fixed: v1=−αgv2=βv1−αg=−αg(1+β)vt=−αg (1+β+β2+⋯+β t−1).\begin{aligned}v_1&=-\alpha g\\ v_2&=\beta v_1-\alpha g=-\alpha g(1+\beta)\\ v_t&=-\alpha g\,(1+\beta+\beta^2+\cdots+\beta^{\,t-1}).\end{aligned} Each old push survives multiplied by β\beta once more, so the surviving copies form a geometric series.
2
Sum it. Since 0≤β<10\le\beta<1, ∑k=0t−1β k=1−β t1−β → t→∞  11−β,v∞=−αg1−β.\sum_{k=0}^{t-1}\beta^{\,k}=\frac{1-\beta^{\,t}}{1-\beta}\ \xrightarrow[\ t\to\infty\ ]{}\ \frac{1}{1-\beta},\qquad v_\infty=-\frac{\alpha g}{1-\beta}. At β=0.9\beta=0.9 the limit is 10αg10\alpha g, and the series is already at 0.90.9 of it by step 2222.
3
Now the other half. If the gradient alternates, g,−g,g,−g,…g,-g,g,-g,\dots, the same unrolling gives vt=−αg(1−β+β2−⋯ )→−αg/(1+β)v_t=-\alpha g(1-\beta+\beta^2-\cdots)\to-\alpha g/(1+\beta), which at β=0.9\beta=0.9 is 0.53 αg0.53\,\alpha g — about a twentieth of the consistent case. ∎ The ratio of the two limits is (1+β)/(1−β)=19(1+\beta)/(1-\beta)=19 at β=0.9\beta=0.9. That single number is why the bars stack in one strip and cancel in the other, and it also shows why β≥1\beta\ge1 is fatal: the first series stops converging.
Prove it · the two ways of writing momentum are the same rule

Claim. vt=βvt−1−α∇J(wt−1), wt=wt−1+vt\mathbf v_t=\beta\mathbf v_{t-1}-\alpha\nabla J(\mathbf w_{t-1}),\ \mathbf w_t=\mathbf w_{t-1}+\mathbf v_t is identical to wt=wt−1−α∇J(wt−1)+β(wt−1−wt−2)\mathbf w_t=\mathbf w_{t-1}-\alpha\nabla J(\mathbf w_{t-1})+\beta(\mathbf w_{t-1}-\mathbf w_{t-2}); and on J=12w12+5w22J=\tfrac12w_1^2+5w_2^2 with α=0.1,β=0.9\alpha=0.1,\beta=0.9 the first three points are [0.9,0][0.9,0], [0.72,−0.9][0.72,-0.9], [0.486,−0.810][0.486,-0.810].

1
From the second line, vt=wt−wt−1\mathbf v_t=\mathbf w_t-\mathbf w_{t-1} — the velocity is the last move. Shift the index: vt−1=wt−1−wt−2\mathbf v_{t-1}=\mathbf w_{t-1}-\mathbf w_{t-2}. Nothing has been assumed; this is just naming the same quantity twice.
2
Substitute into the first line: wt−wt−1=β(wt−1−wt−2)−α∇J(wt−1),\mathbf w_t-\mathbf w_{t-1}=\beta(\mathbf w_{t-1}-\mathbf w_{t-2})-\alpha\nabla J(\mathbf w_{t-1}), which rearranges to the second form exactly. So "keep a velocity" and "add β\beta times the last move" are the same instruction. Different books pick different halves; nothing changes.
3
Run it. ∇J=(w1,10w2)\nabla J=(w_1,10w_2), start [1,1][1,1], v0=0\mathbf v_0=\mathbf 0: v1=−0.1(1,10)=(−0.1,−1),w1=[0.9, 0]v2=0.9(−0.1,−1)−0.1(0.9,0)=(−0.18,−0.9),  w2=[0.72, −0.9]v3=0.9(−0.18,−0.9)−0.1(0.72,−9)=(−0.234,0.09),  w3=[0.486, −0.810]\begin{aligned}\mathbf v_1&=-0.1(1,10)=(-0.1,-1),\quad \mathbf w_1=[0.9,\ 0]\\[2pt] \mathbf v_2&=0.9(-0.1,-1)-0.1(0.9,0)=(-0.18,-0.9),\\ &\qquad\qquad\qquad\qquad\ \ \mathbf w_2=[0.72,\ -0.9]\\[2pt] \mathbf v_3&=0.9(-0.18,-0.9)-0.1(0.72,-9)=(-0.234,0.09),\\ &\qquad\qquad\qquad\qquad\ \ \mathbf w_3=[0.486,\ -0.810]\end{aligned} and JJ reads 5.5→0.405→4.3092→3.39865.5\to0.405\to4.3092\to3.3986. ∎ Step 2 is the overshoot in numbers: the fresh push on w2w_2 is zero and the memory carries it to −0.9-0.9. Step 3 is the return: the slope at w2=−0.9w_2=-0.9 is −9-9, so the fresh push finally turns it around.
In one sentence: Momentum adds a faded copy of the last move, so pushes that agree compound to 1/(1−β)1/(1-\beta) times the plain step and pushes that alternate cancel — bought with an overshoot, and a loss that is allowed to rise on the way down.
3

AdaGrad — a stride each, out of a permanent record

The permanent record

Momentum kept the one shared stride and added memory on top. AdaGrad goes at the real problem instead: it stops sharing. Every knob is issued a school report on its first day. Nothing about where it went — only how loud its pushes have been, added up as squares, from the beginning of time. A knob with a loud record gets gentle taps from now on. A knob with a quiet record keeps its full push. And the record is never cleared, which is the part that eventually costs.

The permanent recordKeep every squared slope you ever felt, and divide your stride by the square root of the total — a brake that never lifts

Try: read the first step on the two steps tab: 0.10000.1000 in both weights, although one slope is 11 and the other is 1010. Then open the long run and watch the stride die like α/t\alpha/\sqrt t.

12
0.1
—

A←A+g2A\leftarrow A+g^2, step =αg/A=\alpha g/\sqrt A. On step one αg/g2=α sign(g)\alpha g/\sqrt{g^2}=\alpha\,\mathrm{sign}(g): the size of the slope cancels exactly and only its direction survives — which is why the walker leaves [1,1][1,1] along the diagonal. AA never shrinks, so the stride can only fall.

Watch the first step, because it is the most surprising number in this unit. The steep knob felt a slope of 1010; the gentle one felt 11. Both move by exactly 0.10.1. The ten-to-one mismatch that broke the shared stride in §1 has simply disappeared, and nobody standardised anything.

The reason is one line of cancellation. On step 1 the record holds only that step's own square, so the square root of the record is the size of the slope, and dividing the slope by its own size leaves ±1\pm1.

The realization

A←A+∇J⊙∇J,w←w−αA⊙∇JA\leftarrow A+\nabla J\odot\nabla J,\qquad \mathbf w\leftarrow\mathbf w-\frac{\alpha}{\sqrt A}\odot\nabla J

with every operation done one entry at a time (⊙\odot means "multiply entry by entry"). On step 1, αg/g2=α sign(g)\alpha g/\sqrt{g^2}=\alpha\,\mathrm{sign}(g): only the sign of the slope survives. Its size decides nothing. Every knob takes a step of exactly α\alpha, and the only thing the gradient contributes is which way.

That is why AdaGrad's famous win is rare features. A word that appears in one document in ten thousand gives its weight a slope almost never, so its record stays tiny and its strides stay long. A word that appears everywhere is throttled. You get frequency-aware strides for nothing, without ever writing down what is rare.

Now the catch, and it is written into the update: AA is a running total. It only ever grows, so α/A\alpha/\sqrt A only ever shrinks, whether or not the knob has arrived. Two steps in, the stride is already down from 0.10.1 to 0.0669\mathbf{0.0669}. Open the long run tab and watch it trace α/t\alpha/\sqrt t — a curve that reaches zero, and reaches it whether or not you did. A shrinking step is a brake, not a convergence. AdaGrad routinely stops short of the bottom because it ran out of stride, not because it arrived.

Pause & predict

Two knobs start together. Knob A feels a slope of +0.1+0.1 at every step; knob B feels +100+100 then −100-100, alternating, for ever. After many steps, which one is AdaGrad still moving in long strides?

If you want the algebra · 2 proofs, step by step
Prove it · AdaGrad's first step is exactly α\alpha, whatever the slope

Claim. With A0=0A_0=0, the first AdaGrad step moves every coordinate by exactly α\alpha in the direction −sign(gi)-\mathrm{sign}(g_i).

1
After one update, Ai=0+gi2=gi2A_i=0+g_i^2=g_i^2, so Ai=∣gi∣\sqrt{A_i}=|g_i|. The record contains exactly one entry: this step's own square. Its root is therefore the size of this step's own slope.
2
The step is then α giAi=α gi∣gi∣=α sign(gi).\frac{\alpha\,g_i}{\sqrt{A_i}}=\frac{\alpha\,g_i}{|g_i|}=\alpha\,\mathrm{sign}(g_i). ∎ The size of the slope cancels against itself. Only its sign reaches the update — the direction is data, the distance is a constant you chose.
3
Check on the session's valley: ∇J([1,1])=(1,10)\nabla J([1,1])=(1,10), A=[1,100]A=[1,100], A=[1,10]\sqrt A=[1,10], step =0.1⋅[1/1, 10/10]=[0.1,0.1]=0.1\cdot[1/1,\ 10/10]=[0.1,0.1], so w(1)=[0.9,0.9]\mathbf w^{(1)}=[0.9,0.9]. The ten-to-one mismatch of §1 is gone on step one, with no standardisation and no knowledge of the landscape.
Prove it · why the record becomes a brake

Claim. On a constant slope gg, AdaGrad's step at time tt is α/t\alpha/\sqrt t; the total distance it can ever cover in TT steps grows only like 2αT2\alpha\sqrt T, so reaching a target distance DD costs about (D/2α)2(D/2\alpha)^2 steps.

1
With gg fixed, At=At−1+g2A_t=A_{t-1}+g^2 and A0=0A_0=0 give At=t g2A_t=t\,g^2, so At=t ∣g∣\sqrt{A_t}=\sqrt t\,|g|. A running total of identical squares is just tt copies of one square.
2
The step size is therefore α ∣g∣t ∣g∣=αt.\frac{\alpha\,|g|}{\sqrt t\,|g|}=\frac{\alpha}{\sqrt t}. The slope cancels at every step, not just the first. What remains depends only on how long you have been walking.
3
Add up the first TT steps and compare with an integral: ∑t=1Tαt ≈ α ⁣∫1T ⁣dtt=2α(T−1).\sum_{t=1}^{T}\frac{\alpha}{\sqrt t}\ \approx\ \alpha\!\int_1^{T}\!\frac{\mathrm dt}{\sqrt t}=2\alpha\big(\sqrt T-1\big). Setting that equal to DD gives T≈(D/2α+1)2T\approx(D/2\alpha+1)^2. ∎ The distance still grows without limit — AdaGrad is not stuck in theory. But it grows like T\sqrt T, so doubling the distance costs four times the steps, and in practice you run out of patience long before you run out of hill.
In one sentence: Divide each knob's stride by the square root of everything it has ever felt, and the first step becomes exactly α\alpha for every knob whatever its slope — at the cost of a record that never clears, so the brake never lifts.
4

RMSProp — form, not career average

Picking the side on form

No selector picks a side on career averages. They look at recent form — the last ten innings, with the latest counting most — because a bad patch from nine seasons ago tells you nothing about today. AdaGrad judges every knob on its career. RMSProp keeps the whole per-knob idea and changes one word: forget. The catch is the one every selector knows too. After a single innings, "recent form" is a wild number.

Form, not career averageForget the distant past at rate ρ\rho: the brake eases, the stride stays alive — and the very first step is puffed up by 1/1−ρ1/\sqrt{1-\rho}

Try: click ρ = 0.999 and watch the first step launch the walker clean off the map — the inflation 1/1−ρ1/\sqrt{1-\rho} has gone from 3.16×3.16\times to 31.6×31.6\times.

0.9
0.1
12
—

A←ρA+(1−ρ)g2A\leftarrow\rho A+(1-\rho)g^2 is a running average with a memory of about 1/(1−ρ)1/(1-\rho) steps. Starting it at zero makes the first average (1−ρ)g2(1-\rho)g^2, so the first stride is 1/1−ρ1/\sqrt{1-\rho} times too long. RMSProp never fixes that first step. Adam does — next section.

One line of AdaGrad changes. Instead of adding squares to a total for ever, keep a fading average: hold on to a share ρ\rho of what you had and let 1−ρ1-\rho of the new square in.

The realization

A←ρ A+(1−ρ) ∇J⊙∇J,w←w−αA⊙∇JA\leftarrow \rho\,A+(1-\rho)\,\nabla J\odot\nabla J,\qquad \mathbf w\leftarrow\mathbf w-\frac{\alpha}{\sqrt A}\odot\nabla J

A slope from tt steps ago is worth ρ t\rho^{\,t} of a fresh one — the memory comb in the widget is exactly that. As a rule of thumb the average remembers about the last 1/(1−ρ)1/(1-\rho) steps, which at ρ=0.9\rho=0.9 is ten. And because AA can now fall as well as rise, the brake can be released again. The stride never dies.

Compare the two stride curves in the third panel. AdaGrad's slides towards zero and stays there; RMSProp's settles at a healthy size and keeps working. On the session's valley the difference shows up fast: after two steps RMSProp's strides are 0.31620.3162 then 0.18490.1849, and the loss has fallen 5.5→2.57→1.375.5\to2.57\to1.37 while AdaGrad is still at 3.823.82.

But look at that first number again. 0.31620.3162 is three times α\alpha. Where did that come from? The average started at zero, so on step 1 it holds only (1−ρ)g2(1-\rho)g^2 — a tenth of the true size. Its square root is 0.1\sqrt{0.1} too small, and dividing by something too small makes the step too big, by exactly 1/1−ρ=3.161/\sqrt{1-\rho}=3.16. Set ρ=0.999\rho=0.999, as people often do, and the first step is 31.6 times what you asked for. RMSProp never fixes this. You just live through it — the average fills up within a few steps and the problem goes away on its own. The next method refuses to live through it.

Pause & predict

You raise the forgetting dial from ρ=0.9\rho=0.9 to ρ=0.99\rho=0.99. What happens to the very first step?

Pause & predict

A knob has been feeling the same slope gg for hundreds of steps. What does RMSProp's stride settle at, and what does AdaGrad's do?

If you want the algebra · 2 proofs, step by step
Prove it · a fading average converges, a running total does not

Claim. On a constant slope gg, RMSProp's accumulator is At=g2(1−ρ t)→g2A_t=g^2(1-\rho^{\,t})\to g^2, so its step size tends to α\alpha and never dies.

1
Unroll At=ρAt−1+(1−ρ)g2A_t=\rho A_{t-1}+(1-\rho)g^2 from A0=0A_0=0: At=(1−ρ)g2(1+ρ+ρ2+⋯+ρ t−1).A_t=(1-\rho)g^2\big(1+\rho+\rho^2+\cdots+\rho^{\,t-1}\big). Each old square is multiplied by ρ\rho once per step, which is what "fades as ρ t\rho^{\,t}" means.
2
Sum the geometric series and simplify: At=(1−ρ)g2⋅1−ρ t1−ρ=g2(1−ρ t) → t→∞  g2.A_t=(1-\rho)g^2\cdot\frac{1-\rho^{\,t}}{1-\rho}=g^2\big(1-\rho^{\,t}\big)\ \xrightarrow[\ t\to\infty\ ]{}\ g^2. The (1−ρ)(1-\rho) that scaled the new square is exactly cancelled by the (1−ρ)(1-\rho) in the denominator of the sum. The average converges to the thing being averaged — which is the whole point of an average.
3
So the step size is α∣g∣/(∣g∣1−ρ t)=α/1−ρ t→α\alpha|g|/\big(|g|\sqrt{1-\rho^{\,t}}\big)=\alpha/\sqrt{1-\rho^{\,t}}\to\alpha. Compare AdaGrad's α/t→0\alpha/\sqrt t\to0. ∎ Same slope, same α\alpha, two different fates: one method settles into a working stride, the other brakes itself to a stop. The only difference is whether the accumulator is a total or an average.
Prove it · the zero start inflates the first step by 1/1−ρ1/\sqrt{1-\rho}

Claim. RMSProp's first step is α/1−ρ\alpha/\sqrt{1-\rho} — 3.162 α3.162\,\alpha at ρ=0.9\rho=0.9 and 31.62 α31.62\,\alpha at ρ=0.999\rho=0.999.

1
Put t=1t=1 in the formula above: A1=g2(1−ρ)A_1=g^2(1-\rho), so A1=∣g∣1−ρ\sqrt{A_1}=|g|\sqrt{1-\rho}. The average is holding only a (1−ρ)(1-\rho) share of the true size, because the other ρ\rho share is still the zero it started from.
2
Hence α∣g∣A1=α∣g∣∣g∣1−ρ=α1−ρ.\frac{\alpha|g|}{\sqrt{A_1}}=\frac{\alpha|g|}{|g|\sqrt{1-\rho}}=\frac{\alpha}{\sqrt{1-\rho}}. At ρ=0.9\rho=0.9: α/0.1=3.1623 α\alpha/\sqrt{0.1}=3.1623\,\alpha, which is the 0.31620.3162 the widget prints at α=0.1\alpha=0.1. ∎ Dividing by a root that is too small makes the step too big, and the longer the memory the worse it is — the opposite of the intuition that more memory means more caution.
3
How long does it last? The inflation at step tt is 1/1−ρ t1/\sqrt{1-\rho^{\,t}}, which is within 1 %1\,\% of 11 once ρ t<0.02\rho^{\,t}<0.02, i.e. t>ln⁡(0.02)/ln⁡ρt>\ln(0.02)/\ln\rho — about 3737 steps at ρ=0.9\rho=0.9, but about 3 9003\,900 at ρ=0.999\rho=0.999. That is why the fix matters: at the popular ρ=0.999\rho=0.999 the "start-up transient" lasts thousands of steps.
In one sentence: Replace the permanent record with a fading one and the brake eases — the stride survives to the bottom — at the price of a first step puffed up by 1/1−ρ1/\sqrt{1-\rho}, because an average that starts at zero is a wild guess after one reading.
5

Adam — two notebooks and a probation period

The new analyst

A new analyst joins and starts two notebooks about a project. One records which way the decisions have been trending. The other records how big they have been running. On day two both notebooks are nearly empty, and a careful manager knows exactly what to do with a nearly-empty notebook: discount it. Not ignore it — discount it, heavily at first, less each week, until a year in the notebooks are full and can be read at face value. That discount is a number, it shrinks the analyst's authority on purpose, and it retires itself.

Two notebooks and a probationOne book remembers which way; one remembers how loud. A shrinking rate covers the first few steps while both books are still nearly empty — then retires itself.

Try: step tt from 1 to 12 and watch αt\alpha_t fall to its minimum 0.0152240.015224, then keep going — it climbs back toward α=0.1\alpha=0.1 on its own.

1
0.9
0.999
—
—

F←ρfF+(1−ρf)gF\leftarrow\rho_f F+(1-\rho_f)g, A←ρA+(1−ρ)g2A\leftarrow\rho A+(1-\rho)g^2, and the step is αtF/A\alpha_t F/\sqrt A with αt=α1−ρ t/(1−ρf t)\alpha_t=\alpha\sqrt{1-\rho^{\,t}}/(1-\rho_f^{\,t}). Count tt from 0 instead of 1 and 1−ρf0=01-\rho_f^0=0: the rate divides by zero on the very first step. That is the classic bug.

You have already met both notebooks. The direction notebook is momentum, written as a fading average instead of a running velocity. The loudness notebook is RMSProp. Adam keeps both, one per knob, and divides the first by the root of the second.

The realization

F←ρfF+(1−ρf)∇J,A←ρA+(1−ρ)∇J⊙∇J,w←w−αt FAF\leftarrow \rho_f F+(1-\rho_f)\nabla J,\qquad A\leftarrow \rho A+(1-\rho)\nabla J\odot\nabla J,\qquad \mathbf w\leftarrow\mathbf w-\alpha_t\,\frac{F}{\sqrt A}

αt=α 1−ρ t1−ρf t\alpha_t=\alpha\,\frac{\sqrt{1-\rho^{\,t}}}{1-\rho_f^{\,t}}

The step is average direction divided by root average loudness. The numerator averages signed slopes, so slopes that disagree cancel; the denominator averages squares, which cannot cancel. A knob being pushed consistently gets a ratio near ±1\pm1; a knob being shaken about gets a ratio near zero. Noise is throttled automatically, and nothing had to detect it.

Now the probation rate. Both notebooks start empty, so after tt steps FF has filled to only a share 1−ρf t1-\rho_f^{\,t} of full and AA to 1−ρ t1-\rho^{\,t}. Correct each by its own share, put the corrected pair into an RMSProp-shaped step, and everything cancels except one leftover factor — and that leftover factor is αt\alpha_t. Only AA sits under a root, so only its correction picks up a square root. That is the whole derivation, and it is folded into the drawer below.

What it buys is visible in one number. Drag the step slider to t=1t=1: the stride is exactly 0.10.1 in both knobs. RMSProp's 0.31620.3162 spike is gone, and AdaGrad's early fade never happens. Watch αt\alpha_t on the log axis: it starts at 0.03160.0316, dips to a minimum of 0.0152240.015224 at t=12t=12 — the two notebooks fill at different speeds, so the correction is not monotone — and then climbs back to the plain α=0.1\alpha=0.1 and stays there. The scaffolding comes down by itself.

Two practical notes. Libraries call (ρf,ρ)(\rho_f,\rho) by the names (β1,β2)(\beta_1,\beta_2), with the same defaults 0.90.9 and 0.9990.999. And count tt from 11: at t=0t=0 the denominator 1−ρf 01-\rho_f^{\,0} is zero and the whole rate blows up. That off-by-one is one of the most-committed bugs in machine learning.

Pause & predict

A knob's slope alternates +4,−4,+4,−4,…+4,-4,+4,-4,\dots while another knob's stays steady at +4+4. Both use Adam. Which one takes the bigger steps, and why?

If you want the algebra · 2 proofs, step by step
Prove it · where Adam's probation rate αt\alpha_t comes from

Claim. Correcting both zero-started averages for how full they are turns the RMSProp step into αt F/A\alpha_t\,F/\sqrt A with αt=α1−ρ t/(1−ρf t)\alpha_t=\alpha\sqrt{1-\rho^{\,t}}\big/(1-\rho_f^{\,t}) — the square root landing on the AA correction only.

1
A zero-started fading average of a constant cc reaches c(1−ρf t)c(1-\rho_f^{\,t}) after tt steps (the same geometric sum as §4). So FF is systematically short by exactly that factor, and the honest estimate is F^=F1−ρf t,A^=A1−ρ t.\widehat F=\frac{F}{1-\rho_f^{\,t}},\qquad \widehat A=\frac{A}{1-\rho^{\,t}}. This is a division by "how full the notebook is", nothing more. Each notebook fills at its own rate, so each gets its own correction.
2
Put the corrected pair into an RMSProp-shaped step and separate the constants from the raw averages: α F^A^=α F/(1−ρf t)A/1−ρ t=α 1−ρ t1−ρf t⏟αt⋅FA.\alpha\,\frac{\widehat F}{\sqrt{\widehat A}}=\alpha\,\frac{F/(1-\rho_f^{\,t})}{\sqrt{A}\big/\sqrt{1-\rho^{\,t}}}=\underbrace{\alpha\,\frac{\sqrt{1-\rho^{\,t}}}{1-\rho_f^{\,t}}}_{\textstyle \alpha_t}\cdot\frac{F}{\sqrt A}. ∎ The whole correction collapses into one scalar multiplying the uncorrected ratio — which is why implementations can keep the raw FF and AA and just scale the stride. And the square root sits only on AA's correction because only AA was under a root.
3
Limits and shape. As t→∞t\to\infty both ρ t\rho^{\,t} and ρf t\rho_f^{\,t} vanish, so αt→α\alpha_t\to\alpha. With the defaults ρf=0.9,ρ=0.999\rho_f=0.9,\rho=0.999, αt/α\alpha_t/\alpha reads 0.3162, 0.2353, 0.2020,…0.3162,\ 0.2353,\ 0.2020,\dots, dips to 0.152240.15224 at t=12t=12, then climbs back. Non-monotone, because the two notebooks fill at very different speeds — FF is nearly full by step 2020 while AA needs thousands. The correction is not a schedule somebody tuned; it is bookkeeping that retires itself.
Prove it · Adam's first step is exactly α\alpha per knob

Claim. At t=1t=1, Adam moves every coordinate by exactly α\alpha in the direction −sign(gi)-\mathrm{sign}(g_i) — RMSProp's 1/1−ρ1/\sqrt{1-\rho} spike is cancelled precisely.

1
At t=1t=1 the two notebooks hold one reading each: Fi=(1−ρf)gi,Ai=(1−ρ)gi2,Ai=1−ρ ∣gi∣.\begin{aligned}F_i&=(1-\rho_f)g_i,\qquad A_i=(1-\rho)g_i^2,\\[2pt] \sqrt{A_i}&=\sqrt{1-\rho}\,|g_i|.\end{aligned} Both are short by their own factor — and those are exactly the factors α1\alpha_1 is built from.
2
And α1=α1−ρ/(1−ρf)\alpha_1=\alpha\sqrt{1-\rho}\big/(1-\rho_f). Multiply: α1 FiAi=α 1−ρ1−ρf⋅(1−ρf) gi1−ρ ∣gi∣=α gi∣gi∣=α sign(gi).\begin{aligned}\alpha_1\,\frac{F_i}{\sqrt{A_i}}&=\alpha\,\frac{\sqrt{1-\rho}}{1-\rho_f}\cdot\frac{(1-\rho_f)\,g_i}{\sqrt{1-\rho}\,|g_i|}\\[2pt] &=\alpha\,\frac{g_i}{|g_i|}=\alpha\,\mathrm{sign}(g_i).\end{aligned} ∎ Every factor cancels — (1−ρf)(1-\rho_f) against (1−ρf)(1-\rho_f), 1−ρ\sqrt{1-\rho} against 1−ρ\sqrt{1-\rho}, ∣gi∣|g_i| against gig_i. What survives is the stride you asked for and the direction the data gave.
3
On the valley: F=[0.1,1]F=[0.1,1], A=[0.001,0.1]A=[0.001,0.1], A=[0.031623,0.31623]\sqrt A=[0.031623,0.31623], F/A=[3.1623,3.1623]F/\sqrt A=[3.1623,3.1623], α1=0.031623\alpha_1=0.031623, step =[0.1,0.1]=[0.1,0.1]. Compare RMSProp's [0.3162,0.3162][0.3162,0.3162] at the same point. Same landscape, same α\alpha, one method three times too eager and the other exactly right — because of one scalar.
In one sentence: Adam carries a signed memory and a squared memory per knob, steps by their ratio so that disagreement is thrown away and loudness is divided out, and wears a shrinking probation rate αt\alpha_t that makes the very first step exactly α\alpha and then retires itself.
6

Five walkers, one valley — and the dial that decides the race

A fair race

Same valley, same start [1,1][1,1], same stride α=0.1\alpha=0.1, five rules. Everything you are about to see comes from the update rule alone — no tuning, no tricks, no head start. Press play, then do the thing the race is really for: turn the stiffness dial and watch the result change shape.

Five walkers, one valleyThe same start, the same stride, five rules — and a stiffness dial that decides the race before it starts. Drag to orbit.

Try: drag stiffness to 300300 and press ▶ — the blue walker leaves the map while the other four barely blink.

drag the picture to orbit

10
0.1
0
—

J=12w12+c2w22J=\tfrac12 w_1^2+\tfrac c2 w_2^2. Plain descent is stable only while α<2/c\alpha<2/c; the adaptive methods divide by their own record of the slope and never notice cc at all. This race is tiny, clean and noiseless: take the mechanisms from it, not the finishing order — on a real network with noise and millions of weights the order can and does change.

At the lecture setting the story is already rich. Plain descent looks excellent — because α=0.1\alpha=0.1 happens to annihilate the steep direction in one step, which is luck, not skill. Momentum pays an early debt (the loss rises to 4.314.31 at step 2) and then rings its way down. AdaGrad evens the two directions immediately and then loses its stride. RMSProp reaches the floor first and by a distance. Adam walks a steady α\alpha-sized pace, rolls through the bottom around step eleven because it still carries momentum, and swings back.

Methodw(1)\mathbf w^{(1)}w(2)\mathbf w^{(2)}JJ after 2JJ after 25
Gradient descent[0.9, 0][0.9,\ 0][0.81, 0][0.81,\ 0]0.32810.00258
Momentum[0.9, 0][0.9,\ 0][0.72, −0.9][0.72,\ -0.9]4.30920.196
AdaGrad[0.9, 0.9][0.9,\ 0.9][0.8331, 0.8331][0.8331,\ 0.8331]3.81730.547
RMSProp[0.6838, 0.6838][0.6838,\ 0.6838][0.4989, 0.4989][0.4989,\ 0.4989]1.36883.6×10−133.6\times10^{-13}
Adam[0.9, 0.9][0.9,\ 0.9][0.8004, 0.8004][0.8004,\ 0.8004]3.52360.179

Now do not crown a winner. This valley is tiny, clean, noiseless, only ten-to-one stiff, and the stride was chosen to suit it. Change any one of those and the order changes. That is not a weakness of the demo — it is the demo, and the dial is how you see it.

Push stiffness to c=300c=300 with the same α=0.1\alpha=0.1. Plain descent is now outside its own safety limit and leaves the map inside five steps; so does momentum, which inherits that limit and adds energy to it. The two adaptive methods do not notice. Drop α\alpha to 0.0050.005 to rescue descent and it survives — and now crawls, because the stride that keeps the stiff direction stable is far too small for the gentle one. That is §1's impossible choice returning at scale.

The realization

plain descent needsα<2λmax⁡,and progress along λmin⁡ costsλmax⁡λmin⁡=κ  times more steps.\begin{aligned}\text{plain descent needs}\quad &\alpha<\frac{2}{\lambda_{\max}},\\[2pt] \text{and progress along }\lambda_{\min}\text{ costs}\quad &\frac{\lambda_{\max}}{\lambda_{\min}}=\kappa\ \text{ times more steps.}\end{aligned}

The safe window for the shared stride is set by the stiffest direction; the number of steps is set by the softest. Their ratio is the condition number κ\kappa, and it is the tax that plain descent pays and the adaptive methods refuse to. AdaGrad, RMSProp and Adam all divide by a measurement of the slope's own size, so the size never reaches the stride — they cannot see κ\kappa at all.

That is the honest reason Adam and its cousin AdamW are the default for transformers and large language models. At that scale, slope sizes differ across layers by orders of magnitude, they drift while training, and the readings are noisy mini-batch estimates. Nobody is going to hand-tune a stride per layer. A method that self-scales, smooths and starts fairly is the practical pick — not because it wins a race on a two-knob toy, but because it never needed the race to be fair.

Pause & predict

You make the valley a hundred times stiffer (λmax⁡\lambda_{\max} up by 100×100\times) and leave everything else alone. What happens to plain gradient descent's largest usable stride?

Pause & predict

On the same stiffer valley, why do AdaGrad, RMSProp and Adam keep working without you touching α\alpha?

If you want the algebra · 1 proof, step by step
Prove it · the best shared stride, and the price of a bad condition number

Claim. On J=12∑λiwi2J=\tfrac12\sum\lambda_iw_i^2 the stride that minimises the worst per-step factor is η⋆=2λmin⁡+λmax⁡\eta^\star=\dfrac{2}{\lambda_{\min}+\lambda_{\max}}, and at that stride every coordinate shrinks by at best κ−1κ+1\dfrac{\kappa-1}{\kappa+1} per step, where κ=λmax⁡/λmin⁡\kappa=\lambda_{\max}/\lambda_{\min}.

1
From the first drawer, coordinate ii is multiplied by 1−ηλi1-\eta\lambda_i each step, so after kk steps the worst-behaved coordinate governs: r(η)=max⁡i∣1−ηλi∣=max⁡{∣1−ηλmin⁡∣, ∣1−ηλmax⁡∣}.\begin{aligned}r(\eta)&=\max_i\big|1-\eta\lambda_i\big|\\[2pt] &=\max\big\{|1-\eta\lambda_{\min}|,\ |1-\eta\lambda_{\max}|\big\}.\end{aligned} The maximum over an interval of λ\lambda is attained at an end, because ∣1−ηλ∣|1-\eta\lambda| is a V in λ\lambda.
2
As η\eta grows, 1−ηλmin⁡1-\eta\lambda_{\min} falls from 11 and ∣1−ηλmax⁡∣|1-\eta\lambda_{\max}| eventually rises. The maximum of a falling and a rising curve is smallest where they cross: 1−ηλmin⁡=−(1−ηλmax⁡) ⟹ η⋆=2λmin⁡+λmax⁡.1-\eta\lambda_{\min}=-(1-\eta\lambda_{\max})\ \Longrightarrow\ \eta^\star=\frac{2}{\lambda_{\min}+\lambda_{\max}}. At the best stride the softest direction creeps forward and the stiffest one flips sign every step by the same fraction. Optimal does not mean pretty.
3
Substitute back: r(η⋆)=1−2λmin⁡λmin⁡+λmax⁡=λmax⁡−λmin⁡λmax⁡+λmin⁡=κ−1κ+1.r(\eta^\star)=1-\frac{2\lambda_{\min}}{\lambda_{\min}+\lambda_{\max}}=\frac{\lambda_{\max}-\lambda_{\min}}{\lambda_{\max}+\lambda_{\min}}=\frac{\kappa-1}{\kappa+1}. ∎ At κ=1\kappa=1 the rate is 00: one step and you are done. At κ=10\kappa=10 it is 9/11=0.8189/11=0.818 and you need ≈23\approx23 steps per decimal place. At κ=1000\kappa=1000 it is 0.9980.998 and you need ≈1150\approx1150. That curve is the whole reason the adaptive family exists.
In one sentence: Plain descent's safe stride is set by the stiffest direction and its speed by the softest, so it pays the condition number in steps — while every adaptive method divides the slope by a record of its own size, and so never sees the condition number at all.
7

Then someone builds a wall

A problem you can do in your head

Find the smallest value of f(x)=x2f(x)=x^2 — but you may only pick x≥2x\ge2. Do it now, before reading on. The bowl bottoms at x=0x=0, that point is banned, so you slide as close to it as the rule lets you and stop at x=2x=2, where f=4f=4. It took three seconds, and you just broke every method in this course. At x=2x=2 the slope of ff is 44. Not zero. Four. Every technique you have — set the derivative to zero, walk until the tilt vanishes, check the Hessian — is hunting for a flat spot that is not there.

Then someone builds a wallThe old test — "stop where the slope is zero" — stops being true the moment the answer is pressed against something

Try: slide the wall from c=−1c=-1 up past 00 on the first tab and watch the slope readout flip from 00 to 2c2c: the answer stops being flat, and there is still nowhere better to go.

2
—

Standard form is one shape: minimise ff subject to gi(x)≤0g_i(\mathbf x)\le 0 and hj(x)=0h_j(\mathbf x)=0. Every rule is pushed into it — a ≥\ge is multiplied by −1-1, an == is kept as it is (or split into two ≤\le), and a strict << is simply not allowed, because a set with no smallest allowed value has no answer to find.

Slide the wall and watch the readout flip. While the wall sits at c≤0c\le0 it is not in your way: the free answer survives and the slope there is zero, the old world. The instant c>0c>0 three things happen at once, and they happen in almost every constrained problem you will ever meet.

One: the free answer is thrown away. The rule did not adjust the answer, it replaced it. Two: the new answer sits exactly on the edge of the allowed set, not comfortably inside it. Three: the gradient at the answer is not zero, and it points straight into the wall — which is precisely why you cannot move.

Point three is the whole reason this half of the unit exists. We need a new test for "I have arrived", one that says: the slope is nonzero, but every direction that would use it is blocked.

Before we can build that test, everything has to be written in one shape. Open the standard form tab. Two mechanical moves do it. A ≥\ge becomes a ≤\le by multiplying through by −1-1. Everything else moves to the left of the sign.

The realization

min⁡x f(x)subject toe(x)=0,gi(x)≤0,  i=1,…,m\min_{\mathbf x}\ f(\mathbf x)\qquad\text{subject to}\qquad e(\mathbf x)=0,\qquad g_i(\mathbf x)\le0,\ \ i=1,\dots,m

Three roles, and this unit gives each a name you can picture. ff is the score — the number you want small. e=0e=0 is the path — a line you must sit exactly on. Each gi≤0g_i\le0 is a fence — a wall you must stay behind. So x≥2x\ge2 is written g=2−x≤0g=2-x\le0, and its gradient is ∇g=−1\nabla g=-1. Keep that minus sign. More answers are lost to that sign than to any other step in the topic.

One last piece of the shape, and it looks like pedantry until you try to break it. You will never see a strict <<. Try to minimise f(x)=xf(x)=x subject to x>2x>2. Is 2.12.1 the answer? No — 2.012.01 is allowed and smaller. Is 2.012.01? No. You can keep going for ever, getting closer to 22 without ever being allowed to reach it. The problem has no answer at all. Including the boundary is what makes the answer exist — and since the answer almost always sits on the boundary, a form that excluded it would throw away the thing we came for.

Pause & predict

Minimise f(x)=(x−5)2f(x)=(x-5)^2 subject to x≤1x\le1. Where is the answer, and what is the slope there?

If you want the algebra · 1 proof, step by step
Prove it · a strict inequality can leave a problem with no answer

Claim. min⁡x\min x subject to x>2x>2 has infimum 22 and no minimiser; replacing >> by ≥\ge makes the answer exist, at x=2x=2.

1
Every feasible xx satisfies x>2x>2, so 22 is a lower bound for the objective. A lower bound always exists here; the question is whether anything attains it.
2
Suppose some feasible x0x_0 were the minimum. Then x0>2x_0>2, so the midpoint x1=x0+22x_1=\tfrac{x_0+2}{2} satisfies 2<x1<x02<x_1<x_0: it is feasible and strictly better. The assumption defeats itself, and it does so for any candidate — there is no special point where the argument fails.
3
So no feasible point is minimal: the infimum 22 is approached (2.1,2.01,2.001,…2.1,2.01,2.001,\dots) and never reached. With x≥2x\ge2 the point x=2x=2 is feasible and clearly optimal. ∎ This is not pedantry, because constrained answers usually sit on the boundary. A form that excluded the boundary would throw away the answer in the typical case, not the exceptional one.
In one sentence: Put a wall in a problem and the answer moves onto the wall, where the gradient is not zero — so "stop where the slope vanishes" has to be replaced, and the replacement starts by writing everything as min⁡f\min f with e=0e=0 and gi≤0g_i\le0.
8

Pushing a box against a wall

The corridor

Push a heavy box along a corridor at an angle, so it presses against the wall. While your push has any sideways component along the wall, the box slides. It keeps sliding. It stops only at the instant your push is square-on — when nothing you are doing runs along the wall any more, and all of it goes into the wall. That is not a fact about boxes. It is the stopping condition for every constrained problem, and it is the first of the five conditions we are building.

Pushing a box against a wallSplit the downhill arrow into the part that runs along the fence and the part that pushes into it. You stop when the along-part is gone.

Try: drag the dot along the fence and watch the along-the-fence bar shrink; where it hits zero the two gradient arrows lie on one line and the stretch factor is the multiplier.

0.74
—

At the answer the leftover downhill along the fence is zero, so ∇f\nabla f has nothing left but the across-fence direction. For a ≤\le fence that means ∇f=−μ∇g\nabla f=-\mu\nabla g with μ≥0\mu\ge0 — the two arrows point opposite ways. For an == path it only means ∇f\nabla f is some multiple of ∇h\nabla h, and the sign of that multiple is free. Either way the multiplier is the stretch factor that makes the two arrows the same length.

Drag the point around the fence and watch the bar. The downhill arrow −∇f-\nabla f has been split into two pieces: the part that runs along the fence, and the part that pushes across it. While the along-part exists you are not finished — slide that way and the score improves, legally, without ever leaving the allowed set. The bar shrinks as you approach the answer and reaches zero exactly at it.

When the along-part is gone, all of ∇f\nabla f points across the fence. And there is only one direction that is "across the fence": the fence's own gradient ∇g\nabla g, which points out of the allowed side. Two arrows pointing along one line is not a vague picture — it is an equation.

The realization

∇f(x⋆)=−μ ∇g(x⋆),μ≥0\nabla f(\mathbf x^\star)=-\mu\,\nabla g(\mathbf x^\star),\qquad \mu\ge0

Parallel — not equal. The two arrows almost never have the same length, and μ\mu is the stretch factor between them. Writing "∇f=∇g\nabla f=\nabla g" is the single most common slip in this topic, and the widget shows you the two lengths side by side so you can see how different they are: on the straight fence ∇f=(4,4)\nabla f=(4,4) and ∇h=(1,1)\nabla h=(1,1), a stretch of 44.

There is a second way to read the same picture, and it is worth having both. The level curves of ff are the score's contour lines. Shrink them until the smallest one still touches the allowed set. It touches — it does not cross — and at a touching point two curves share a tangent, which means their normals lie on one line. Tangency and "nothing left to slide" are the same statement seen from two angles.

Open the budget circle tab, because you have been doing this for months without being told. Ridge regression is usually taught as "minimise the error plus λ∑βj2\lambda\sum\beta_j^2". Its honest original form is a constrained problem: minimise the training error subject to ∑jβj2≤s\sum_j\beta_j^2\le s — a budget on how large the coefficients may grow. The grey rings are the error, the red circle is the budget, and the answer is where the smallest reachable ring touches the circle. That picture is the entire geometry of ridge, and the λ\lambda in your notes is the stretch factor μ\mu at that touching point. Lasso is the same picture with a diamond instead of a circle — and corners are exactly where coefficients become zero.

Pause & predict

At a candidate point on a fence you find that ∇f\nabla f has a component of size 0.70.7 running along the fence. What does that tell you?

If you want the algebra · 1 proof, step by step
Prove it · nothing left to slide means the two gradients are parallel

Claim. At a minimum sitting on an active fence g=0g=0 (with ∇g≠0\nabla g\ne\mathbf 0), the component of ∇f\nabla f along the fence must vanish, hence ∇f(x⋆)=−μ ∇g(x⋆)\nabla f(\mathbf x^\star)=-\mu\,\nabla g(\mathbf x^\star) for some μ≥0\mu\ge0.

1
Split ∇f\nabla f into the part along the fence and the part across it. Writing n=∇g/∥∇g∥\mathbf n=\nabla g/\|\nabla g\| for the unit normal, ∇f=(∇f ⁣⊤n) n⏟across+∇f−(∇f ⁣⊤n) n⏟p = along.\nabla f=\underbrace{(\nabla f^{\!\top}\mathbf n)\,\mathbf n}_{\text{across}}+\underbrace{\nabla f-(\nabla f^{\!\top}\mathbf n)\,\mathbf n}_{\textstyle \mathbf p\ =\ \text{along}}. A plain orthogonal decomposition. p\mathbf p is the piece that lives in the fence's tangent direction.
2
Suppose p≠0\mathbf p\ne\mathbf 0. Move a small ε\varepsilon along −p-\mathbf p. To first order this keeps you on the fence (∇g ⁣⊤p=0\nabla g^{\!\top}\mathbf p=0, so gg does not change) and changes the score by ∇f ⁣⊤(−εp)=−ε∥p∥2<0.\nabla f^{\!\top}(-\varepsilon\mathbf p)=-\varepsilon\|\mathbf p\|^2<0. A legal move that strictly lowers the score. So the point was not a minimum — exactly the box that is still sliding.
3
Therefore p=0\mathbf p=\mathbf 0 at any minimum, so ∇f\nabla f is a multiple of n\mathbf n, i.e. of ∇g\nabla g: write ∇f=−μ∇g\nabla f=-\mu\nabla g. Parallel, not equal — μ\mu absorbs the difference in length, which is typically large.
4
The sign. Moving into the feasible side means moving along −∇g-\nabla g, and that must not lower ff: ∇f ⁣⊤(−∇g)=(−μ∇g) ⁣⊤(−∇g)=μ∥∇g∥2 ≥0 ⟹ μ≥0.\begin{aligned}\nabla f^{\!\top}(-\nabla g)&=(-\mu\nabla g)^{\!\top}(-\nabla g)\\[2pt] &=\mu\|\nabla g\|^2\ \ge0\ \Longrightarrow\ \mu\ge0.\end{aligned} ∎ If μ\mu were negative you could step inwards, legally, and improve — so the fence was not holding you at all. That is the geometric twin of §9's guard argument.
In one sentence: You stop when nothing is left to slide, which means all of ∇f\nabla f points across the fence — so ∇f\nabla f and ∇g\nabla g lie on one line, related by a stretch factor μ≥0\mu\ge0, and that factor is about to turn out to be a price.
9

Turn the wall into a fine

The guard at the fence

We know how to optimise a function with no rules: differentiate, set to zero. So the plan is to get rid of the rules. And there is exactly one way to get rid of a rule without changing the answer: charge for breaking it. Put a guard at the fence. Cross it and you pay μ\mu rupees per metre past it; stay behind it and you pay nothing. Now there is no fence — only a bill. You want the bill small. The guard, who would love you to stray, wants it large. That tug-of-war is the whole method.

Turn the wall into a fineAn infinite wall is not a function you can differentiate. A straight-line fine is. Raise the rate until the fine does the wall's whole job.

Try: drag μ\mu below zero and watch the walker sprint off to the right — a negative fine pays you to trespass. That one drag is the whole of μ≥0\mu\ge0.

2
—

max⁡μ≥0μg\max_{\mu\ge0}\mu g is 00 when g≤0g\le0 and +∞+\infty when g>0g>0: the infinite wall, rebuilt out of straight lines. That is why min⁡xmax⁡μ≥0L\min_{\mathbf x}\max_{\mu\ge0}L is the original problem — and why swapping the two, max⁡μ≥0min⁡xL\max_{\mu\ge0}\min_{\mathbf x}L, is the dual.

The first honest attempt at that bill is a wall written as a function: charge 00 inside and ∞\infty outside. It is perfectly correct — any illegal point now scores infinity, so the unconstrained problem has exactly the same answer as the constrained one. It is also useless, because you cannot differentiate a vertical cliff, and differentiating is the only thing we know how to do.

So look at the top panel and do the one thing that saves the method: put a straight line under the wall and raise its slope. The line μg\mu g is zero at the fence, harmless on the allowed side (where g≤0g\le0 makes it negative or zero), and climbing on the banned side. It is not the wall — it is always below the wall — but as μ\mu grows it does more and more of the wall's job. And the wall is exactly what you get if you let the guard pick the worst μ\mu for you:

The realization

max⁡μ≥0 μ g  =  {0,g≤0+∞,g>0⟹L(x,λ,μ)=f(x)+λ e(x)+∑iμi gi(x)\max_{\mu\ge0}\ \mu\,g \;=\; \begin{cases}0,& g\le0\\ +\infty,& g>0\end{cases}\qquad\Longrightarrow\qquad L(\mathbf x,\lambda,\boldsymbol\mu)=f(\mathbf x)+\lambda\,e(\mathbf x)+\sum_i\mu_i\,g_i(\mathbf x)

The infinite wall, rebuilt out of straight lines. Obey the fence and the guard's best move is μ=0\mu=0, so you pay nothing; break it and the guard sends μ\mu up without limit. That one line is why the Lagrangian — score, plus a fine for leaving the path, plus a fine for crossing each fence — is not an approximation of the constrained problem. It is the constrained problem, with the rules relaxed into prices.

Two sign rules come out of the same picture, and they are not conventions.

Every fence fine must satisfy μi≥0\mu_i\ge0. Drag μ\mu below zero in the top panel and watch: the line now dips below zero on the banned side, so crossing the fence would lower your bill. The optimiser would sprint out of bounds on purpose — and the widget draws it doing exactly that. A fine has to raise the bill, never lower it. This rule has a name, dual feasibility, and you have just seen the whole of it in one drag.

The path fine λ\lambda is free. Any sign. The path constraint is e=0e=0, and you can drift off it in either direction; both directions are equally illegal, so the fine has no natural sign. You will find negative λ\lambda's constantly and they are correct. Forcing λ≥0\lambda\ge0 will make you find nothing.

The lower panel is the same idea on a real problem: f(x)=(x−3)2f(x)=(x-3)^2 behind a fence at x≤1x\le1. Slide μ\mu and watch min⁡xL\min_x L — a perfectly ordinary unconstrained minimisation, one you could do in your sleep — climb towards 44, the true constrained answer, and touch it exactly at μ=4\mu=4. At that price, the straight line does the whole wall's job.

Pause & predict

Why is a negative fence multiplier μi<0\mu_i<0 forbidden, when a negative λ\lambda on the path is perfectly fine?

Pause & predict

You are minimising ff subject to one fence, and your candidate point sits comfortably inside the allowed region. What does the guard charge?

If you want the algebra · 2 proofs, step by step
Prove it · the infinite wall, rebuilt out of straight lines

Claim. max⁡μ≥0 μ g={0,g≤0+∞,g>0\displaystyle\max_{\mu\ge0}\ \mu\,g=\begin{cases}0,&g\le0\\ +\infty,&g>0\end{cases} — the indicator of the fence, exactly.

1
If g≤0g\le0: for every μ≥0\mu\ge0 the product μg≤0\mu g\le0, and the value 00 is achieved at μ=0\mu=0. So the maximum is 00. On the allowed side the guard's best move is to charge nothing — any positive rate would reduce the bill the guard is trying to raise.
2
If g>0g>0: taking μ=M\mu=M gives Mg→∞Mg\to\infty as M→∞M\to\infty. So the supremum is +∞+\infty. On the banned side the guard is unbounded, and one violated fence is enough to make the whole bill infinite.
3
Hence for every x\mathbf x, max⁡μ≥0L(x,μ)=f(x)+∑imax⁡μi≥0μigi(x)={f(x),x feasible+∞,otherwise,\begin{aligned}\max_{\boldsymbol\mu\ge0} L(\mathbf x,\boldsymbol\mu)&=f(\mathbf x)+\sum_i\max_{\mu_i\ge0}\mu_ig_i(\mathbf x)\\[2pt] &=\begin{cases}f(\mathbf x),&\mathbf x\ \text{feasible}\\ +\infty,&\text{otherwise,}\end{cases}\end{aligned} so min⁡xmax⁡μ≥0L\min_{\mathbf x}\max_{\boldsymbol\mu\ge0}L is the constrained problem. ∎ Nothing was relaxed or approximated. The Lagrangian with a maximising guard is the original problem written in a form we can differentiate.
Prove it · why a fence fine can never be negative

Claim. If some μi<0\mu_i<0 were allowed, the minimiser of LL would be pushed outside the feasible set on purpose, and the construction above would fail.

1
Take one fence and a point with g(x)>0g(\mathbf x)>0 — illegal. The term contributed to the bill is μg\mu g. This is the only place the rule enters the objective, so this term alone decides whether breaking the rule is punished or rewarded.
2
With μ<0\mu<0 and g>0g>0, μg<0\mu g<0: the bill falls. And it falls further the more the fence is broken, since μg→−∞\mu g\to-\infty as g→∞g\to\infty. A subsidy, not a fine. The minimiser will chase it out of bounds and never come back.
3
Correspondingly, max⁡μ∈Rμg\max_{\mu\in\mathbb R}\mu g is +∞+\infty for g≠0g\ne0 and 00 only at g=0g=0 — the indicator of the equality g=0g=0, not of g≤0g\le0. Restricting to μ≥0\mu\ge0 is exactly what turns it into the one-sided rule. ∎ So the sign rule is not a convention: it is the difference between "stay behind the fence" and "sit exactly on it". And it explains λ\lambda at once — for a genuine equality we want the two-sided version, so λ\lambda is left free.
In one sentence: An infinite wall cannot be differentiated but a straight line can, and letting the guard raise the line's slope without limit rebuilds the wall exactly — which is why L=f+λe+∑μigiL=f+\lambda e+\sum\mu_i g_i with μi≥0\mu_i\ge0 is the constrained problem itself, not a softened version of it.
10

Room left, and the rule that falls out of it

The gap you can still walk

Stand somewhere legal and measure the one number the Lagrangian keeps ignoring: how much room you have left before you touch the fence. If there is room, the guard has no grounds to charge you. If there is no room, the guard may charge whatever the geometry demands. That sentence is a theorem, and the way to prove it is to give the room a name and differentiate with respect to it.

Room left, and the rule that falls out of itEither you have room and the fine is zero, or you are touching and the fine may be positive. Never both, never neither.

Try: drag the answer from deep inside to hard against the fence and watch the dot travel along the two edges of the square — it never once enters the middle, and μ⋅g\mu\cdot g stays 0.0000.000 the whole way.

−1.2
—

μ g=0\mu\,g=0 is not an extra wish; it is what "the fine is only charged when you are actually touching" means in one line. Writing g+t2=0g+t^2=0 says the same thing with a slack length tt: a square is never negative, so g≤0g\le0 is built into the algebra instead of being asserted.

Here is the move. The fence g≤0g\le0 is an inequality, and calculus is bad at inequalities. So turn it into an equation by adding the room:

The realization

gi(x)+ti 2=0⟹ μi gi(x⋆)=0 g_i(\mathbf x)+t_i^{\,2}=0\qquad\Longrightarrow\qquad \boxed{\ \mu_i\,g_i(\mathbf x^\star)=0\ }

Why squared? Because writing gi+ti=0g_i+t_i=0 with ti≥0t_i\ge0 would just swap one inequality for another. A square is never negative by construction — the rule is built into the algebra instead of sitting beside it as a condition — and it stays smooth, so we can still differentiate. Nothing is lost: ti2=−gi≥0t_i^2=-g_i\ge0 says exactly gi≤0g_i\le0, back again.

And then the payoff falls out in four lines. tit_i appears in LL only inside μiti2\mu_i t_i^2, so ∂L/∂ti=2μiti=0\partial L/\partial t_i=2\mu_it_i=0; multiply by tit_i and halve to get μiti2=0\mu_it_i^2=0; substitute ti2=−git_i^2=-g_i. The name of the rule now makes sense: complementary slackness was derived from the slack.

A product of two numbers is zero only if one of them is. So for every fence, exactly one of two worlds holds — and the widget's greyed-out quadrant is the world that cannot exist.

Room to spare. gi<0g_i<0: you are strictly inside. The guard has no grounds, so μi=0\mu_i=0. The fence is inactive, or slack — it is doing no work, and deleting it entirely would not move the answer.

Touching. gi=0g_i=0: you are pressed against the edge. Now μi\mu_i is free to be positive, and usually is. The fence is active, or tight, and it is holding you back.

Two traps live here and both are easy. The first: "the fence is active" and "we are on the boundary" are the same world, not two — active means gi=0g_i=0 means on the boundary. The real split is fine is zero versus fence is touched. The second, and it costs more marks: on the boundary the fine is not forced to zero. With gi=0g_i=0 the product μigi\mu_ig_i is zero for any μi\mu_i at all. A positive fine on an active fence is the normal case; in two sections you will meet a problem whose answer sits on the fence with μ⋆=4\mu^\star=4.

And the multiplier is not bookkeeping. It is a price: relax fence ii by a small amount ε\varepsilon and the best score improves by about μiε\mu_i\varepsilon. A fence with μi=0\mu_i=0 is a fence you would pay nothing to remove — because it was never in your way. We will cash that in at §13.

Pause & predict

At the optimum you find μ3=0\mu_3=0 for the third fence. What can you conclude about g3(x⋆)g_3(\mathbf x^\star)?

If you want the algebra · 1 proof, step by step
Prove it · complementary slackness, in four lines, from the room left

Claim. Writing each fence as gi(x)+ti2=0g_i(\mathbf x)+t_i^2=0 and differentiating LL with respect to tit_i gives μi gi(x⋆)=0\mu_i\,g_i(\mathbf x^\star)=0.

1
The substitution loses nothing: ti2=−git_i^2=-g_i, and a square is never negative, so −gi≥0-g_i\ge0, which is gi≤0g_i\le0 — the original fence, recovered. The inequality has been absorbed into the algebra. Every rule in the problem is now an equation, apart from the sign rule on μi\mu_i.
2
With the slacks in, L(x,λ,μ,t)=f+λe+∑iμi(gi+ti2)L(\mathbf x,\lambda,\boldsymbol\mu,\mathbf t)=f+\lambda e+\sum_i\mu_i\big(g_i+t_i^2\big). The only term containing tit_i is μiti2\mu_it_i^2, so ∂L∂ti=2μiti=0.\frac{\partial L}{\partial t_i}=2\mu_it_i=0. A new unknown means a new equation — and this is the one that books usually state without ever deriving.
3
Multiply by tit_i and halve: μiti2=0\mu_it_i^2=0. Multiplying by tit_i is legal even when ti=0t_i=0; it simply keeps the identity true in both worlds.
4
Substitute ti2=−git_i^2=-g_i: μi(−gi(x⋆))=0 ⟹ μi gi(x⋆)=0.\mu_i\big(-g_i(\mathbf x^\star)\big)=0\ \Longrightarrow\ \mu_i\,g_i(\mathbf x^\star)=0. ∎ A product is zero only if a factor is, so per fence: either ti≠0t_i\ne0 (room left) forcing μi=0\mu_i=0, or μi≠0\mu_i\ne0 forcing ti=0t_i=0, i.e. the fence is touched. The name is literal — the rule came out of the slack.
In one sentence: Name the room left as a square, and differentiating with respect to it hands you μigi=0\mu_ig_i=0 — either you have room and the fine is zero, or you are touching and the fine may be positive, never both loose at once.
11

Five conditions, and a branching interrogation

Nothing new, just everything at once

Here is the anticlimax that makes this topic learnable. The famous KKT conditions — Karush, Kuhn and Tucker — are not a new idea. They are the oldest idea in the course, set every derivative to zero, run on the Lagrangian with the slack variables in it. Differentiate with respect to each kind of unknown in turn and each condition falls out, one per kind. Only the last one has to be added by hand.

The realization

1 ⋅ stationarity (∂L/∂x):∇f+λ∇e+∑iμi∇gi=02 ⋅ the path (∂L/∂λ):e(x⋆)=03 ⋅ the fences (∂L/∂μi):gi(x⋆)≤04 ⋅ complementary slackness (∂L/∂ti):μi gi(x⋆)=05 ⋅ dual feasibility (the sign rule):μi≥0\begin{aligned} \text{1 · stationarity } (\partial L/\partial\mathbf x):\quad & \nabla f+\lambda\nabla e+\textstyle\sum_i\mu_i\nabla g_i=\mathbf 0\\[2pt] \text{2 · the path } (\partial L/\partial\lambda):\quad & e(\mathbf x^\star)=0\\[2pt] \text{3 · the fences } (\partial L/\partial\mu_i):\quad & g_i(\mathbf x^\star)\le0\\[2pt] \text{4 · complementary slackness } (\partial L/\partial t_i):\quad & \mu_i\,g_i(\mathbf x^\star)=0\\[2pt] \text{5 · dual feasibility } (\text{the sign rule}):\quad & \mu_i\ge0 \end{aligned}

Four of the five are derivatives. The fifth is §9's guard argument, and no derivative will ever give it to you. Note what condition 1 is: it is §8's two-arrows-on-one-line, written for many rules at once. And note that λ\lambda is absent from the sign rule. It stays free.

Now the part that turns this into a procedure you can actually run. Condition 4 is one product per fence, and a product being zero offers two branches: the fine is zero, or the fence is touched. Guess a branch for every fence, solve the resulting equations, and let conditions 2, 3 and 5 throw out the guesses that lie. Work through the four branches yourself:

Five conditions, a branching interrogationEach fence is either doing work or not. Guess, solve, and let the conditions throw out the guesses that lie.

Try: click each of the four branches on the first tab — three of them die on a negative multiplier or on the path itself, and exactly one survives every condition.

—

Stationarity · the path · the fences · one fine charged only when touching · every fence fine ≥0\ge0. A path multiplier λ\lambda may be any sign — only fence multipliers are forced to be non-negative, and that is the condition doing most of the rejecting here.

Three of the four cases died, and notice how they died — each one is a different lesson. Case 2 and case 3 produced a perfectly well-formed answer and then returned a negative multiplier, μ=−2\mu=-2 and μ=−4\mu=-4. That is not a sign convention to be fixed; it means the case you assumed is impossible — the fence would have to pull you towards it rather than push you away. Discard and move on. Case 4 never even got that far: it broke the path before any fine rate was computed. And the surviving case returned λ⋆=−4/3\lambda^\star=-4/3, negative, and perfectly legal, because λ\lambda was never sign-restricted.

The branches multiply. Each fence doubles the count, so mm fences give 2m2^m cases — and the classic slip is to write m2m^2. The two agree at m=2m=2 (both 44) and at m=4m=4 (both 1616), which is exactly why the mistake survives; they part company at m=3m=3, where the truth is 8\mathbf 8, not 99. Equality constraints add no branches at all: the path is always tight and λ\lambda is never forced to zero.

Three honest footnotes about that count. Branches overlap — a point can have μi=0\mu_i=0 and gi=0g_i=0 at once, and will then turn up in two of them; finding the same point twice is normal. A branch may yield no solution, one, or a whole family, so 2m2^m counts branches to check, not candidates you will collect. And 2m2^m grows viciously: ten fences give 10241024, and a support vector machine has one fence per training point. Nobody solves a real one by listing cases. The case list is a hand tool; §13 is the algorithm.

Pause & predict

While testing a case you assumed active, the algebra returns μ2=−3\mu_2=-3. What do you do?

Pause & predict

A problem has one equality constraint and three inequality constraints. How many cases does complementary slackness create?

If you want the algebra · 1 proof, step by step
Prove it · the five conditions are four derivatives and a sign

Claim. Setting every partial derivative of L(x,λ,μ,t)=f+λe+∑iμi(gi+ti2)L(\mathbf x,\lambda,\boldsymbol\mu,\mathbf t)=f+\lambda e+\sum_i\mu_i(g_i+t_i^2) to zero yields conditions 1–4, and condition 5 is the sign rule of the previous drawer.

1
In x\mathbf x (nn equations). The slack terms carry no x\mathbf x, so they drop: ∇f(x⋆)+λ∇e(x⋆)+∑iμi∇gi(x⋆)=0.\nabla f(\mathbf x^\star)+\lambda\nabla e(\mathbf x^\star)+\sum_i\mu_i\nabla g_i(\mathbf x^\star)=\mathbf 0. This is §8's two-arrows statement, written for many rules at once: ∇f\nabla f is a combination of the constraint gradients, so nothing of it is left running along the feasible directions.
2
In λ\lambda. Only λe(x)\lambda e(\mathbf x) contains λ\lambda, and it is linear in it, so the derivative is e(x⋆)=0e(\mathbf x^\star)=0. Our own path constraint, handed back. A good sign: the machinery did not lose a rule.
3
In μi\mu_i. Only μi(gi+ti2)\mu_i(g_i+t_i^2) contains μi\mu_i, so gi(x⋆)+ti2=0g_i(\mathbf x^\star)+t_i^2=0, i.e. gi(x⋆)=−ti2≤0.g_i(\mathbf x^\star)=-t_i^2\le0. Our own fences, handed back — and with the inequality restored for free by the square.
4
In tit_i. The previous drawer: μigi(x⋆)=0\mu_ig_i(\mathbf x^\star)=0. And the sign: μi≥0\mu_i\ge0, which no derivative will give you — it comes from the guard argument. ∎ Four kinds of unknown, four conditions, plus one rule about what a fine is. Some books list four conditions by folding the sign rule into the setup; count five when you write an answer, so nothing can be said to be missing.
5
Counting: nn variables, one λ\lambda, mm multipliers, mm slacks — n+2m+1n+2m+1 unknowns, matched by n+1+m+mn+1+m+m equations plus mm sign rules. And condition 4 splits into 2m2^m branches, since each μigi=0\mu_ig_i=0 can be satisfied two ways. Books that skip slacks report n+m+1n+m+1 unknowns. Both counts are right; they describe different setups, and only the slack version hands you condition 4 for free.
In one sentence: KKT is "set every derivative to zero" run on the Lagrangian with slacks — four conditions from four kinds of unknown, plus the sign rule — and complementary slackness turns it into a finite interrogation of 2m2^m branches, most of which die on a negative multiplier.
12

Which problems are honest

The string test

You now have a test that finds candidates. When is a candidate the answer? There is a physical test you can do on any graph with a piece of string. Stretch it tight between two points on the curve. If the string never sags below the curve — if the curve always stays on or under its own chords — the function is a bowl, and a bowl has exactly one bottom. Stretch the string on a curve with two dips and it cuts straight across the hump: not a bowl, and everything gets harder.

Which problems are honestTwo tests for a bowl — the chord and the tangent — and one test for a set. They always agree, and together they decide whether a stopping point is the answer or only a candidate.

Try: pick x4−3x2x^4-3x^2 and press ▶ — the chord test fails on a fat block of pairs; then switch to the tangent test and watch the line rise above the curve over exactly the same region.

0.18
0.86
0.5
convex ⇒ a stopping point is THE answer. Not convex ⇒ only a candidate.
—

A bowl is a function no chord ever cuts into, which is the same as a function that never falls below any of its own tangents. A convex set is one that contains every segment between two of its points. The problem is honest when the score is a bowl and the allowed region is such a set.

Drag the two points and read the two numbers. The point on the chord sits at height θf(x)+(1−θ)f(y)\theta f(x)+(1-\theta)f(y); the point on the curve directly below it sits at f(θx+(1−θ)y)f(\theta x+(1-\theta)y). If the second is never above the first, you have a convex function.

Then switch to the tangent tab, which is the same fact in a different pose: lay a tangent line at any point and let it run. For a bowl the tangent is a global under-estimate — the curve never dips below it anywhere. Run the sweep on both tabs and they agree on every curve, every time; on x2x^2 the chord test fails 00 times in 200200 sampled pairs, on x4−3x2x^4-3x^2 it fails in 119119 of them.

The realization

f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)⟺f(y)≥f(x)+∇f(x) ⁣⊤(y−x)\begin{aligned}f\big(\theta\mathbf x+(1-\theta)\mathbf y\big)&\le\theta f(\mathbf x)+(1-\theta)f(\mathbf y)\\[3pt] \Longleftrightarrow\quad f(\mathbf y)&\ge f(\mathbf x)+\nabla f(\mathbf x)^{\!\top}(\mathbf y-\mathbf x)\end{aligned}

Chord above the curve, on the left; tangent below the curve, on the right. Same property, two poses — and the right-hand one is the useful one, because it says a local reading of the slope is a global promise. That is the whole reason convexity matters: on a bowl, what you can measure at your feet constrains the entire landscape.

The same test applies to sets, on the third tab: a set is convex when the segment joining any two of its points stays inside. A disc passes; a crescent and a ring fail. So a convex problem means a bowl objective, bowl fences, linear path — and then the allowed region is convex too, and there is nothing to get trapped in.

Now collect the payoff, stated carefully, because the two halves of it are constantly confused.

KKT is necessary — every true answer must pass the test — provided the constraints are well behaved where the answer sits. The technical name is a constraint qualification, and the common one is that the gradients of the active constraints are linearly independent there. Two active fences with parallel gradients break it, the multipliers may fail to exist, and the test can miss the answer entirely.

KKT is sufficient only if the problem is convex. For convex ff, convex gig_i and linear ee, a point passing all five conditions is the global minimum, full stop, no second check. For a non-convex problem it might be a maximum or a saddle, and you must verify some other way. So never write "all five conditions hold, therefore this is the minimum" without saying which part is convex.

Two shapes cover most of what you will meet, and both are convex. A linear program has a linear score and linear rules: min⁡c ⁣⊤x\min\mathbf c^{\!\top}\mathbf x subject to Ax≤bA\mathbf x\le\mathbf b. A quadratic program has a bowl score and linear rules: min⁡12x ⁣⊤Qx+c ⁣⊤x\min\tfrac12\mathbf x^{\!\top}Q\mathbf x+\mathbf c^{\!\top}\mathbf x subject to Ax≤bA\mathbf x\le\mathbf b. Ridge, lasso and the support vector machine are all quadratic programs. Their duals come out in closed form, and both are worked in the drawer below.

Pause & predict

You run the five conditions on a problem and one point passes all of them. Is it the minimum?

If you want the algebra · 2 proofs, step by step
Prove it · the chord test implies the tangent test

Claim. If f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)f\big(\theta\mathbf x+(1-\theta)\mathbf y\big)\le\theta f(\mathbf x)+(1-\theta)f(\mathbf y) for all θ∈[0,1]\theta\in[0,1], then f(y)≥f(x)+∇f(x) ⁣⊤(y−x)f(\mathbf y)\ge f(\mathbf x)+\nabla f(\mathbf x)^{\!\top}(\mathbf y-\mathbf x) for all x,y\mathbf x,\mathbf y.

1
Rewrite the chord condition with the roles arranged around x\mathbf x. Put zθ=x+θ(y−x)\mathbf z_\theta=\mathbf x+\theta(\mathbf y-\mathbf x); then zθ=(1−θ)x+θy\mathbf z_\theta=(1-\theta)\mathbf x+\theta\mathbf y, so f(zθ)≤(1−θ)f(x)+θf(y).f(\mathbf z_\theta)\le(1-\theta)f(\mathbf x)+\theta f(\mathbf y). Same statement, parametrised by how far along the segment you have walked.
2
Subtract f(x)f(\mathbf x) from both sides and divide by θ>0\theta>0: f(x+θ(y−x))−f(x)θ ≤ f(y)−f(x).\frac{f\big(\mathbf x+\theta(\mathbf y-\mathbf x)\big)-f(\mathbf x)}{\theta}\ \le\ f(\mathbf y)-f(\mathbf x). The left side is a difference quotient along the direction y−x\mathbf y-\mathbf x. The right side does not contain θ\theta at all — so it is an upper bound that survives any limit.
3
Let θ→0+\theta\to0^+. The left side is the directional derivative ∇f(x) ⁣⊤(y−x)\nabla f(\mathbf x)^{\!\top}(\mathbf y-\mathbf x), giving ∇f(x) ⁣⊤(y−x)≤f(y)−f(x).\nabla f(\mathbf x)^{\!\top}(\mathbf y-\mathbf x)\le f(\mathbf y)-f(\mathbf x). ∎ Read it as a promise: the tangent plane at x\mathbf x lies below the whole surface. So if ∇f(x)=0\nabla f(\mathbf x)=\mathbf 0 then f(y)≥f(x)f(\mathbf y)\ge f(\mathbf x) everywhere — one local measurement certifies a global minimum. That is the entire practical value of convexity.
Prove it · the duals of a linear program and a quadratic program

Claim. For min⁡c ⁣⊤x\min\mathbf c^{\!\top}\mathbf x s.t. Ax≤bA\mathbf x\le\mathbf b the dual is max⁡−λ ⁣⊤b\max-\boldsymbol\lambda^{\!\top}\mathbf b s.t. c+A ⁣⊤λ=0, λ≥0\mathbf c+A^{\!\top}\boldsymbol\lambda=\mathbf 0,\ \boldsymbol\lambda\ge\mathbf 0; for min⁡12x ⁣⊤Qx+c ⁣⊤x\min\tfrac12\mathbf x^{\!\top}Q\mathbf x+\mathbf c^{\!\top}\mathbf x s.t. Ax≤bA\mathbf x\le\mathbf b with QQ invertible it is max⁡−12(c+A ⁣⊤λ) ⁣⊤Q−1(c+A ⁣⊤λ)−λ ⁣⊤b\max-\tfrac12(\mathbf c+A^{\!\top}\boldsymbol\lambda)^{\!\top}Q^{-1}(\mathbf c+A^{\!\top}\boldsymbol\lambda)-\boldsymbol\lambda^{\!\top}\mathbf b s.t. λ≥0\boldsymbol\lambda\ge\mathbf 0.

1
Linear. Write the Lagrangian and collect the x\mathbf x terms: L=c ⁣⊤x+λ ⁣⊤(Ax−b)=(c+A ⁣⊤λ) ⁣⊤x−λ ⁣⊤b.L=\mathbf c^{\!\top}\mathbf x+\boldsymbol\lambda^{\!\top}(A\mathbf x-\mathbf b)=(\mathbf c+A^{\!\top}\boldsymbol\lambda)^{\!\top}\mathbf x-\boldsymbol\lambda^{\!\top}\mathbf b. It is linear in x\mathbf x, which makes the inner minimisation trivial and brutal.
2
Minimising a linear function over all of Rd\mathbb R^d gives −∞-\infty unless its coefficient vector is zero. So d(λ)={−λ ⁣⊤b,c+A ⁣⊤λ=0−∞,otherwise.d(\boldsymbol\lambda)=\begin{cases}-\boldsymbol\lambda^{\!\top}\mathbf b,&\mathbf c+A^{\!\top}\boldsymbol\lambda=\mathbf 0\\ -\infty,&\text{otherwise.}\end{cases} Maximising over λ≥0\boldsymbol\lambda\ge\mathbf 0 therefore forces the equation as a constraint of the dual. The −∞-\infty region is not a nuisance; it is where the dual's own constraints come from. A dual variable that sends the inner problem to −∞-\infty is a price nobody would ever quote.
3
Note the shape swap: the primal has dd variables and mm rules; the dual has mm variables and dd rules. Solve whichever is smaller. This is reason one from §13, in its purest form.
4
Quadratic. Now L=12x ⁣⊤Qx+(c+A ⁣⊤λ) ⁣⊤x−λ ⁣⊤bL=\tfrac12\mathbf x^{\!\top}Q\mathbf x+(\mathbf c+A^{\!\top}\boldsymbol\lambda)^{\!\top}\mathbf x-\boldsymbol\lambda^{\!\top}\mathbf b; setting ∇xL=0\nabla_{\mathbf x}L=\mathbf 0 gives Qx+(c+A ⁣⊤λ)=0Q\mathbf x+(\mathbf c+A^{\!\top}\boldsymbol\lambda)=\mathbf 0, so x=−Q−1(c+A ⁣⊤λ)\mathbf x=-Q^{-1}(\mathbf c+A^{\!\top}\boldsymbol\lambda). A bowl in x\mathbf x has a genuine minimum, so nothing runs off to −∞-\infty and there is no hidden constraint this time.
5
Substituting back and writing u=c+A ⁣⊤λ\mathbf u=\mathbf c+A^{\!\top}\boldsymbol\lambda: d(λ)=12u ⁣⊤Q−1u−u ⁣⊤Q−1u−λ ⁣⊤b=−12u ⁣⊤Q−1u−λ ⁣⊤b.\begin{aligned}d(\boldsymbol\lambda)&=\tfrac12\mathbf u^{\!\top}Q^{-1}\mathbf u-\mathbf u^{\!\top}Q^{-1}\mathbf u-\boldsymbol\lambda^{\!\top}\mathbf b\\ &=-\tfrac12\mathbf u^{\!\top}Q^{-1}\mathbf u-\boldsymbol\lambda^{\!\top}\mathbf b.\end{aligned} ∎ A concave quadratic in λ\boldsymbol\lambda with only the sign rules left — and ridge, lasso and the support vector machine are all of exactly this shape. The last one is worked in §14.
In one sentence: A bowl is a function that never rises above its own chords and never dips below its own tangents — and on a bowl, with bowl fences, a point that passes the five conditions is the answer; off a bowl, it is only a candidate.
13

Who moves first — and what a wall is worth

Naming your price first

Two people share one number: you pick x\mathbf x and want the bill low, the guard picks μ\mu and wants it high. Everything about duality comes from one question nobody asks in the algebra — who moves first? If you choose and the guard answers, that is one game. If the guard announces the price and you then choose knowing it, that is a different game, and it is a worse deal for the guard. Moving second is an advantage. Whoever gives it up loses something.

Who moves firstThe same number seen from two sides — and the reason the view from below is always a bowl turned upside down, however ugly the problem is

Try: open a bundle of lines and drag the highlight: every single line is straight, and the thick curve under them all still bends downward. That is why the dual is always concave.

1
4
—

For each fixed xx, μ↦L(x,μ)\mu\mapsto L(x,\mu) is a straight line of height f(x)f(x) and slope g(x)g(x). The dual is the lowest of all those lines, and the lowest of any bundle of straight lines bends downward — so dd is concave whatever ff and gg are. Weak duality d∗≤p∗d^*\le p^* is free; it is equality that needs convexity.

Put both games on paper. If you move first, the guard sees your choice and answers with the worst μ\mu for you — which, as §9 showed, is 00 when you obeyed the fence and ∞\infty when you did not. So the min-max quietly scores every illegal point at infinity and every legal one at its true score: it is the original problem.

The realization

p⋆=min⁡x max⁡μ≥0 L(x,μ)≥max⁡μ≥0 min⁡x L(x,μ)=d⋆p^\star=\min_{\mathbf x}\ \max_{\mu\ge0}\ L(\mathbf x,\mu)\qquad\ge\qquad \max_{\mu\ge0}\ \min_{\mathbf x}\ L(\mathbf x,\mu)=d^\star

Left, the primal: you move first. Right, the dual: the guard moves first, and the inner part d(μ)=min⁡xL(x,μ)d(\mu)=\min_{\mathbf x}L(\mathbf x,\mu) is the dual function — an ordinary unconstrained minimisation with no x\mathbf x left in the answer. The inequality is weak duality and it is always true, for every problem, convex or not. The shortfall p⋆−d⋆≥0p^\star-d^\star\ge0 is the duality gap, and when it is zero we have strong duality.

Now open a bundle of lines, because this is the picture that explains why anybody bothers. Fix any x\mathbf x and look at L(x,μ)=f(x)+μg(x)L(\mathbf x,\mu)=f(\mathbf x)+\mu g(\mathbf x) as a function of μ\mu: it is a straight line, with height f(x)f(\mathbf x) and slope g(x)g(\mathbf x). One line per x\mathbf x. The dual function is the lowest of all of them — and the lowest of any bundle of straight lines always bends downward.

So dd is concave. Always. However lumpy, non-convex, multi-valleyed and awful ff and gg are, the view from below is a single hill with one peak and no local traps. Maximising it is a well-behaved problem when the original is not. (Say that carefully: the dual function is concave; the dual problem, maximising a concave function, is a convex optimization problem. Both statements are right and they are about different objects.)

Three reasons this matters, and the third is the one that decides this course. Fewer unknowns: the primal has one variable per parameter, the dual has one per constraint — swap a thousand-variable primal for a three-variable dual and the work collapses. No local traps, by the paragraph above. And the variables change meaning: in a support vector machine the primal is over the weight vector, whose length is the number of features, while the dual is over one multiplier per training point. That swap is what lets kernels in, and it is why we spent this session here.

Does the gap ever actually open? Yes — and it is worth seeing both outcomes. On the gap tab, two allowed bands is a genuinely non-convex problem whose feasible set is two separate intervals, and its gap closes anyway: p⋆=d⋆=−2p^\star=d^\star=-2. Two wells is non-convex and does not close: p⋆=0.3894p^\star=0.3894 while d⋆=0d^\star=0, a gap of 0.38940.3894. Read the lesson in the right direction. Weak duality is free. Convexity plus a strictly feasible point is sufficient for the gap to close — not necessary. Sometimes you get lucky; you just cannot count on it.

One thing remains: the multiplier itself. We have called it a stretch factor, a fine rate, a price. Make that literal.

What a wall is worthThe multiplier is not bookkeeping. It is the price of the wall: move the wall a little and it tells you the new answer before you re-solve anything.

Try: move the wall from 3.003.00 to 2.902.90 and compare the two numbers: the price predicts 9.609.60 and the truth is 9.629.62. Then push the wall below 22 and watch the price fall to zero.

3
—

dp∗/dc=μ∗\mathrm dp^*/\mathrm dc=\mu^*. Below c=2c=2 the wall is not touching, the multiplier is 00, and the value curve is flat — the price of a wall you are not pressed against is nothing. Above it the wall bites, and its price is exactly how fast the bill grows as you push the wall in.

Drag the wall. The answer slides along the path, the score rises, and the chip compares two numbers: what the multiplier predicted and what actually happened. At c=3c=3 the answer is (3,1)(3,1) with μ⋆=4\mu^\star=4 and p⋆=10p^\star=10. Move the wall back to c=2.9c=2.9 and the multiplier says the score should fall by about 4×0.1=0.44\times0.1=0.4, to 9.60\mathbf{9.60}. Re-solve properly and the truth is (2.9,1.1)(2.9,1.1), giving 9.62\mathbf{9.62}.

The realization

μ⋆=∣d p⋆d (how tight the fence is)∣\mu^\star=\left|\frac{\mathrm d\,p^\star}{\mathrm d\,(\text{how tight the fence is})}\right|

The multiplier is the slope of the value function — how much the best achievable score changes per unit of relaxation. It is exact for an infinitesimal move and approximate for a real one (the 0.020.02 discrepancy above is the curvature of the value curve). And watch what happens as you slide the wall left past c=2c=2: the fence stops biting, μ⋆\mu^\star drops to 00, and the value curve goes flat. The price of a wall you are not touching is nothing — which is complementary slackness, arriving from the economics side.

That reading is why multipliers appear all over applied work under the name shadow price. The λ\lambda in ridge regression is the price of the coefficient budget. In a resource allocation, μ\mu is what one more machine-hour is worth to you — before you buy it. It is not bookkeeping left over from a derivation; it is the answer to the question you were going to ask next.

Pause & predict

A colleague computes the dual of a horrible non-convex problem and gets d⋆=7d^\star=7. What have they proved about the primal answer p⋆p^\star?

Pause & predict

At the optimum of a resource problem, the multiplier on the "at most 40 machine-hours" constraint comes out as μ⋆=0\mu^\star=0. Your supplier offers you an extra hour. What is it worth?

If you want the algebra · 3 proofs, step by step
Prove it · moving second is never worse (the minimax inequality)

Claim. For any function φ\varphi of two arguments, max⁡ymin⁡xφ(x,y)≤min⁡xmax⁡yφ(x,y)\displaystyle\max_y\min_x\varphi(x,y)\le\min_x\max_y\varphi(x,y).

1
Name the two optima: let the left side be attained at (xA,yA)(x_A,y_A) and the right side at (xB,yB)(x_B,y_B), so LHS =φ(xA,yA)=\varphi(x_A,y_A) and RHS =φ(xB,yB)=\varphi(x_B,y_B). Two numbers, four points' worth of information. The whole proof is comparing them through a shared middle term.
2
Fix y=yAy=y_A. The left side's inner operation is a minimum over xx, and it returned xAx_A, so it is no larger than the value at any other xx — in particular xBx_B: φ(xA,yA)≤φ(xB,yA).\varphi(x_A,y_A)\le\varphi(x_B,y_A). A minimum is ≤\le any particular value.
3
Fix x=xBx=x_B. The right side's inner operation is a maximum over yy, and it returned yBy_B, so it is no smaller than the value at any other yy — in particular yAy_A: φ(xB,yB)≥φ(xB,yA).\varphi(x_B,y_B)\ge\varphi(x_B,y_A). A maximum is ≥\ge any particular value. The middle term φ(xB,yA)\varphi(x_B,y_A) is the same in both lines — that is the whole trick.
4
Chain them: φ(xA,yA)≤φ(xB,yA)≤φ(xB,yB)\varphi(x_A,y_A)\le\varphi(x_B,y_A)\le\varphi(x_B,y_B). ∎ With φ=L\varphi=L, x=xx=\mathbf x, y=μy=\boldsymbol\mu: d⋆≤p⋆d^\star\le p^\star. No convexity, no differentiability, no assumptions at all — which is why weak duality is free.
5
The one-line version, worth memorising. For any feasible x\mathbf x and any μ≥0\boldsymbol\mu\ge\mathbf 0, d(μ)=min⁡zL(z,μ)≤L(x,μ)=f(x)+μ ⁣⊤g(x) ≤ f(x),\begin{aligned}d(\boldsymbol\mu)&=\min_{\mathbf z}L(\mathbf z,\boldsymbol\mu)\le L(\mathbf x,\boldsymbol\mu)\\[2pt] &=f(\mathbf x)+\boldsymbol\mu^{\!\top}\mathbf g(\mathbf x)\ \le\ f(\mathbf x),\end{aligned} because μ≥0\boldsymbol\mu\ge\mathbf 0 and g(x)≤0\mathbf g(\mathbf x)\le\mathbf 0. Take the best on each side. Every dual value you ever compute is a certified lower bound on the primal answer — even if you never solve the primal.
Prove it · the dual function is always concave

Claim. d(μ)=min⁡x[f(x)+μ ⁣⊤g(x)]d(\boldsymbol\mu)=\min_{\mathbf x}\big[f(\mathbf x)+\boldsymbol\mu^{\!\top}\mathbf g(\mathbf x)\big] is concave in μ\boldsymbol\mu, whatever ff and g\mathbf g are.

1
Fix any single x\mathbf x. As a function of μ\boldsymbol\mu, L(x,μ)=f(x)+μ ⁣⊤g(x)L(\mathbf x,\boldsymbol\mu)=f(\mathbf x)+\boldsymbol\mu^{\!\top}\mathbf g(\mathbf x) is affine: a constant height f(x)f(\mathbf x) plus a constant slope g(x)\mathbf g(\mathbf x). All the nastiness of ff and g\mathbf g has been frozen into two numbers. This is the step that does the work.
2
dd is the pointwise minimum of that whole family of affine functions, one per x\mathbf x. Take any μ1,μ2\boldsymbol\mu_1,\boldsymbol\mu_2 and θ∈[0,1]\theta\in[0,1], and let xθ\mathbf x_\theta attain the minimum at θμ1+(1−θ)μ2\theta\boldsymbol\mu_1+(1-\theta)\boldsymbol\mu_2. Then d(θμ1+(1−θ)μ2)=L(xθ, θμ1+(1−θ)μ2)=θL(xθ,μ1)+(1−θ)L(xθ,μ2)≥θ d(μ1)+(1−θ) d(μ2),\begin{aligned}d\big(\theta\boldsymbol\mu_1+(1-\theta)\boldsymbol\mu_2\big)&=L\big(\mathbf x_\theta,\ \theta\boldsymbol\mu_1+(1-\theta)\boldsymbol\mu_2\big)\\ &=\theta L(\mathbf x_\theta,\boldsymbol\mu_1)+(1-\theta)L(\mathbf x_\theta,\boldsymbol\mu_2)\\ &\ge\theta\,d(\boldsymbol\mu_1)+(1-\theta)\,d(\boldsymbol\mu_2),\end{aligned} the middle line because LL is affine in μ\boldsymbol\mu, the last because L(xθ,⋅)≥d(⋅)L(\mathbf x_\theta,\cdot)\ge d(\cdot) by definition of a minimum. ∎ That is exactly the chord test with the inequality reversed: concave. The picture in the widget is this proof — forty straight lines, and the thing underneath them all bends downward.
3
Say it precisely: the dual function is concave; the dual problem, "maximise a concave function over μ≥0\boldsymbol\mu\ge\mathbf 0", is a convex optimization problem. Both statements are true and they are about different objects. "The dual is convex" is loose talk that costs marks. Be specific about which object you mean.
Prove it · the multiplier is the slope of the value function

Claim. Let p⋆(b)=min⁡f(x)p^\star(b)=\min f(\mathbf x) subject to g(x)≤bg(\mathbf x)\le b. Then dp⋆/db=−μ⋆\mathrm dp^\star/\mathrm db=-\mu^\star — relaxing the fence by ε\varepsilon improves the best score by about μ⋆ε\mu^\star\varepsilon.

1
Write the Lagrangian with the level bb in it: L=f(x)+μ(g(x)−b)L=f(\mathbf x)+\mu\big(g(\mathbf x)-b\big). At the optimum, strong duality gives p⋆(b)=L(x⋆(b),μ⋆(b))p^\star(b)=L(\mathbf x^\star(b),\mu^\star(b)). The value function is the Lagrangian evaluated along the optimal pair — which is what lets us differentiate it.
2
Differentiate in bb. The terms coming from x⋆\mathbf x^\star and μ⋆\mu^\star moving are multiplied by ∂L/∂x=0\partial L/\partial\mathbf x=\mathbf 0 (stationarity) and ∂L/∂μ=g−b=0\partial L/\partial\mu=g-b=0 (the fence is active), so both vanish. Only the explicit bb survives: dp⋆db=∂L∂b=−μ⋆.\frac{\mathrm dp^\star}{\mathrm db}=\frac{\partial L}{\partial b}=-\mu^\star. ∎ This is the envelope argument: at an optimum, first-order changes in the decisions cost nothing, so only the direct effect of the parameter is left.
3
Check it on min⁡x2+y2\min x^2+y^2 s.t. x+y=4, x≥cx+y=4,\ x\ge c. For c≥2c\ge2 the answer is (c,4−c)(c,4-c), so p⋆(c)=c2+(4−c)2p^\star(c)=c^2+(4-c)^2 and dp⋆/dc=4c−8\mathrm dp^\star/\mathrm dc=4c-8, which is 44 at c=3c=3 — exactly μ⋆\mu^\star. Predicting c=2.9c=2.9: 10−4(0.1)=9.6010-4(0.1)=9.60; the truth is 8.41+1.21=9.628.41+1.21=9.62. The 0.020.02 is the curvature of the value function; the multiplier is a derivative, so it is exact only in the limit. And at c≤2c\le2 the fence stops binding, μ⋆=0\mu^\star=0, and p⋆p^\star goes flat at 88 — a wall you are not touching is worth nothing.
In one sentence: Swapping the order of the two moves gives the dual, which is the lowest of a bundle of straight lines and therefore always concave and always a lower bound — and the multiplier it hands back is the price of the wall, the slope of the best achievable score.
14

Two points and a line — where all of this is going

The smallest problem that uses everything

One number line. Two labelled points: x=+1x=+1 is a positive, x=−1x=-1 is a negative. Draw the boundary that separates them with the widest possible gap. You already know where it goes. What you may not know is that finding it uses every single thing in this half of the unit — standard form, the Lagrangian, stationarity, the dual, and complementary slackness — and that the last one explains why these machines are called support vector machines.

Two points and a lineThe widest gap is the smallest 12w2\tfrac12 w^2 that still clears both constraints — and the answer is built out of the multipliers of the points that touch

Try: on add a point, drag the third point in from 33 toward 0.50.5: nothing at all happens until it crosses 11, and then the boundary moves and the point fills in.

1
—

Every point with αi=0\alpha_i=0 could be deleted from the training set and the classifier would not move. That one sentence is where Unit 14 begins.

The trick is the translation. "Widest gap" sounds like a maximisation with no obvious objective, so rescale the boundary until both classes clear it by at least 11: yi(wxi+b)≥1y_i(wx_i+b)\ge1. The margin's width is then 2/∣w∣2/|w|, so making the gap widest means making ∣w∣|w| smallest — and minimising 12w2\tfrac12w^2 subject to two fences is an ordinary quadratic program. Slide ww on the first tab and watch the two constraints go red the moment w<1w<1: w=1w=1 is the smallest value that still clears both.

Now do it the other way, through the dual, because that is how it is actually solved. Stationarity in ww gives w=α1+α2w=\alpha_1+\alpha_2; stationarity in bb gives α1=α2\alpha_1=\alpha_2. Substitute both back and the two primal variables vanish, leaving a one-variable concave problem:

The realization

q(α)=2α−2α2,α⋆=12,d⋆=12=p⋆q(\alpha)=2\alpha-2\alpha^2,\qquad \alpha^\star=\tfrac12,\qquad d^\star=\tfrac12=p^\star

and then the classifier is rebuilt out of the multipliers: w⋆=α1+α2=1w^\star=\alpha_1+\alpha_2=1; and since α1>0\alpha_1>0, complementary slackness forces that point's constraint tight, w+b=1w+b=1, so b⋆=0b^\star=0. Boundary at x=0x=0, margin edges at x=±1x=\pm1, width 2/∣w⋆∣=22/|w^\star|=2. This is the general rule w=∑iαiyixiw=\sum_i\alpha_iy_ix_i with ∑iαiyi=0\sum_i\alpha_iy_i=0, written out for two points.

Then the sentence this whole half of the unit was built for. Drag the third point on the last tab. While it sits out at x=3x=3, comfortably beyond the margin, its constraint is slack — g3<0g_3<0 — so complementary slackness forces α3=0\alpha_3=\mathbf 0. The classifier does not move. You could delete that training point entirely and get the same machine. Drag it inside the margin and its multiplier comes alive, the boundary shifts, and it becomes load-bearing.

That is what "support vector" means: the points whose constraints are tight, the ones with αi>0\alpha_i>0, the only ones carrying the answer. A million training points, a handful of multipliers that are not zero, and the rest could be thrown away. The sparsity of a support vector machine is complementary slackness, and nothing else. It is also why the dual is the form people solve: one multiplier per training point, most of them zero, and the data entering only through products xixjx_ix_j — which is the doorway that kernels walk through.

Units 13 and 14 are that door. You now have the key.

Pause & predict

A trained classifier reports αi=0\alpha_i=0 for 9 9709\,970 of its 10 00010\,000 training points. What does that mean geometrically, and what may you do with those points?

If you want the algebra · 1 proof, step by step
Prove it · the widest margin, solved through its dual

Claim. For x1=+1x_1=+1 (class +1+1) and x2=−1x_2=-1 (class −1-1), minimising 12w2\tfrac12w^2 subject to yi(wxi+b)≥1y_i(wx_i+b)\ge1 has dual q(α)=2α−2α2q(\alpha)=2\alpha-2\alpha^2 with α⋆=12\alpha^\star=\tfrac12, giving w⋆=1w^\star=1, b⋆=0b^\star=0, boundary x=0x=0 and margin width 22; and a third point at x3=3x_3=3 gets α3=0\alpha_3=0.

1
Standard form. For i=1i=1: (+1)(w⋅1+b)≥1(+1)(w\cdot1+b)\ge1, so g1=1−w−b≤0g_1=1-w-b\le0. For i=2i=2: (−1)(w⋅(−1)+b)≥1(-1)(w\cdot(-1)+b)\ge1, i.e. w−b≥1w-b\ge1, so g2=1−w+b≤0g_2=1-w+b\le0. Then L(w,b,α1,α2)=12w2+α1(1−w−b)+α2(1−w+b),αi≥0.\begin{aligned}L(w,b,\alpha_1,\alpha_2)&=\tfrac12w^2+\alpha_1(1-w-b)\\ &\quad+\alpha_2(1-w+b),\qquad \alpha_i\ge0.\end{aligned} Two fences, so m=2m=2; the multipliers are traditionally called α\alpha here rather than μ\mu.
2
Stationarity in the primal variables: ∂L∂w=w−α1−α2=0 ⇒ w=α1+α2,∂L∂b=−α1+α2=0 ⇒ α1=α2.\begin{aligned}\frac{\partial L}{\partial w}&=w-\alpha_1-\alpha_2=0\ \Rightarrow\ w=\alpha_1+\alpha_2,\\[3pt] \frac{\partial L}{\partial b}&=-\alpha_1+\alpha_2=0\ \Rightarrow\ \alpha_1=\alpha_2.\end{aligned} These are the general identities w=∑iαiyixiw=\sum_i\alpha_iy_ix_i and ∑iαiyi=0\sum_i\alpha_iy_i=0, written out for this data. The second is what makes bb drop out of the dual entirely.
3
Substitute. Group L=12w2−w(α1+α2)−b(α1−α2)+(α1+α2)L=\tfrac12w^2-w(\alpha_1+\alpha_2)-b(\alpha_1-\alpha_2)+(\alpha_1+\alpha_2); with α1=α2=α\alpha_1=\alpha_2=\alpha the bb term vanishes and w=2αw=2\alpha: q(α)=12(2α)2−(2α)(2α)+2α=2α2−4α2+2α=2α−2α2.\begin{aligned}q(\alpha)&=\tfrac12(2\alpha)^2-(2\alpha)(2\alpha)+2\alpha\\[2pt] &=2\alpha^2-4\alpha^2+2\alpha=2\alpha-2\alpha^2.\end{aligned} Two primal variables gone, one dual variable left, and the result is a downward parabola — concave, as §13 promised.
4
Maximise over α≥0\alpha\ge0: q′(α)=2−4α=0⇒α⋆=12≥0q'(\alpha)=2-4\alpha=0\Rightarrow\alpha^\star=\tfrac12\ge0 ✓, and d⋆=q(12)=1−12=12d^\star=q(\tfrac12)=1-\tfrac12=\tfrac12. Check the sign rule before reporting — a peak with α<0\alpha<0 would be out of bounds and the best allowed value would sit at α=0\alpha=0.
5
Recover the classifier. w⋆=α1+α2=1w^\star=\alpha_1+\alpha_2=1. Since α1=12>0\alpha_1=\tfrac12>0, complementary slackness forces g1=0g_1=0, i.e. w+b=1w+b=1, so b⋆=0b^\star=0. Primal value 12(1)2=12=d⋆\tfrac12(1)^2=\tfrac12=d^\star: zero gap. Boundary x=0x=0, margin lines x=±1x=\pm1, width 2/∣w⋆∣=22/|w^\star|=2, both points tight and therefore support vectors. Note how bb was recovered — not from stationarity (which only gave α1=α2\alpha_1=\alpha_2) but from a tight constraint identified by a positive multiplier. That is the standard trick.
6
Add x3=3x_3=3, class +1+1. Its constraint is 3w+b≥13w+b\ge1, which at (1,0)(1,0) reads 3≥13\ge1: slack, so g3<0g_3<0 and complementary slackness forces α3=0\alpha_3=0. The point contributes nothing to w=∑αiyixiw=\sum\alpha_iy_ix_i and can be deleted. If instead x3<1x_3<1, it and the negative point become the binding pair, giving w=2x3+1w=\dfrac{2}{x_3+1} and b=1−x31+x3b=\dfrac{1-x_3}{1+x_3} — at x3=0.5x_3=0.5, w=1.3333w=1.3333, b=0.3333b=0.3333, boundary −0.25-0.25, margin 1.51.5. ∎ A million training points, a handful of nonzero multipliers, and the rest deletable: the sparsity of a support vector machine is complementary slackness and nothing else.
In one sentence: The widest margin is the smallest 12w2\tfrac12w^2 that still clears every constraint, its dual has one multiplier per training point, and complementary slackness makes almost all of them zero — which is why the machine is built out of a handful of support vectors.
15

What to carry forward

Two halves, one thread. The first half fixes the walker because one stride can never suit two directions; the second half admits that sometimes the place you want to stand is not allowed, and builds a test for arriving where the ground is still tilted.

The pictureWhat it saysThe line of math it becomes
Walking blindfoldedfeet feel the tilt, never how long it lasts; one stride, two factorswi←(1−ηλi)wiw_i\leftarrow(1-\eta\lambda_i)w_i
The loaded trolleyagreeing pushes stack, alternating pushes cancel; speed costs overshootv←βv−α∇J\mathbf v\leftarrow\beta\mathbf v-\alpha\nabla J; speed-up 1/(1−β)1/(1-\beta)
The permanent recorda stride per knob out of its own history; first step is exactly α\alpha, then the brake never liftsA←A+∇J⊙∇JA\leftarrow A+\nabla J\odot\nabla J; step α/t\alpha/\sqrt t
Form, not career averageforget at rate ρ\rho and the stride survives; the zero start puffs step 1A←ρA+(1−ρ)∇J⊙2A\leftarrow\rho A+(1-\rho)\nabla J^{\odot2}; inflation 1/1−ρ1/\sqrt{1-\rho}
Two notebookssigned average over root squared average; disagreement cancels, loudness divides outαt=α1−ρt/(1−ρft)\alpha_t=\alpha\sqrt{1-\rho^t}/(1-\rho_f^t)
The racethe stiffest direction sets the safe stride, the softest sets the step countα<2/λmax⁡\alpha<2/\lambda_{\max}; cost κ\kappa
The wallthe answer moves onto the boundary, where the gradient is not zeromin⁡f\min f s.t. e=0, gi≤0e=0,\ g_i\le0
The box in the corridoryou stop when nothing of ∇f\nabla f runs along the fence∇f=−μ∇g\nabla f=-\mu\nabla g, parallel not equal
The guard's finean infinite wall rebuilt out of straight lines; a negative fine pays you to trespassL=f+λe+∑μigi, μi≥0L=f+\lambda e+\sum\mu_ig_i,\ \mu_i\ge0
Room leftname the room as a square and differentiate: fine and spare room never coexistg+t2=0⇒μigi=0g+t^2=0\Rightarrow\mu_ig_i=0
The interrogationeach fence is active or not; guess, solve, discard on a negative multiplierfive conditions; 2m2^m branches
The string testnever above its chords, never below its tangents; then a candidate is the answerf(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)f(\theta x+(1-\theta)y)\le\theta f(x)+(1-\theta)f(y)
Who moves firstmoving second is an advantage; the view from below is a bundle of lines, so always a hilld⋆≤p⋆d^\star\le p^\star; dd concave
The price of a wallthe multiplier is the slope of the value function; untouched walls cost nothingμ⋆=∣dp⋆/db∣\mu^\star=|\mathrm dp^\star/\mathrm db|
Two points and a linethe classifier is built from the multipliers, and almost all of them are zeroq(α)=2α−2α2q(\alpha)=2\alpha-2\alpha^2; αi=0⇒\alpha_i=0\Rightarrow deletable
The one thing to remember

Divide by what you have felt, and price what blocks you. Every adaptive method is the same move: measure how loud a knob's slopes have been, divide its stride by that, and the curvature never reaches the step size — momentum adds memory so agreement compounds, forgetting keeps the brake from becoming a life sentence, and Adam does all three with a start-up correction that retires itself. Every constrained method is the other same move: replace each wall by the cheapest straight line that does its job, and the price of that line tells you three things at once — which way the answer is pinned, whether the wall matters at all, and exactly what you would pay to move it.

16

Practice arena — fourteen problems, solved in full

Fourteen problems, easy to hard, across both halves: descent on a two-knob fit and recovering the stride from where it landed, four logged runs read backwards, exact line search, momentum's hyperparameters recovered from three numbers, AdaGrad against RMSProp on a long slope, RMSProp in vector form on badly scaled columns, Adam by hand with its bias correction — then framing a word problem, standard form and the branch count, a quadratic form on the unit circle where the multiplier is the eigenvalue, a fence tested both ways, the full four-case enumeration, a primal-and-dual round trip with the shadow price, and a two-point classifier built from its multipliers. Every number is machine-verified.

Three habits do most of the work. For any optimizer question, tabulate before you calculate — one row per step, columns for the gradient, the accumulators and the new point, in that fixed order; nearly every lost mark is a value used one step out of date. For any constrained question, write the standard form first and keep the minus signs — x≥2x\ge2 is g=2−xg=2-x, so ∇g=−1\nabla g=-1. And never stop at the first case that works: test every branch, or say in writing why a branch is impossible.

Problem 1easy

A straight line y^=wx+b\hat y=wx+b is fitted to the two points (1,3)(1,3) and (2,5)(2,5) by minimising L(w,b)=12[(w+b−3)2+(2w+b−5)2]L(w,b)=\tfrac12\big[(w+b-3)^2+(2w+b-5)^2\big]. (a) Derive ∂L/∂w\partial L/\partial w and ∂L/∂b\partial L/\partial b in simplest form and write the two update lines. (b) From (w0,b0)=(0,0)(w_0,b_0)=(0,0) with α=0.1\alpha=0.1, run two iterations; report (w1,b1)(w_1,b_1), (w2,b2)(w_2,b_2) and the loss after each. (c) A second run started from the same (0,0)(0,0) with a different rate and landed at (0.26, 0.16)(0.26,\,0.16) after one step. Recover that rate and check it on both coordinates. (d) From the Hessian of LL, give the two eigenvalues, the largest safe rate, and decide whether α=0.3\alpha=0.3 is safe — and by how much.

The five rules used throughout this set. All start from the current point wt\mathbf w_t with gt=∇f(wt)\mathbf g_t=\nabla f(\mathbf w_t); squares, roots and divisions of vectors are taken element by element; ϵ≈10−8\epsilon\approx10^{-8} only prevents division by zero and is dropped in hand calculation.

methodrule
gradient descentwt+1=wt−αgt\mathbf w_{t+1}=\mathbf w_t-\alpha\mathbf g_t
momentumvt+1=βvt−αgt,wt+1=wt+vt+1,v0=0\mathbf v_{t+1}=\beta\mathbf v_t-\alpha\mathbf g_t,\quad \mathbf w_{t+1}=\mathbf w_t+\mathbf v_{t+1},\quad \mathbf v_0=\mathbf 0
AdaGradGt+1=Gt+gt2,wt+1=wt−αGt+1 gt,G0=0G_{t+1}=G_t+\mathbf g_t^2,\quad \mathbf w_{t+1}=\mathbf w_t-\dfrac{\alpha}{\sqrt{G_{t+1}}}\,\mathbf g_t,\quad G_0=0
RMSPropAt+1=ρAt+(1−ρ)gt2,wt+1=wt−αAt+1 gt,A0=0A_{t+1}=\rho A_t+(1-\rho)\mathbf g_t^2,\quad \mathbf w_{t+1}=\mathbf w_t-\dfrac{\alpha}{\sqrt{A_{t+1}}}\,\mathbf g_t,\quad A_0=0
Adammt=β1mt−1+(1−β1)gt−1,  vt=β2vt−1+(1−β2)gt−12m_t=\beta_1m_{t-1}+(1-\beta_1)g_{t-1},\ \ v_t=\beta_2v_{t-1}+(1-\beta_2)g_{t-1}^2
m^t=mt1−β1 t,  v^t=vt1−β2 t,  wt=wt−1−αv^t m^t\hat m_t=\dfrac{m_t}{1-\beta_1^{\,t}},\ \ \hat v_t=\dfrac{v_t}{1-\beta_2^{\,t}},\ \ w_t=w_{t-1}-\dfrac{\alpha}{\sqrt{\hat v_t}}\,\hat m_t

What this tests. Chain rule into a gradient, the plain rule run without slips, the fact that one step is exactly α\alpha times the gradient vector — so a landing point hands α\alpha back — and the speed limit α<2/λmax⁡\alpha<2/\lambda_{\max}. Plan. Differentiate each square by the chain rule and collect; then per iteration in this order: gradient at the current point, update both knobs with that same gradient, loss at the new point; for (c) write one step with α\alpha unknown and solve from each coordinate; for (d) read trace and determinant off the Hessian.

Show the full solution
(a) Step 1 — differentiate, do not expand. Each term is 12(stuff)2\tfrac12(\text{stuff})^2, whose derivative is (stuff)×(derivative of the stuff)(\text{stuff})\times(\text{derivative of the stuff}). The ww-derivative of w+b−3w+b-3 is 11; of 2w+b−52w+b-5 it is 22: ∂L∂w=(w+b−3)(1)+(2w+b−5)(2)=w+b−3+4w+2b−10=5w+3b−13.\begin{aligned} \frac{\partial L}{\partial w}&=(w+b-3)(1)+(2w+b-5)(2)\\ &=w+b-3+4w+2b-10\\ &=5w+3b-13. \end{aligned} Both bb-derivatives are 11: ∂L∂b=(w+b−3)+(2w+b−5)=3w+2b−8.\begin{aligned} \frac{\partial L}{\partial b}&=(w+b-3)+(2w+b-5)\\ &=3w+2b-8. \end{aligned} So the two update lines are w←w−α (5w+3b−13),b←b−α (3w+2b−8).\begin{aligned} w&\leftarrow w-\alpha\,(5w+3b-13),\\ b&\leftarrow b-\alpha\,(3w+2b-8). \end{aligned}
(b) Step 2 — iteration 1 from (0,0)(0,0). Gradient first: ∂L∂w∣(0,0)=5(0)+3(0)−13=−13,∂L∂b∣(0,0)=3(0)+2(0)−8=−8,L0=12[(−3)2+(−5)2]=12(34)=17.\begin{aligned} \frac{\partial L}{\partial w}\Big|_{(0,0)}&=5(0)+3(0)-13=-13,\\ \frac{\partial L}{\partial b}\Big|_{(0,0)}&=3(0)+2(0)-8=-8,\\ L_0&=\tfrac12\big[(-3)^2+(-5)^2\big]=\tfrac12(34)=17. \end{aligned} Now move both knobs with that one gradient: w1=0−0.1(−13)=1.3,b1=0−0.1(−8)=0.8.\begin{aligned} w_1&=0-0.1(-13)=1.3,\\ b_1&=0-0.1(-8)=0.8. \end{aligned} The new loss, residual by residual: w1+b1−3=1.3+0.8−3=−0.9,2w1+b1−5=2.6+0.8−5=−1.6,L1=12[0.81+2.56]=12(3.37)=1.685.\begin{aligned} w_1+b_1-3&=1.3+0.8-3=-0.9,\\ 2w_1+b_1-5&=2.6+0.8-5=-1.6,\\ L_1&=\tfrac12\big[0.81+2.56\big]\\ &=\tfrac12(3.37)=1.685. \end{aligned}
Step 3 — iteration 2. New gradient at (1.3,0.8)(1.3,0.8): ∂L∂w=5(1.3)+3(0.8)−13=6.5+2.4−13=−4.1,∂L∂b=3(1.3)+2(0.8)−8=3.9+1.6−8=−2.5.\begin{aligned} \frac{\partial L}{\partial w}&=5(1.3)+3(0.8)-13\\ &=6.5+2.4-13=-4.1,\\ \frac{\partial L}{\partial b}&=3(1.3)+2(0.8)-8\\ &=3.9+1.6-8=-2.5. \end{aligned} w2=1.3+0.1(4.1)=1.71,b2=0.8+0.1(2.5)=1.05.\begin{aligned} w_2&=1.3+0.1(4.1)=1.71,\\ b_2&=0.8+0.1(2.5)=1.05. \end{aligned} w2+b2−3=1.71+1.05−3=−0.24,2w2+b2−5=3.42+1.05−5=−0.53,L2=12[0.0576+0.2809]=12(0.3385)=0.16925.\begin{aligned} w_2+b_2-3&=1.71+1.05-3=-0.24,\\ 2w_2+b_2-5&=3.42+1.05-5=-0.53,\\ L_2&=\tfrac12\big[0.0576+0.2809\big]\\ &=\tfrac12(0.3385)=0.16925. \end{aligned} The whole run on one page:
tt(wt,bt)(w_t,b_t)∇L\nabla LLL
0(0, 0)(0,\,0)(−13, −8)(-13,\,-8)1717
1(1.3, 0.8)(1.3,\,0.8)(−4.1, −2.5)(-4.1,\,-2.5)1.6851.685
2(1.71, 1.05)(1.71,\,1.05)—0.169250.16925
Two steps cut the bill from 1717 to 0.1690.169, a factor of about 100100. (The exact fit is w=2, b=1w=2,\ b=1, where L=0L=0.)
(c) Step 4 — read the rate off the landing point. One step from (0,0)(0,0) with the gradient (−13,−8)(-13,-8) is (w1,b1)=(0+13α, 0+8α).(w_1,b_1)=\big(0+13\alpha,\ 0+8\alpha\big). Match each coordinate: 13α=0.26 ⇒ α=0.2613=0.02,8α=0.16 ⇒ α=0.168=0.02.\begin{aligned} 13\alpha&=0.26\ \Rightarrow\ \alpha=\tfrac{0.26}{13}=0.02,\\ 8\alpha&=0.16\ \Rightarrow\ \alpha=\tfrac{0.16}{8}=0.02. \end{aligned} Both coordinates give α=0.02\alpha=0.02 — the agreement is the check that the run really was plain gradient descent.
(d) Step 5 — curvature, eigenvalues, speed limit. Differentiate the two partials once more: H=[5332],tr⁡H=7,det⁡H=10−9=1.H=\begin{bmatrix}5&3\\3&2\end{bmatrix},\quad \operatorname{tr}H=7,\quad \det H=10-9=1. Eigenvalues from λ2−(tr⁡)λ+det⁡=0\lambda^2-(\operatorname{tr})\lambda+\det=0: λ2−7λ+1=0,λ=7±49−42=7±452,λmax⁡=6.854102,λmin⁡=0.145898.\begin{aligned} \lambda^2-7\lambda+1&=0,\\ \lambda&=\frac{7\pm\sqrt{49-4}}{2}=\frac{7\pm\sqrt{45}}{2},\\ \lambda_{\max}&=6.854102,\\ \lambda_{\min}&=0.145898. \end{aligned} The safe range is α<2/λmax⁡\alpha<2/\lambda_{\max}: 2λmax⁡=26.854102=0.291796,0.3−0.291796=0.008204.\begin{aligned} \frac{2}{\lambda_{\max}}&=\frac{2}{6.854102}=0.291796,\\ 0.3-0.291796&=0.008204. \end{aligned} So α=0.3\alpha=0.3 is not safe — but it misses by only 0.0082040.008204, about 2.8%2.8\% over the limit, so the divergence would be slow and easy to mistake for noise. (The condition number λmax⁡/λmin⁡=46.98\lambda_{\max}/\lambda_{\min}=46.98 is what makes the safe window so narrow in the first place.)

answers at a glance: (a) ∂L/∂w=5w+3b−13\partial L/\partial w=5w+3b-13, ∂L/∂b=3w+2b−8\partial L/\partial b=3w+2b-8. (b) L0=17L_0=17; (w1,b1)=(1.3,0.8)(w_1,b_1)=(1.3,0.8), L1=1.685L_1=1.685; (w2,b2)=(1.71,1.05)(w_2,b_2)=(1.71,1.05), L2=0.16925L_2=0.16925. (c) α=0.02\alpha=0.02, from both coordinates. (d) λ=6.854102, 0.145898\lambda=6.854102,\ 0.145898; safe for α<0.291796\alpha<0.291796; 0.30.3 is unsafe by 0.0082040.008204.

Remember

One step is exactly α\alpha times the gradient vector, which is why a landing point gives α\alpha back — and why both coordinates must agree. The classic slip is updating ww first and then using the new ww inside the bb-gradient: both knobs must move on the same old gradient. The second slip is testing safety against λmin⁡\lambda_{\min}; the speed limit is set by the steepest direction, 2/λmax⁡2/\lambda_{\max}.

Problem 2easy

Four runs on f(x)=x2f(x)=x^2 were logged, all starting from x0=1x_0=1. A: 1, 0.8, 0.64, 0.5121,\ 0.8,\ 0.64,\ 0.512. B: 1, −0.5, 0.25, −0.1251,\ -0.5,\ 0.25,\ -0.125. C: 1, −1.2, 1.44, −1.7281,\ -1.2,\ 1.44,\ -1.728. D: 1, 0.8, 0.54, 0.3021,\ 0.8,\ 0.54,\ 0.302. (a) Three of the four are plain gradient descent. Name them, give each one's α\alpha, and list the five bands of behaviour of α\alpha on this loss. (b) Name the odd run out, recover its α\alpha and its β\beta (momentum, v0=0\mathbf v_0=0), and verify them on its third step. (c) Re-run B with the decaying rate αt=0.75/(1+t)\alpha_t=0.75/(1+t): give α0,α1,α2\alpha_0,\alpha_1,\alpha_2 and x1,x2,x3x_1,x_2,x_3. (d) Give the first tt with αt<0.1\alpha_t<0.1 and that αt\alpha_t; the percentage drop from α0\alpha_0; and the first tt at which the factor 1−2αt1-2\alpha_t turns positive, so the sign stops flipping.

What this tests. Diagnosis: on x2x^2 every plain run is a geometric sequence, so the ratio is the fingerprint, and a run whose ratio drifts must be carrying the loaded trolley. Plan. Divide each term by the one before; a constant ratio identifies plain descent and gives α\alpha from 1−2α1-2\alpha; for the drifting run use v0=0\mathbf v_0=0 to get α\alpha from step 1 alone, then β\beta from step 2, then check step 3; finally do the decay arithmetic with two inequalities.

Show the full solution
(a) Step 1 — the fingerprint. On f=x2f=x^2 the gradient is 2x2x, so plain descent reads xt+1=xt−α(2xt)=(1−2α) xt.x_{t+1}=x_t-\alpha(2x_t)=(1-2\alpha)\,x_t. Every step multiplies by the same number, so a constant ratio means plain descent, and the ratio is 1−2α1-2\alpha. Divide:
runratios1−2α1-2\alphaα\alphabehaviour
A0.8, 0.8, 0.80.8,\ 0.8,\ 0.80.80.80.10.1monotone
B−0.5, −0.5, −0.5-0.5,\ -0.5,\ -0.5−0.5-0.50.750.75oscillating, shrinking
C−1.2, −1.2, −1.2-1.2,\ -1.2,\ -1.2−1.2-1.21.11.1diverging
D0.8, 0.675, 0.55930.8,\ 0.675,\ 0.5593——not plain
The three α\alpha values come straight out of 1−2α1-2\alpha: 1−2α=0.8 ⇒ α=0.1,1−2α=−0.5 ⇒ α=0.75,1−2α=−1.2 ⇒ α=1.1.\begin{aligned} 1-2\alpha&=0.8\ \Rightarrow\ \alpha=0.1,\\ 1-2\alpha&=-0.5\ \Rightarrow\ \alpha=0.75,\\ 1-2\alpha&=-1.2\ \Rightarrow\ \alpha=1.1. \end{aligned} The five bands, all read off ∣1−2α∣|1-2\alpha|:
range of α\alphafactor 1−2α1-2\alphawhat happens
0<α<0.50<\alpha<0.5in (0,1)(0,1)monotone descent
α=0.5\alpha=0.500lands on 00 in one step
0.5<α<10.5<\alpha<1in (−1,0)(-1,0)oscillates, still converges
α=1\alpha=1−1-1permanent oscillation ±1\pm1
α>1\alpha>1<−1<-1diverges
(b) Step 2 — D is the loaded trolley. Its ratios 0.8, 0.675, 0.55930.8,\ 0.675,\ 0.5593 shrink instead of repeating, so no single α\alpha explains it. Momentum starts with an empty trolley, v0=0v_0=0, so its first step is pure descent: v1=−α g(1)=−α(2)=−2α,x1=1−2α=0.8 ⇒ α=0.1,v1=−0.2.\begin{aligned} v_1&=-\alpha\,g(1)=-\alpha(2)=-2\alpha,\\ x_1&=1-2\alpha=0.8\ \Rightarrow\ \alpha=0.1,\\ v_1&=-0.2. \end{aligned} Now step 2 is the only place β\beta appears: g(0.8)=1.6,v2=β(−0.2)−0.1(1.6)=−0.2β−0.16,x2=0.8+v2=0.64−0.2β.\begin{aligned} g(0.8)&=1.6,\\ v_2&=\beta(-0.2)-0.1(1.6)\\ &=-0.2\beta-0.16,\\ x_2&=0.8+v_2=0.64-0.2\beta. \end{aligned} Set that to the logged 0.540.54: 0.64−0.2β=0.54 ⇒ β=0.5.0.64-0.2\beta=0.54\ \Rightarrow\ \beta=0.5.
Step 3 — verify on the third step. With β=0.5\beta=0.5, v2=−0.2(0.5)−0.16=−0.26v_2=-0.2(0.5)-0.16=-0.26: g(0.54)=1.08,v3=0.5(−0.26)−0.1(1.08)=−0.13−0.108=−0.238,x3=0.54−0.238=0.302.\begin{aligned} g(0.54)&=1.08,\\ v_3&=0.5(-0.26)-0.1(1.08)\\ &=-0.13-0.108=-0.238,\\ x_3&=0.54-0.238=0.302. \end{aligned} That is the logged value exactly, so (α,β)=(0.1, 0.5)(\alpha,\beta)=(0.1,\,0.5) is confirmed. ✓
(c) Step 4 — B again, with a fading rate. αt=0.75/(1+t)\alpha_t=0.75/(1+t): α0=0.751=0.75,α1=0.752=0.375,α2=0.753=0.25.\begin{aligned} \alpha_0&=\tfrac{0.75}{1}=0.75,\\ \alpha_1&=\tfrac{0.75}{2}=0.375,\\ \alpha_2&=\tfrac{0.75}{3}=0.25. \end{aligned} The factors 1−2αt1-2\alpha_t are −0.5, 0.25, 0.5-0.5,\ 0.25,\ 0.5, so x1=(−0.5)(1)=−0.5,x2=(0.25)(−0.5)=−0.125,x3=(0.5)(−0.125)=−0.0625.\begin{aligned} x_1&=(-0.5)(1)=-0.5,\\ x_2&=(0.25)(-0.5)=-0.125,\\ x_3&=(0.5)(-0.125)=-0.0625. \end{aligned} Compare with the constant-rate run B — 1, −0.5, 0.25, −0.1251,\,-0.5,\,0.25,\,-0.125 — which flipped sign every single step. Fading the rate killed the flipping after one step and still reached a smaller ∣x∣|x| by step 3 (0.06250.0625 against 0.1250.125).
(d) Step 5 — three small inequalities. First, when the rate drops below 0.10.1: 0.751+t<0.11+t>7.5t≥7,α7=0.758=0.09375.\begin{aligned} \frac{0.75}{1+t}&<0.1\\ 1+t&>7.5\\ t&\ge7,\qquad \alpha_7=\tfrac{0.75}{8}=0.09375. \end{aligned} The drop from the start: 0.75−0.093750.75=0.656250.75=0.875=87.5%.\frac{0.75-0.09375}{0.75}=\frac{0.65625}{0.75}=0.875=87.5\%. Finally, when the factor stops being negative: 1−1.51+t>01+t>1.5t≥1.\begin{aligned} 1-\frac{1.5}{1+t}&>0\\ 1+t&>1.5\\ t&\ge1. \end{aligned} So t=1t=1 is the first index with a positive factor: the step taken at t=0t=0 is the last one that flips the sign, and from x1x_1 onward every iterate stays negative — exactly what the numbers in (c) show.

answers at a glance: (a) A, B, C are plain, with α=0.1, 0.75, 1.1\alpha=0.1,\ 0.75,\ 1.1; bands 0<α<0.50<\alpha<0.5 monotone, α=0.5\alpha=0.5 one step, 0.5<α<10.5<\alpha<1 oscillating convergence, α=1\alpha=1 permanent oscillation, α>1\alpha>1 divergence. (b) D is momentum with α=0.1\alpha=0.1, β=0.5\beta=0.5; step-3 check x3=0.302x_3=0.302. (c) α=0.75, 0.375, 0.25\alpha=0.75,\,0.375,\,0.25; x=−0.5, −0.125, −0.0625x=-0.5,\,-0.125,\,-0.0625. (d) t=7t=7, α7=0.09375\alpha_7=0.09375; 87.5%87.5\% drop; the factor turns positive at t=1t=1.

Remember

On a quadratic, plain descent is a geometric sequence — so always divide consecutive iterates first. A constant ratio means plain descent and hands you α\alpha; a drifting ratio means something is carrying memory. The slip is trying to fit β\beta from step 1, where the trolley is still empty and β\beta cannot appear: step 1 gives α\alpha, step 2 gives β\beta, step 3 checks them both.

Problem 3medium

Let f(x,y)=2x2+xy+y2−2x−yf(x,y)=2x^2+xy+y^2-2x-y, which is 12w ⁣⊤Aw−b ⁣⊤w\tfrac12\mathbf w^{\!\top}A\mathbf w-\mathbf b^{\!\top}\mathbf w with A=[4112]A=\begin{bmatrix}4&1\\1&2\end{bmatrix} and b=(2,1)\mathbf b=(2,1); start at w0=(0,0)\mathbf w_0=(0,0), where ∇f=(4x+y−2, x+2y−1)\nabla f=(4x+y-2,\ x+2y-1). (a) With direction d1=(1,0)\mathbf d_1=(1,0), show it is a descent direction, write h(α)=f(w0+αd1)h(\alpha)=f(\mathbf w_0+\alpha\mathbf d_1), minimise it exactly, and give w1\mathbf w_1 and f(w1)f(\mathbf w_1). (b) Take d2=−∇f(w1)\mathbf d_2=-\nabla f(\mathbf w_1) and repeat: give h(α)h(\alpha), α2∗\alpha_2^*, w2\mathbf w_2 and f(w2)f(\mathbf w_2). (c) Derive the closed form α∗=−∇f(w) ⁣⊤dd ⁣⊤Ad\alpha^*=-\dfrac{\nabla f(\mathbf w)^{\!\top}\mathbf d}{\mathbf d^{\!\top}A\mathbf d} and evaluate it for (a) and (b). (d) Give the exact minimiser w∗\mathbf w^* and f∗f^*, and the amount by which f(w2)f(\mathbf w_2) still exceeds f∗f^*. Also verify the free check ∇f(w1) ⁣⊤d1=0\nabla f(\mathbf w_1)^{\!\top}\mathbf d_1=0 and ∇f(w2) ⁣⊤d2=0\nabla f(\mathbf w_2)^{\!\top}\mathbf d_2=0.

What this tests. That "how far do I walk?" is itself a one-variable minimisation, that on a quadratic it has a formula, and that an exact line search always leaves the new gradient perpendicular to the direction just walked. Plan. Substitute the line into ff to get a parabola in α\alpha; set h′(α)=0h'(\alpha)=0; step; repeat once; then do the same substitution with symbols to get the formula, and finish with ∇f=0\nabla f=\mathbf 0 for the exact answer.

Show the full solution
(a) Step 1 — is d1\mathbf d_1 downhill? At w0=(0,0)\mathbf w_0=(0,0), ∇f(w0)=(−2, −1),∇f ⁣⊤d1=−2<0,\nabla f(\mathbf w_0)=(-2,\,-1),\qquad \nabla f^{\!\top}\mathbf d_1=-2<0, so yes: moving along +x+x lowers ff.
Step 2 — the walk becomes a parabola. Put (x,y)=(α,0)(x,y)=(\alpha,0) into ff: h(α)=2α2+α(0)+0−2α−0=2α2−2α.\begin{aligned} h(\alpha)&=2\alpha^2+\alpha(0)+0-2\alpha-0\\ &=2\alpha^2-2\alpha. \end{aligned} Minimise it: h′(α)=4α−2=0,α1∗=0.5,h′′=4>0.\begin{aligned} h'(\alpha)&=4\alpha-2=0,\\ \alpha_1^*&=0.5,\qquad h''=4>0. \end{aligned} w1=(0,0)+0.5(1,0)=(0.5, 0),f(w1)=2(0.25)−2(0.5)=−0.5.\begin{aligned} \mathbf w_1&=(0,0)+0.5(1,0)=(0.5,\,0),\\ f(\mathbf w_1)&=2(0.25)-2(0.5)=-0.5. \end{aligned}
(b) Step 3 — the second leg. The gradient at w1\mathbf w_1: ∇f(w1)=(4(0.5)+0−2, 0.5+0−1)=(0, −0.5),d2=−∇f(w1)=(0, 0.5).\begin{aligned} \nabla f(\mathbf w_1)&=\big(4(0.5)+0-2,\ 0.5+0-1\big)\\ &=(0,\,-0.5),\\ \mathbf d_2&=-\nabla f(\mathbf w_1)=(0,\,0.5). \end{aligned} The line is (0.5, 0.5α)(0.5,\,0.5\alpha). Substitute, term by term: 2x2=2(0.25)=0.5,xy=0.5(0.5α)=0.25α,y2=0.25α2,−2x=−1,−y=−0.5α.\begin{aligned} 2x^2&=2(0.25)=0.5,\\ xy&=0.5(0.5\alpha)=0.25\alpha,\\ y^2&=0.25\alpha^2,\\ -2x&=-1,\qquad -y=-0.5\alpha. \end{aligned} Add: h(α)=0.25α2+0.25α−0.5α+0.5−1=0.25α2−0.25α−0.5.\begin{aligned} h(\alpha)&=0.25\alpha^2+0.25\alpha-0.5\alpha+0.5-1\\ &=0.25\alpha^2-0.25\alpha-0.5. \end{aligned} h′(α)=0.5α−0.25=0,α2∗=0.5,w2=(0.5, 0)+0.5(0,0.5)=(0.5, 0.25),f(w2)=0.25(0.25)−0.25(0.5)−0.5=0.0625−0.125−0.5=−0.5625.\begin{aligned} h'(\alpha)&=0.5\alpha-0.25=0,\\ \alpha_2^*&=0.5,\\ \mathbf w_2&=(0.5,\,0)+0.5(0,0.5)\\ &=(0.5,\,0.25),\\ f(\mathbf w_2)&=0.25(0.25)-0.25(0.5)-0.5\\ &=0.0625-0.125-0.5=-0.5625. \end{aligned}
(c) Step 4 — the formula, once and for all. Expand f(w+αd)f(\mathbf w+\alpha\mathbf d) with f=12w ⁣⊤Aw−b ⁣⊤wf=\tfrac12\mathbf w^{\!\top}A\mathbf w-\mathbf b^{\!\top}\mathbf w: f(w+αd)=12(w+αd) ⁣⊤A(w+αd)−b ⁣⊤(w+αd).\begin{aligned} f(\mathbf w+\alpha\mathbf d)&=\tfrac12(\mathbf w+\alpha\mathbf d)^{\!\top}A(\mathbf w+\alpha\mathbf d)\\ &\qquad-\mathbf b^{\!\top}(\mathbf w+\alpha\mathbf d). \end{aligned} Because AA is symmetric, w ⁣⊤Ad=d ⁣⊤Aw\mathbf w^{\!\top}A\mathbf d=\mathbf d^{\!\top}A\mathbf w, so the two cross terms merge: =f(w)+α d ⁣⊤(Aw−b)+α22 d ⁣⊤Ad.\begin{aligned} &=f(\mathbf w)+\alpha\,\mathbf d^{\!\top}(A\mathbf w-\mathbf b)\\ &\qquad+\tfrac{\alpha^2}{2}\,\mathbf d^{\!\top}A\mathbf d. \end{aligned} But Aw−b=∇f(w)A\mathbf w-\mathbf b=\nabla f(\mathbf w), so this is a parabola in α\alpha with slope ∇f ⁣⊤d\nabla f^{\!\top}\mathbf d and curvature d ⁣⊤Ad\mathbf d^{\!\top}A\mathbf d. Setting the derivative to zero: α∗=−∇f(w) ⁣⊤dd ⁣⊤Ad.\alpha^*=-\frac{\nabla f(\mathbf w)^{\!\top}\mathbf d}{\mathbf d^{\!\top}A\mathbf d}. Check it on both legs: (a)d1 ⁣⊤Ad1=4,α1∗=−−24=0.5 ✓(b)∇f(w1) ⁣⊤d2=−0.25,d2 ⁣⊤Ad2=2(0.5)2=0.5,α2∗=−−0.250.5=0.5 ✓\begin{aligned} \text{(a)}\quad \mathbf d_1^{\!\top}A\mathbf d_1&=4,\\ \alpha_1^*&=-\frac{-2}{4}=0.5\ \checkmark\\ \text{(b)}\quad \nabla f(\mathbf w_1)^{\!\top}\mathbf d_2&=-0.25,\\ \mathbf d_2^{\!\top}A\mathbf d_2&=2(0.5)^2=0.5,\\ \alpha_2^*&=-\frac{-0.25}{0.5}=0.5\ \checkmark \end{aligned}
(d) Step 5 — the exact bottom, and how close we got. Set ∇f=0\nabla f=\mathbf 0: 4x+y=2,x+2y=1.\begin{aligned} 4x+y&=2,\\ x+2y&=1. \end{aligned} From the first, y=2−4xy=2-4x; substitute: x+2(2−4x)=1,−7x=−3,x=37,y=2−127=27.\begin{aligned} x+2(2-4x)&=1,\\ -7x&=-3,\qquad x=\tfrac37,\\ y&=2-\tfrac{12}{7}=\tfrac27. \end{aligned} Evaluate over a denominator of 4949: f∗=1849+649+449−4249−1449=−2849=−47≈−0.571429.\begin{aligned} f^*&=\tfrac{18}{49}+\tfrac{6}{49}+\tfrac{4}{49}-\tfrac{42}{49}-\tfrac{14}{49}\\ &=-\tfrac{28}{49}=-\tfrac47\approx-0.571429. \end{aligned} Two exact line searches got to −0.5625-0.5625, still −0.5625−(−0.571429)=0.008929-0.5625-(-0.571429)=0.008929 above the floor.
Step 6 — the free check. After an exact line search the parabola is at its bottom, so the directional derivative along d\mathbf d is zero — i.e. the new gradient is perpendicular to the direction just walked: ∇f(w1) ⁣⊤d1=(0,−0.5)⋅(1,0)=0,∇f(w2)=(0.25, 0),∇f(w2) ⁣⊤d2=(0.25,0)⋅(0,0.5)=0.\begin{aligned} \nabla f(\mathbf w_1)^{\!\top}\mathbf d_1&=(0,-0.5)\cdot(1,0)=0,\\ \nabla f(\mathbf w_2)&=(0.25,\,0),\\ \nabla f(\mathbf w_2)^{\!\top}\mathbf d_2&=(0.25,0)\cdot(0,0.5)=0. \end{aligned} Both are exactly zero, which is why consecutive exact-search directions turn a right angle — the zig-zag is not a bug, it is a theorem.

answers at a glance: (a) descent since −2<0-2<0; h=2α2−2αh=2\alpha^2-2\alpha, α1∗=0.5\alpha_1^*=0.5, w1=(0.5,0)\mathbf w_1=(0.5,0), f=−0.5f=-0.5. (b) h=0.25α2−0.25α−0.5h=0.25\alpha^2-0.25\alpha-0.5, α2∗=0.5\alpha_2^*=0.5, w2=(0.5,0.25)\mathbf w_2=(0.5,0.25), f=−0.5625f=-0.5625. (c) α∗=−∇f ⁣⊤d/(d ⁣⊤Ad)\alpha^*=-\nabla f^{\!\top}\mathbf d/(\mathbf d^{\!\top}A\mathbf d); 2/4=0.52/4=0.5 and 0.25/0.5=0.50.25/0.5=0.5. (d) w∗=(3/7, 2/7)\mathbf w^*=(3/7,\,2/7), f∗=−4/7≈−0.571429f^*=-4/7\approx-0.571429, excess 0.0089290.008929; both orthogonality checks give 00.

Remember

"How far?" is its own one-variable problem, and on a quadratic its answer is −∇f ⁣⊤d/(d ⁣⊤Ad)-\nabla f^{\!\top}\mathbf d/(\mathbf d^{\!\top}A\mathbf d) — slope over curvature, measured along the direction you are actually walking. Always spend the one line on ∇f(wnew) ⁣⊤d=0\nabla f(\mathbf w_{\text{new}})^{\!\top}\mathbf d=0: if it is not zero, the line search was not exact. The slip is minimising ff over (x,y)(x,y) instead of over the single number α\alpha.

Problem 4medium

A run of momentum on f(x)=(x−5)2f(x)=(x-5)^2 starts at x0=0x_0=0 with v0=0v_0=0; the log records x1=1.0x_1=1.0 and x2=2.6x_2=2.6, and nothing else. (a) Recover α\alpha and β\beta, in that order, saying why the order is forced. (b) Continue the run: give f′(x2)f'(x_2), v3v_3, x3x_3, f′(x3)f'(x_3), v4v_4 and x4x_4. (c) Run plain gradient descent from x0=0x_0=0 with the same α\alpha for four steps, and give the two distances from the target x=5x=5 after four steps — one for momentum, one for plain descent — saying which is past and which is short.

What this tests. Reading the loaded trolley backwards: v0=0\mathbf v_0=0 makes the first step pure descent, so α\alpha falls out alone and β\beta shows up only at step 2 — and then whether you can see the overshoot that memory buys. Plan. One step with α\alpha unknown; one step with β\beta unknown; then roll the recursion forward two more rows; finally run the plain map x←0.8x+1x\leftarrow0.8x+1 four times and subtract.

Show the full solution
(a) Step 1 — step 1 has no β\beta in it. The gradient is f′(x)=2(x−5)f'(x)=2(x-5), so f′(0)=−10f'(0)=-10. With v0=0v_0=0, v1=β(0)−α(−10)=10α,x1=0+10α=1.0,α=0.1,v1=1.0.\begin{aligned} v_1&=\beta(0)-\alpha(-10)=10\alpha,\\ x_1&=0+10\alpha=1.0,\\ \alpha&=0.1,\qquad v_1=1.0. \end{aligned} The empty trolley is what makes this identification possible: β\beta multiplies v0=0v_0=0 and disappears.
Step 2 — β\beta from the second step. f′(1.0)=2(1−5)=−8f'(1.0)=2(1-5)=-8: v2=β(1.0)−0.1(−8)=β+0.8,x2=1.0+β+0.8=1.8+β,1.8+β=2.6 ⇒ β=0.8,v2=1.6.\begin{aligned} v_2&=\beta(1.0)-0.1(-8)=\beta+0.8,\\ x_2&=1.0+\beta+0.8=1.8+\beta,\\ 1.8+\beta&=2.6\ \Rightarrow\ \beta=0.8,\\ v_2&=1.6. \end{aligned}
(b) Step 3 — two more rows. f′(2.6)=2(2.6−5)=−4.8,v3=0.8(1.6)−0.1(−4.8)=1.28+0.48=1.76,x3=2.6+1.76=4.36.\begin{aligned} f'(2.6)&=2(2.6-5)=-4.8,\\ v_3&=0.8(1.6)-0.1(-4.8)\\ &=1.28+0.48=1.76,\\ x_3&=2.6+1.76=4.36. \end{aligned} f′(4.36)=2(4.36−5)=−1.28,v4=0.8(1.76)−0.1(−1.28)=1.408+0.128=1.536,x4=4.36+1.536=5.896.\begin{aligned} f'(4.36)&=2(4.36-5)=-1.28,\\ v_4&=0.8(1.76)-0.1(-1.28)\\ &=1.408+0.128=1.536,\\ x_4&=4.36+1.536=5.896. \end{aligned} Note what happened at the last row: the pull 0.1280.128 was tiny, but the trolley still carried 1.4081.408 — so the walker sailed straight past 55.
ttxtx_tf′(xt)f'(x_t)vt+1v_{t+1}
000−10-101.01.0
11.01.0−8-81.61.6
22.62.6−4.8-4.81.761.76
34.364.36−1.28-1.281.5361.536
45.8965.896——
(c) Step 4 — the same rate without the trolley. Plain descent is x←x−0.1⋅2(x−5)=x−0.2x+1=0.8x+1.\begin{aligned} x&\leftarrow x-0.1\cdot2(x-5)\\ &=x-0.2x+1=0.8x+1. \end{aligned} Four applications from 00: x1=0.8(0)+1=1,x2=0.8(1)+1=1.8,x3=0.8(1.8)+1=2.44,x4=0.8(2.44)+1=2.952.\begin{aligned} x_1&=0.8(0)+1=1,\\ x_2&=0.8(1)+1=1.8,\\ x_3&=0.8(1.8)+1=2.44,\\ x_4&=0.8(2.44)+1=2.952. \end{aligned} The two distances after four steps: momentum: 5.896−5=0.896 past,plain: 5−2.952=2.048 short.\begin{aligned} \text{momentum: }&5.896-5=0.896\ \text{past},\\ \text{plain: }&5-2.952=2.048\ \text{short}. \end{aligned} Same α\alpha, same four steps: memory covered 5.8965.896 of the ground while plain descent covered 2.9522.952 — but it bought that speed with an overshoot of 0.8960.896, which it will now have to walk back.

answers at a glance: (a) α=0.1\alpha=0.1 (from step 1, where v0=0v_0=0 hides β\beta), then β=0.8\beta=0.8. (b) f′(2.6)=−4.8f'(2.6)=-4.8, v3=1.76v_3=1.76, x3=4.36x_3=4.36; f′(4.36)=−1.28f'(4.36)=-1.28, v4=1.536v_4=1.536, x4=5.896x_4=5.896. (c) plain run 1, 1.8, 2.44, 2.9521,\ 1.8,\ 2.44,\ 2.952; momentum ends 0.8960.896 past the target, plain descent 2.0482.048 short of it.

Remember

v0=0\mathbf v_0=\mathbf 0 is the crack that lets you read a momentum log backwards: step 1 is pure descent and gives α\alpha; only step 2 can give β\beta. The slip is fitting both at once from step 2 and getting a whole family of answers. The second thing to keep: momentum overshoots by design — the trolley keeps rolling after the slope has flattened — which is exactly what makes it fast in a long valley and jumpy near the bottom.

Problem 5medium

A single weight sits on a long, perfectly straight slope: dL/dw=g=4\mathrm dL/\mathrm dw=g=4 at every iteration. Take α=1\alpha=1 and ignore ϵ\epsilon. (a) Give AdaGrad's accumulator GtG_t in closed form, show its step size is α/t\alpha/\sqrt t, and give the first four step sizes. (b) Give the first tt at which AdaGrad's step has fallen below 10%10\% of α\alpha. (c) For RMSProp with ρ=0.5\rho=0.5, prove At=g2(1−ρ t)A_t=g^2(1-\rho^{\,t}) by unrolling the geometric series, then give the first four step sizes and the value they approach. (d) Give the two limits as t→∞t\to\infty and the step each method takes at t=100t=100, plus the ratio between them.

What this tests. The permanent record against form-not-career-average, on the one input where they visibly disagree: a slope that never changes. Plan. Sum tt copies of g2g^2 for AdaGrad and cancel gg against g2\sqrt{g^2}; for RMSProp unroll At=ρAt−1+(1−ρ)g2A_t=\rho A_{t-1}+(1-\rho)g^2 into a geometric series and use 1+ρ+⋯+ρt−1=(1−ρ t)/(1−ρ)1+\rho+\dots+\rho^{t-1}=(1-\rho^{\,t})/(1-\rho); then two limits and one division.

Show the full solution
(a) Step 1 — the permanent record never forgets. AdaGrad adds g2g^2 every iteration and never subtracts, so after tt iterations Gt=g2+g2+⋯+g2⏟t terms=t g2=16t.G_t=\underbrace{g^2+g^2+\dots+g^2}_{t\ \text{terms}}=t\,g^2=16t. The step size is therefore α gGt=α gt g2=α g∣g∣t=αt\begin{aligned} \frac{\alpha\,g}{\sqrt{G_t}}&=\frac{\alpha\,g}{\sqrt{t\,g^2}}=\frac{\alpha\,g}{|g|\sqrt t}=\frac{\alpha}{\sqrt t} \end{aligned} for g>0g>0. The size of the slope cancels completely — only the count of steps survives. With α=1\alpha=1: t=1:1/1=1,t=2:1/2=0.70711,t=3:1/3=0.57735,t=4:1/4=0.5.\begin{aligned} t=1:&\quad 1/\sqrt1=1,\\ t=2:&\quad 1/\sqrt2=0.70711,\\ t=3:&\quad 1/\sqrt3=0.57735,\\ t=4:&\quad 1/\sqrt4=0.5. \end{aligned} (Arithmetic check: G1=16, 16=4, αg/G1=4/4=1G_1=16,\ \sqrt{16}=4,\ \alpha g/\sqrt{G_1}=4/4=1 ✓; G2=32, 32=5.65685, 4/5.65685=0.70711G_2=32,\ \sqrt{32}=5.65685,\ 4/5.65685=0.70711 ✓.)
(b) Step 2 — when the record strangles the walker. αt<0.1 αt>10t>100,\begin{aligned} \frac{\alpha}{\sqrt t}&<0.1\,\alpha\\ \sqrt t&>10\\ t&>100, \end{aligned} so from t=101t=101 onward. At t=100t=100 the step is exactly 0.1α0.1\alpha; at t=101t=101 it is 0.099504α0.099504\alpha. Nothing about the problem changed — the brake came purely from the step count.
(c) Step 3 — unroll RMSProp. Write c=1−ρc=1-\rho and start from A0=0A_0=0: A1=c g2,A2=ρ c g2+c g2=c g2(1+ρ),A3=c g2(1+ρ+ρ2),At=c g2(1+ρ+⋯+ρ t−1).\begin{aligned} A_1&=c\,g^2,\\ A_2&=\rho\,c\,g^2+c\,g^2=c\,g^2(1+\rho),\\ A_3&=c\,g^2(1+\rho+\rho^2),\\ A_t&=c\,g^2\big(1+\rho+\dots+\rho^{\,t-1}\big). \end{aligned} The bracket is a geometric series: 1+ρ+⋯+ρ t−1=1−ρ t1−ρ,At=(1−ρ)g2⋅1−ρ t1−ρ=g2(1−ρ t).\begin{aligned} 1+\rho+\dots+\rho^{\,t-1}&=\frac{1-\rho^{\,t}}{1-\rho},\\ A_t&=(1-\rho)g^2\cdot\frac{1-\rho^{\,t}}{1-\rho}\\ &=g^2\big(1-\rho^{\,t}\big). \end{aligned} So the step size is αgg2(1−ρ t)=α1−ρ t.\frac{\alpha g}{\sqrt{g^2(1-\rho^{\,t})}}=\frac{\alpha}{\sqrt{1-\rho^{\,t}}}. With ρ=0.5\rho=0.5 and α=1\alpha=1: t=1: 1/0.5=1.41421,t=2: 1/0.75=1.15470,t=3: 1/0.875=1.06904,t=4: 1/0.9375=1.03280.\begin{aligned} t=1:&\ 1/\sqrt{0.5}=1.41421,\\ t=2:&\ 1/\sqrt{0.75}=1.15470,\\ t=3:&\ 1/\sqrt{0.875}=1.06904,\\ t=4:&\ 1/\sqrt{0.9375}=1.03280. \end{aligned} As tt grows, ρ t→0\rho^{\,t}\to0 and the step settles at α=1\alpha=1. Notice it comes down to α\alpha from above: the empty notebook at t=1t=1 makes the first step 1/1−ρ=1.414211/\sqrt{1-\rho}=1.41421 times too big, and that inflation fades.
(d) Step 4 — the two limits, side by side. AdaGrad: αt⟶0,RMSProp: α1−ρ t⟶α=1.\begin{aligned} \text{AdaGrad: }&\frac{\alpha}{\sqrt t}\longrightarrow 0,\\ \text{RMSProp: }&\frac{\alpha}{\sqrt{1-\rho^{\,t}}}\longrightarrow \alpha=1. \end{aligned} At t=100t=100: AdaGrad: 1100=0.1,RMSProp: 11−0.5100=1.0000,ratio: 1.00000.1=10.\begin{aligned} \text{AdaGrad: }&\frac{1}{\sqrt{100}}=0.1,\\ \text{RMSProp: }&\frac{1}{\sqrt{1-0.5^{100}}}=1.0000,\\ \text{ratio: }&\frac{1.0000}{0.1}=10. \end{aligned} (0.5100≈7.9×10−310.5^{100}\approx7.9\times10^{-31}, so RMSProp's step at t=100t=100 is 11 to thirty decimal places.) On a slope that genuinely never ends, AdaGrad is ten times slower than RMSProp by step 100 and the gap keeps widening as t\sqrt t.

answers at a glance: (a) Gt=16tG_t=16t, step =α/t=\alpha/\sqrt t: 1, 0.70711, 0.57735, 0.51,\ 0.70711,\ 0.57735,\ 0.5. (b) from t=101t=101. (c) At=g2(1−ρ t)A_t=g^2(1-\rho^{\,t}), step =α/1−ρ t=\alpha/\sqrt{1-\rho^{\,t}}: 1.41421, 1.15470, 1.06904, 1.03280→α=11.41421,\ 1.15470,\ 1.06904,\ 1.03280\to\alpha=1. (d) limits 00 and α=1\alpha=1; at t=100t=100, 0.10.1 versus 1.00001.0000, a ratio of 1010.

Remember

Both methods divide by a root of remembered squares; the only difference is whether the memory is a permanent record (AdaGrad, sum) or recent form (RMSProp, fading average). On a constant slope that difference is α/t→0\alpha/\sqrt t\to0 against α/1−ρ t→α\alpha/\sqrt{1-\rho^{\,t}}\to\alpha — a brake that never lifts, against one that lifts after a few steps. The slip is thinking AdaGrad's shrinking step means "converging": here nothing has converged at all, the walker has simply been throttled.

Problem 6hard

A model y^=w1x1+w2x2\hat y=w_1x_1+w_2x_2 is fitted to two rows, (10,1)↦21(10,1)\mapsto21 and (10,−1)↦19(10,-1)\mapsto19, with L=12∑i(y^i−yi)2L=\tfrac12\sum_i(\hat y_i-y_i)^2. (a) Write ∂L/∂wj\partial L/\partial w_j in terms of the residuals and evaluate ∇L\nabla L at w0=(0,0)\mathbf w_0=(0,0). (b) Give H=X ⁣⊤XH=X^{\!\top}X, the range of α\alpha for which plain descent is stable, the optimum w∗\mathbf w^*, and — at α=0.005\alpha=0.005 — the first move of w2w_2, its per-step contraction factor, the number of steps it needs to close 99%99\% of its gap, and what w1w_1 does in one step. (c) Run RMSProp with ρ=0.9\rho=0.9, α=0.3\alpha=0.3 for two steps, showing AtA_t, At\sqrt{A_t} and the step vector each time. (d) Give w2w_2 after two RMSProp steps and after two plain steps at α=0.005\alpha=0.005, and the ratio.

What this tests. The whole reason per-weight step sizes exist: one column is ten times bigger than the other, so the curvature ratio is a hundred, and one shared rate cannot serve both. Plan. Residual times feature, summed, gives the gradient; X ⁣⊤XX^{\!\top}X gives the curvature and the speed limit; then run RMSProp in vector form keeping every intermediate to six decimals — the point is that its two steps come out equal on the first iteration even though the gradients differ by a factor of 200200.

Show the full solution
(a) Step 1 — gradient as residual times feature. With ri=y^i−yir_i=\hat y_i-y_i, ∂L∂wj=∑iri xij.\frac{\partial L}{\partial w_j}=\sum_i r_i\,x_{ij}. At w0=(0,0)\mathbf w_0=(0,0) both predictions are 00, so r=(−21, −19)r=(-21,\,-19) and ∂L∂w1=(−21)(10)+(−19)(10)=−210−190=−400,∂L∂w2=(−21)(1)+(−19)(−1)=−21+19=−2.\begin{aligned} \frac{\partial L}{\partial w_1}&=(-21)(10)+(-19)(10)\\ &=-210-190=-400,\\ \frac{\partial L}{\partial w_2}&=(-21)(1)+(-19)(-1)\\ &=-21+19=-2. \end{aligned} So ∇L=(−400, −2)\nabla L=(-400,\,-2): the two partials differ by a factor of 200200 at the very first point, purely because column 1 is ten times larger.
(b) Step 2 — curvature, speed limit, optimum. With X=[10110−1]X=\begin{bmatrix}10&1\\10&-1\end{bmatrix}, X ⁣⊤X=[100+10010−1010−101+1]=[200002].\begin{aligned} X^{\!\top}X&=\begin{bmatrix}100+100&10-10\\10-10&1+1\end{bmatrix}\\ &=\begin{bmatrix}200&0\\0&2\end{bmatrix}. \end{aligned} Diagonal, so the two coordinates never talk to each other; the eigenvalues are 200200 and 22 and the condition number is 100100. Stability needs α<2/λmax⁡\alpha<2/\lambda_{\max}: 0<α<2200=0.01.0<\alpha<\frac{2}{200}=0.01. The optimum solves X ⁣⊤Xw=X ⁣⊤yX^{\!\top}X\mathbf w=X^{\!\top}\mathbf y with X ⁣⊤y=(400, 2)X^{\!\top}\mathbf y=(400,\,2): w∗=(400200, 22)=(2, 1).\mathbf w^*=\Big(\tfrac{400}{200},\ \tfrac{2}{2}\Big)=(2,\,1). Now take the largest rate the problem allows on the small side, α=0.005\alpha=0.005: Δw2=0.005×2=0.01,factor=1−0.005(2)=0.99,0.99 n≤0.01n≥ln⁡0.01ln⁡0.99=458.21,\begin{aligned} \Delta w_2&=0.005\times2=0.01,\\ \text{factor}&=1-0.005(2)=0.99,\\ 0.99^{\,n}&\le0.01\\ n&\ge\frac{\ln0.01}{\ln0.99}=458.21, \end{aligned} so 459459 steps — call it about 460460 — for w2w_2 to close 99%99\% of its gap. Meanwhile factor for w1=1−0.005(200)=0,\text{factor for }w_1=1-0.005(200)=0, so w1w_1 lands exactly on 22 in a single step and then never moves again. One rate, two completely different lives: one knob finished before the first step ended, the other needs four hundred and fifty-nine.
(c) Step 3 — RMSProp, first iteration. ρ=0.9\rho=0.9, α=0.3\alpha=0.3, A0=0A_0=\mathbf 0, g0=(−400,−2)\mathbf g_0=(-400,-2): A1=0.1 g02=0.1(160000, 4)=(16000, 0.4),A1=(126.4911, 0.632456).\begin{aligned} A_1&=0.1\,\mathbf g_0^2=0.1(160000,\,4)\\ &=(16000,\ 0.4),\\ \sqrt{A_1}&=(126.4911,\ 0.632456). \end{aligned} step=0.3(−400)126.4911, 0.3(−2)0.632456=(−0.948683, −0.948683),w1=(0.948683, 0.948683).\begin{aligned} \text{step}&=\frac{0.3(-400)}{126.4911},\ \frac{0.3(-2)}{0.632456}\\ &=(-0.948683,\ -0.948683),\\ \mathbf w_1&=(0.948683,\ 0.948683). \end{aligned} The two moves are identical although the gradients differed by 200×200\times: on the first step A1=0.1 ∣g∣\sqrt{A_1}=\sqrt{0.1}\,|g|, so gg cancels and every coordinate moves α/1−ρ=0.948683\alpha/\sqrt{1-\rho}=0.948683 in the downhill direction.
Step 4 — second iteration. New predictions and residuals: y^1=10(0.948683)+0.948683=10.435516,r1=10.435516−21=−10.564484,y^2=10(0.948683)−0.948683=8.538150,r2=8.538150−19=−10.461850.\begin{aligned} \hat y_1&=10(0.948683)+0.948683\\ &=10.435516,\\ r_1&=10.435516-21=-10.564484,\\ \hat y_2&=10(0.948683)-0.948683\\ &=8.538150,\\ r_2&=8.538150-19=-10.461850. \end{aligned} New gradient: g1,1=10(−10.564484)+10(−10.461850)=−210.263340,g1,2=(−10.564484)−(−10.461850)=−0.102633.\begin{aligned} g_{1,1}&=10(-10.564484)+10(-10.461850)\\ &=-210.263340,\\ g_{1,2}&=(-10.564484)-(-10.461850)\\ &=-0.102633. \end{aligned} Fade the notebook and add the new squares: A2=0.9(16000, 0.4)+0.1 (44210.67, 0.010534)=(18821.067, 0.3610534),A2=(137.189895, 0.600877).\begin{aligned} A_2&=0.9(16000,\,0.4)\\ &\quad+0.1\,(44210.67,\ 0.010534)\\ &=(18821.067,\ 0.3610534),\\ \sqrt{A_2}&=(137.189895,\ 0.600877). \end{aligned} step=0.3(−210.263340)137.189895,0.3(−0.102633)0.600877=(−0.459793, −0.051242),w2=(1.408477, 0.999925).\begin{aligned} \text{step}&=\frac{0.3(-210.263340)}{137.189895},\\ &\qquad\frac{0.3(-0.102633)}{0.600877}\\ &=(-0.459793,\ -0.051242),\\ \mathbf w_2&=(1.408477,\ 0.999925). \end{aligned} Two steps have taken w2w_2 to within 0.0000750.000075 of its optimum 11.
(d) Step 5 — the comparison in one line. Two plain steps at α=0.005\alpha=0.005 leave w2w_2 at w2(1)=0+0.005(2)=0.01,w2(2)=0.01+0.005(1.98)=0.0199.\begin{aligned} w_2^{(1)}&=0+0.005(2)=0.01,\\ w_2^{(2)}&=0.01+0.005(1.98)=0.0199. \end{aligned} Against RMSProp's 0.9999250.999925: 0.9999250.0199=50.25.\frac{0.999925}{0.0199}=50.25. RMSProp has moved the stiff knob fifty times further in the same two steps — and it did it without needing to know that column 2 was small, because the notebook measured that for itself.

answers at a glance: (a) r=(−21,−19)r=(-21,-19), ∇L=(−400, −2)\nabla L=(-400,\,-2). (b) H=diag⁡(200,2)H=\operatorname{diag}(200,2), stable for 0<α<0.010<\alpha<0.01, w∗=(2,1)\mathbf w^*=(2,1); at α=0.005\alpha=0.005: Δw2=0.01\Delta w_2=0.01, factor 0.990.99, 459459 steps for 99%99\%, and w1w_1's factor is 00 so it lands in one step. (c) w1=(0.948683, 0.948683)\mathbf w_1=(0.948683,\,0.948683); w2=(1.408477, 0.999925)\mathbf w_2=(1.408477,\,0.999925). (d) 0.9999250.999925 versus 0.01990.0199, a ratio of 50.2550.25.

Remember

Divide by the root of a remembered square and the gradient's size cancels — what is left is its direction, times a step the method sets for each weight separately. That is why RMSProp's first move is α/1−ρ\alpha/\sqrt{1-\rho} in every coordinate no matter how lopsided the columns are. The slip is fading the notebook with the new squared gradient on the first step and forgetting the 1−ρ1-\rho factor: A1=(1−ρ)g02A_1=(1-\rho)g_0^2, not g02g_0^2.

Problem 7hard

Three gradients were logged for one weight: g0=6, g1=−4, g2=2g_0=6,\ g_1=-4,\ g_2=2. Run Adam by hand with α=0.1\alpha=0.1, β1=0.9\beta_1=0.9, β2=0.999\beta_2=0.999, m0=v0=0m_0=v_0=0 and w0=1w_0=1. (a) Tabulate t=1,2,3t=1,2,3: first the two correction denominators 1−β1 t1-\beta_1^{\,t} and 1−β2 t1-\beta_2^{\,t}, then mt, vt, m^t, v^t, v^tm_t,\ v_t,\ \hat m_t,\ \hat v_t,\ \sqrt{\hat v_t}, the ratio m^t/v^t\hat m_t/\sqrt{\hat v_t} and wtw_t. (b) Give the three iterates plain gradient descent would have produced at the same α\alpha on the same gradients. (c) Give the three Adam step sizes, and give the number m^2/v^2\hat m_2/\sqrt{\hat v_2} together with the two averages that produced it — say which average can cancel and which cannot.

What this tests. The two notebooks and the probation rate, in full arithmetic: a signed average on top, a squared average underneath, and a start-up correction that makes step 1 honest. Plan. Compute the two denominators first — they are the same every run and are where most slips live — then one row at a time; never reuse a corrected value in the next row's recursion (the recursion runs on the raw mt,vtm_t,v_t).

Show the full solution
(a) Step 1 — the two probation denominators. 1−β1 t: 0.1,0.19,0.271,1−β2 t: 0.001,  0.001999,0.002997001.\begin{aligned} 1-\beta_1^{\,t}&:\ 0.1,\quad 0.19,\quad 0.271,\\ 1-\beta_2^{\,t}&:\ 0.001,\ \ 0.001999,\\ &\qquad\quad 0.002997001. \end{aligned} (1−0.92=1−0.81=0.191-0.9^2=1-0.81=0.19; 1−0.93=1−0.729=0.2711-0.9^3=1-0.729=0.271; 1−0.9992=1−0.998001=0.0019991-0.999^2=1-0.998001=0.001999; 1−0.9993=1−0.997002999=0.0029970011-0.999^3=1-0.997002999=0.002997001.) Both start tiny and climb toward 11, which is exactly what inflates the nearly empty notebooks back to honest size.
Step 2 — t=1t=1, using g0=6g_0=6. m1=0.9(0)+0.1(6)=0.6,v1=0.999(0)+0.001(36)=0.036,m^1=0.60.1=6,v^1=0.0360.001=36,v^1=6,m^1v^1=66=1,w1=1−0.1(1)=0.9.\begin{aligned} m_1&=0.9(0)+0.1(6)=0.6,\\ v_1&=0.999(0)+0.001(36)=0.036,\\ \hat m_1&=\frac{0.6}{0.1}=6,\\ \hat v_1&=\frac{0.036}{0.001}=36,\\ \sqrt{\hat v_1}&=6,\\ \frac{\hat m_1}{\sqrt{\hat v_1}}&=\frac66=1,\\ w_1&=1-0.1(1)=0.9. \end{aligned} The ratio is exactly 11: after correction the first step is α\alpha in the downhill direction, whatever the gradient was.
Step 3 — t=2t=2, using g1=−4g_1=-4. m2=0.9(0.6)+0.1(−4)=0.54−0.4=0.14,v2=0.999(0.036)+0.001(16)=0.035964+0.016=0.051964.\begin{aligned} m_2&=0.9(0.6)+0.1(-4)\\ &=0.54-0.4=0.14,\\ v_2&=0.999(0.036)+0.001(16)\\ &=0.035964+0.016=0.051964. \end{aligned} m^2=0.140.19=0.736842,v^2=0.0519640.001999=25.994997,v^2=5.098529,m^2v^2=0.144521,w2=0.9−0.1(0.144521)=0.885548.\begin{aligned} \hat m_2&=\frac{0.14}{0.19}=0.736842,\\ \hat v_2&=\frac{0.051964}{0.001999}=25.994997,\\ \sqrt{\hat v_2}&=5.098529,\\ \frac{\hat m_2}{\sqrt{\hat v_2}}&=0.144521,\\ w_2&=0.9-0.1(0.144521)\\ &=0.885548. \end{aligned}
Step 4 — t=3t=3, using g2=2g_2=2. m3=0.9(0.14)+0.1(2)=0.126+0.2=0.326,v3=0.999(0.051964)+0.001(4)=0.051912036+0.004=0.055912036.\begin{aligned} m_3&=0.9(0.14)+0.1(2)\\ &=0.126+0.2=0.326,\\ v_3&=0.999(0.051964)+0.001(4)\\ &=0.051912036+0.004\\ &=0.055912036. \end{aligned} m^3=0.3260.271=1.202952,v^3=0.0559120360.002997001=18.655995,v^3=4.319259,m^3v^3=0.278509,w3=0.885548−0.0278509=0.857697.\begin{aligned} \hat m_3&=\frac{0.326}{0.271}=1.202952,\\ \hat v_3&=\frac{0.055912036}{0.002997001}\\ &=18.655995,\\ \sqrt{\hat v_3}&=4.319259,\\ \frac{\hat m_3}{\sqrt{\hat v_3}}&=0.278509,\\ w_3&=0.885548-0.0278509\\ &=0.857697. \end{aligned} The whole run:
ttmtm_tvtv_tm^t\hat m_tv^t\sqrt{\hat v_t}ratiowtw_t
10.60.60.0360.0366666110.90.9
20.140.140.0519640.0519640.7368420.7368425.0985295.0985290.1445210.1445210.8855480.885548
30.3260.3260.0559120.0559121.2029521.2029524.3192594.3192590.2785090.2785090.8576970.857697
(b) Step 5 — what plain descent would have done. w←w−0.1gw\leftarrow w-0.1g on the same three gradients: w1=1−0.1(6)=0.4,w2=0.4−0.1(−4)=0.8,w3=0.8−0.1(2)=0.6.\begin{aligned} w_1&=1-0.1(6)=0.4,\\ w_2&=0.4-0.1(-4)=0.8,\\ w_3&=0.8-0.1(2)=0.6. \end{aligned} Plain descent lurched 0.60.6, then 0.40.4 back, then 0.20.2 forward — total travel 1.21.2 to end 0.40.4 from the start. Adam travelled 0.1420.142 in total and ended 0.1420.142 from the start: same three gradients, a tenth of the thrashing.
(c) Step 6 — the three step sizes, and why the middle one is tiny. Each step is α\alpha times the ratio: t=1: 0.1(1)=0.1,t=2: 0.1(0.144521)=0.014452,t=3: 0.1(0.278509)=0.027851.\begin{aligned} t=1:&\ 0.1(1)=0.1,\\ t=2:&\ 0.1(0.144521)=0.014452,\\ t=3:&\ 0.1(0.278509)=0.027851. \end{aligned} The middle ratio is m^2/v^2=0.736842/5.098529=0.144521\hat m_2/\sqrt{\hat v_2}=0.736842/5.098529=0.144521. Look at what each average did with the pair (6,−4)(6,-4): signed top: 0.9(0.6)+0.1(−4)=0.14,squared bottom: 0.999(0.036)+0.001(16)=0.051964.\begin{aligned} \text{signed top: }&0.9(0.6)+0.1(-4)=0.14,\\ \text{squared bottom: }&0.999(0.036)+0.001(16)\\ &=0.051964. \end{aligned} The top averages signed gradients, so +6+6 and −4-4 nearly cancel and the numerator collapses to 0.140.14. The bottom averages squares, which are all positive and can never cancel, so it stays large. A ratio of about 0.140.14 is Adam saying: "the last two reports disagreed about the direction, so take a small step until they agree again."

answers at a glance: (a) denominators 0.1, 0.19, 0.2710.1,\,0.19,\,0.271 and 0.001, 0.001999, 0.0029970010.001,\,0.001999,\,0.002997001; w1=0.9w_1=0.9, w2=0.885548w_2=0.885548, w3=0.857697w_3=0.857697. (b) plain descent gives 0.4, 0.8, 0.60.4,\ 0.8,\ 0.6. (c) step sizes 0.1, 0.014452, 0.0278510.1,\ 0.014452,\ 0.027851; m^2/v^2=0.144521\hat m_2/\sqrt{\hat v_2}=0.144521, small because the signed average 0.140.14 nearly cancelled while the squared average 0.0519640.051964 could not.

Remember

Adam divides a signed average by the root of a squared average: disagreement shrinks the numerator but never the denominator, so conflicting gradients automatically produce small steps. The probation correction is what makes step 1 come out at exactly α\alpha. The slip is feeding the corrected m^t,v^t\hat m_t,\hat v_t back into the next row — the recursion always runs on the raw mt,vtm_t,v_t, and the correction is applied fresh each time.

Problem 8easy

You have 2020 metres of fencing and want to enclose the largest possible rectangular plot. (a) Name the decision variables, the objective and the constraint, and reduce the perimeter equation to its simplest form. (b) Solve with one multiplier: give λ∗\lambda^*, x∗x^*, y∗y^* and the area A∗A^*, and confirm it is a maximum by eliminating one variable. (c) The fencing budget rises to 2222 metres. Give the new optimum and area, the gain the multiplier predicts, the gain that actually occurs, the difference between them, and the exact value function A∗(s)A^*(s) together with its slope at s=10s=10.

What this tests. Framing — what may I choose, what do I want, what limits me — and then the multiplier's second life as the price of a wall: how much the best attainable value improves per unit of extra budget. Plan. Three sentences of framing, then ∇f=λ∇h\nabla f=\lambda\nabla h and the constraint; then re-solve at the new budget and compare λ Δs\lambda\,\Delta s against the true jump, and explain the difference with the value function.

Show the full solution
(a) Step 1 — frame it in three lines. Let x>0x>0 be the width and y>0y>0 the height, in metres. The area to maximise is f(x,y)=xyf(x,y)=xy. The fencing is all used, so the perimeter is 2x+2y=20 ⟹ h(x,y)=x+y−10=0.2x+2y=20\ \Longrightarrow\ h(x,y)=x+y-10=0. Framed problem: max⁡x,y xy\max_{x,y}\,xy subject to x+y=10x+y=10. Call the half-perimeter s=10s=10 the budget; it is the thing whose price we will ask for in (c).
(b) Step 2 — one multiplier. ∇f=(y,x)\nabla f=(y,x) and ∇h=(1,1)\nabla h=(1,1), so ∇f=λ∇h\nabla f=\lambda\nabla h reads y=λ(1)=λ,x=λ(1)=λ.\begin{aligned} y&=\lambda(1)=\lambda,\\ x&=\lambda(1)=\lambda. \end{aligned} Both equations say the same thing, x=y=λx=y=\lambda. Feed that into the constraint: λ+λ=10,λ∗=5,x∗=y∗=5,A∗=5×5=25 m2.\begin{aligned} \lambda+\lambda&=10,\\ \lambda^*&=5,\qquad x^*=y^*=5,\\ A^*&=5\times5=25\ \text{m}^2. \end{aligned} Confirm it is a maximum without any second-derivative test: on the constraint line y=10−xy=10-x, so A(x)=x(10−x)=10x−x2,A(x)=x(10-x)=10x-x^2, a downward parabola whose single critical point is its peak, and whose value collapses to 00 at both ends x→0x\to0 and x→10x\to10. The square wins.
(c) Step 3 — the price of a wall. With 2222 m the budget becomes s=11s=11, i.e. x+y=11x+y=11; the same algebra gives x∗=y∗=5.5,A∗=5.5×5.5=30.25 m2.\begin{aligned} x^*=y^*&=5.5,\\ A^*&=5.5\times5.5=30.25\ \text{m}^2. \end{aligned} Compare the prediction with the fact: predicted gain=λ∗ Δs=5(1)=5,true gain=30.25−25=5.25,difference=0.25.\begin{aligned} \text{predicted gain}&=\lambda^*\,\Delta s=5(1)=5,\\ \text{true gain}&=30.25-25=5.25,\\ \text{difference}&=0.25. \end{aligned}
Step 4 — where the missing 0.250.25 lives. Solve at a general budget ss: x∗=y∗=s/2x^*=y^*=s/2, so the exact value function is A∗(s)=(s2)2=s24,dA∗ds=s2.A^*(s)=\Big(\frac s2\Big)^2=\frac{s^2}{4},\qquad \frac{\mathrm dA^*}{\mathrm ds}=\frac s2. At s=10s=10 that slope is 55 — which is exactly λ∗\lambda^*. So the multiplier is the derivative of the best attainable value with respect to the budget, and a derivative is only exact for an infinitesimal change. Over a whole unit the curve bends upward: A∗(11)−A∗(10)=121−1004=214=5.25,linear part=5,curvature part=(Δs)24=0.25.\begin{aligned} A^*(11)-A^*(10)&=\frac{121-100}{4}=\frac{21}{4}=5.25,\\ \text{linear part}&=5,\\ \text{curvature part}&=\frac{(\Delta s)^2}{4}=0.25. \end{aligned} The 0.250.25 is precisely the quadratic term of s2/4s^2/4. Ask the multiplier for a small favour and it answers exactly; ask it for a big one and it under-promises.

answers at a glance: (a) variables x,y>0x,y>0; max⁡xy\max xy subject to x+y−10=0x+y-10=0. (b) λ∗=5\lambda^*=5, x∗=y∗=5x^*=y^*=5, A∗=25A^*=25 m². (c) new optimum 5.5, 5.55.5,\ 5.5 with A∗=30.25A^*=30.25; predicted gain 55, true gain 5.255.25, difference 0.250.25; A∗(s)=s2/4A^*(s)=s^2/4 with slope s/2=5s/2=5 at s=10s=10.

Remember

The multiplier is not a bookkeeping nuisance — it is the price of one more unit of budget, λ=dA∗/ds\lambda=\mathrm dA^*/\mathrm ds, available before you re-solve anything. The slip is expecting that price to be exact for a large change: it is a slope, so it captures the straight-line part and misses the curvature (here 55 predicted against 5.255.25 delivered). The second slip is forgetting to divide the perimeter by 22 and carrying 2x+2y−202x+2y-20, which scales λ\lambda by a half.

Problem 9easy

(a) Put each of these into the standard form min⁡f\min f subject to e=0, g≤0e=0,\ g\le0, keeping every sign explicit and giving the gradient of each converted rule: (i) x≥2x\ge2; (ii) x+2y≥5x+2y\ge5; (iii) 3x−y≤73x-y\le7; (iv) x+y=1x+y=1; (v) max⁡xy\max xy; (vi) x>2x>2 — for this last one, state what goes wrong and name the value that cannot be attained. (b) Complementary slackness splits the search into branches. Give the number of branches for m=1,2,3,4,10m=1,2,3,4,10 fences, and say for which of m=2,3,4m=2,3,4 the guess m2m^2 happens to agree with the true count and for which it fails, with both numbers. (c) For a problem with one path and no fences, name which of the five conditions are empty and write down what survives. (d) In the slack formulation with nn variables and mm fences, count the unknowns; evaluate for n=2, m=2n=2,\ m=2.

What this tests. The bookkeeping that everything else rests on — every rule pushed to the ≤0\le0 side, every maximisation flipped — and the size of the branching interrogation that complementary slackness sets up. Plan. Move everything to one side so the right-hand side is 00 and the sense is ≤\le; negate the objective to flip a max; then count branches as 22 per inequality and nothing per equality.

Show the full solution
(a) Step 1 — six conversions.
as writtenstandard formgradient
x≥2x\ge2g=2−x≤0g=2-x\le0∇g=(−1)\nabla g=(-1)
x+2y≥5x+2y\ge5g=5−x−2y≤0g=5-x-2y\le0∇g=(−1,−2)\nabla g=(-1,-2)
3x−y≤73x-y\le7g=3x−y−7≤0g=3x-y-7\le0∇g=(3,−1)\nabla g=(3,-1)
x+y=1x+y=1e=x+y−1=0e=x+y-1=0∇e=(1,1)\nabla e=(1,1)
max⁡xy\max xymin⁡ (−xy)\min\,(-xy)∇f=(−y,−x)\nabla f=(-y,-x)
x>2x>2not allowed—
A ≥\ge becomes a ≤\le by multiplying through by −1-1, which also flips the gradient — that sign is the whole content of the first two rows. The last row is different in kind: with x>2x>2 the feasible set is open, the infimum is 22, and 22 is excluded. For any allowed xx the point (x+2)/2(x+2)/2 is still allowed and strictly better, so no minimiser exists. Every fence in this subject is closed: ≤\le, never <<.
(b) Step 2 — how big is the interrogation? Each fence contributes exactly two branches — its fine is zero, or it is touched — and the branches multiply. An equality contributes none, because it is always active. So with mm fences the count is 2m2^m: m=1: 21=2,m=2: 22=4,m=3: 23=8,m=4: 24=16,m=10: 210=1024.\begin{aligned} m=1:&\ 2^1=2,\\ m=2:&\ 2^2=4,\\ m=3:&\ 2^3=8,\\ m=4:&\ 2^4=16,\\ m=10:&\ 2^{10}=1024. \end{aligned} The tempting guess m2m^2 agrees by coincidence at m=2m=2 (4=44=4) and at m=4m=4 (16=1616=16), and fails at m=3m=3, where the truth is 88 and m2m^2 says 99. Two agreements are not a pattern: 210=10242^{10}=1024 against m2=100m^2=100 settles it.
(c) Step 3 — one path, no fences. Of the five conditions — stationarity, path feasibility, fence feasibility, complementary slackness, and non-negative fines — the last three are about fences, so with no fences they are empty. What survives is exactly two lines: ∇f+λ∇e=0,e=0.\nabla f+\lambda\nabla e=\mathbf 0,\qquad e=0. That is the plain Lagrange recipe: the constrained problem with only equalities never needs a case split, and λ\lambda is free to take either sign.
(d) Step 4 — counting unknowns in the slack formulation. Writing each fence as gi+ti2=0g_i+t_i^2=0 with a slack tit_i, the unknowns are n variables+ 1 path multiplier λ+ m fence multipliers μi+ m slacks ti= n+2m+1.\begin{aligned} &n\ \text{variables}\\ +\ &1\ \text{path multiplier }\lambda\\ +\ &m\ \text{fence multipliers }\mu_i\\ +\ &m\ \text{slacks }t_i\\ =\ &n+2m+1. \end{aligned} For n=2n=2 variables and m=2m=2 fences: 2+4+1=72+4+1=7 unknowns — which is why the branching version, solving four small systems, beats the one big system in practice.

answers at a glance: (a) 2−x≤0 (∇=−1)2-x\le0\ (\nabla=-1); 5−x−2y≤0 (∇=(−1,−2))5-x-2y\le0\ (\nabla=(-1,-2)); 3x−y−7≤0 (∇=(3,−1))3x-y-7\le0\ (\nabla=(3,-1)); x+y−1=0 (∇=(1,1))x+y-1=0\ (\nabla=(1,1)); min⁡(−xy)\min(-xy); x>2x>2 is not allowed — the infimum 22 is excluded, so no minimiser exists. (b) 2, 4, 8, 16, 10242,\ 4,\ 8,\ 16,\ 1024; m2m^2 agrees at m=2m=2 and m=4m=4, fails at m=3m=3 (88, not 99). (c) fence feasibility, complementary slackness and μ≥0\mu\ge0 are empty; ∇f+λ∇e=0\nabla f+\lambda\nabla e=\mathbf 0 and e=0e=0 survive. (d) n+2m+1n+2m+1; for n=2,m=2n=2,m=2 that is 77.

Remember

Standard form first, every time: right-hand side 00, sense ≤\le, maximisation negated. A ≥\ge that is not flipped puts the wrong sign on ∇g\nabla g and then the fine comes out negative and the whole branch is thrown away for the wrong reason. And count branches as 2m2^m in the number of inequalities only — equalities never branch, because they are never slack.

Problem 10medium

Maximise and minimise f(v)=v ⁣⊤Avf(\mathbf v)=\mathbf v^{\!\top}A\mathbf v with A=[5222]A=\begin{bmatrix}5&2\\2&2\end{bmatrix} subject to v ⁣⊤v=1\mathbf v^{\!\top}\mathbf v=1. (a) Write ∇f\nabla f and ∇h\nabla h, impose ∇f=λ∇h\nabla f=\lambda\nabla h, and simplify the resulting system to one familiar matrix equation. (b) Give the characteristic equation and both values of λ\lambda. (c) Give the maximum and minimum of ff and the unit vectors where each is attained, to six decimals. (d) Verify the maximum by direct substitution, showing the arithmetic, and verify that the two optimisers are orthogonal.

What this tests. That the tangency condition on the unit circle is the eigenvalue equation, and that the constrained values of a quadratic form are exactly the eigenvalues. Plan. Differentiate both sides, divide out the 22, read off Av=λvA\mathbf v=\lambda\mathbf v; then trace and determinant give the characteristic polynomial; then f=v ⁣⊤Av=v ⁣⊤(λv)=λf=\mathbf v^{\!\top}A\mathbf v=\mathbf v^{\!\top}(\lambda\mathbf v)=\lambda on a unit eigenvector, so the values need no further work.

Show the full solution
(a) Step 1 — the condition is the eigenvalue equation. With f=5x2+4xy+2y2f=5x^2+4xy+2y^2 and h=x2+y2−1h=x^2+y^2-1, ∇f=(10x+4y, 4x+4y)=2Av,∇h=(2x, 2y)=2v.\begin{aligned} \nabla f&=(10x+4y,\ 4x+4y)=2A\mathbf v,\\ \nabla h&=(2x,\ 2y)=2\mathbf v. \end{aligned} So ∇f=λ∇h\nabla f=\lambda\nabla h reads 2Av=λ 2v2A\mathbf v=\lambda\,2\mathbf v; cancel the 22: Av=λv.A\mathbf v=\lambda\mathbf v. The candidates are not "some points found by calculus" — they are the unit eigenvectors of AA, and the multiplier is the eigenvalue. Moreover, at any such candidate f=v ⁣⊤Av=v ⁣⊤(λv)=λ∥v∥2=λ,f=\mathbf v^{\!\top}A\mathbf v=\mathbf v^{\!\top}(\lambda\mathbf v)=\lambda\|\mathbf v\|^2=\lambda, so the constrained values are the eigenvalues.
(b) Step 2 — the two eigenvalues. tr⁡A=7\operatorname{tr}A=7, det⁡A=10−4=6\det A=10-4=6: λ2−7λ+6=0,(λ−6)(λ−1)=0,λ=6  or  λ=1.\begin{aligned} \lambda^2-7\lambda+6&=0,\\ (\lambda-6)(\lambda-1)&=0,\\ \lambda&=6\ \text{ or }\ \lambda=1. \end{aligned}
(c) Step 3 — the two directions. For λ=6\lambda=6, solve (A−6I)v=0(A-6I)\mathbf v=\mathbf 0: −x+2y=0 ⇒ x=2y,v=(2,1)5=(0.894427, 0.447214).\begin{aligned} -x+2y&=0\ \Rightarrow\ x=2y,\\ \mathbf v&=\frac{(2,1)}{\sqrt5}\\ &=(0.894427,\ 0.447214). \end{aligned} For λ=1\lambda=1, solve (A−I)v=0(A-I)\mathbf v=\mathbf 0: 4x+2y=0 ⇒ y=−2x,v=(−1,2)5=(−0.447214, 0.894427).\begin{aligned} 4x+2y&=0\ \Rightarrow\ y=-2x,\\ \mathbf v&=\frac{(-1,2)}{\sqrt5}\\ &=(-0.447214,\ 0.894427). \end{aligned} Both signs work, since −v-\mathbf v is also a unit eigenvector. So max⁡f=6 at ±(0.894427, 0.447214),min⁡f=1 at ±(−0.447214, 0.894427).\begin{aligned} \max f&=6\ \text{at}\ \pm(0.894427,\,0.447214),\\ \min f&=1\ \text{at}\ \pm(-0.447214,\,0.894427). \end{aligned}
(d) Step 4 — two checks. Substitute (2,1)/5(2,1)/\sqrt5 into f=5x2+4xy+2y2f=5x^2+4xy+2y^2, pulling out the 1/51/5: f=15[5(4)+4(2)(1)+2(1)]=15[20+8+2]=305=6.\begin{aligned} f&=\tfrac15\big[5(4)+4(2)(1)+2(1)\big]\\ &=\tfrac15\big[20+8+2\big]=\tfrac{30}{5}=6. \end{aligned} That is λmax⁡\lambda_{\max}, as promised. ✓ And the two optimisers are perpendicular: (2,1)⋅(−1,2)=−2+2=0.(2,1)\cdot(-1,2)=-2+2=0. A symmetric matrix always hands back orthogonal directions for distinct eigenvalues, which is why the largest and smallest values of a quadratic form sit at right angles to each other — the long and short axes of the same ellipse.

answers at a glance: (a) ∇f=2Av\nabla f=2A\mathbf v, ∇h=2v\nabla h=2\mathbf v, so Av=λvA\mathbf v=\lambda\mathbf v. (b) λ2−7λ+6=0\lambda^2-7\lambda+6=0, λ=6, 1\lambda=6,\ 1. (c) max⁡f=6\max f=6 at ±(0.894427, 0.447214)\pm(0.894427,\,0.447214); min⁡f=1\min f=1 at ±(−0.447214, 0.894427)\pm(-0.447214,\,0.894427). (d) direct check gives 30/5=630/5=6; dot product =0=0.

Remember

"Maximise a quadratic form on the unit sphere" is the eigenvalue problem wearing a different hat — which is exactly how the first principal component is found. Once you recognise Av=λvA\mathbf v=\lambda\mathbf v, stop computing: on a unit eigenvector ff equals λ\lambda, so the answers are already on the page. The slip is forgetting to normalise: (2,1)(2,1) gives f=30f=30, not 66, because ff scales with ∥v∥2\|\mathbf v\|^2.

Problem 11medium

Minimise f(x)=(x−3)2f(x)=(x-3)^2 subject to x≤1x\le1. (a) Put it in standard form and work both branches of the fine-or-no-fine split; say which branch dies and on which condition, give μ∗\mu^*, check all five conditions, and give p∗p^*. (b) Write the Lagrangian and minimise it over xx for a fixed μ\mu, confirming it really is a minimum. (c) Substitute back to get d(μ)d(\mu) in closed form and say what shape it is. (d) Solve max⁡μ≥0d(μ)\max_{\mu\ge0}d(\mu): give μ∗\mu^*, d∗d^* and the gap p∗−d∗p^*-d^*; recover x∗x^* from μ∗\mu^* and verify complementary slackness.

What this tests. The same one-fence problem answered twice — once by the branching interrogation, once by turning the wall into a fine — and the fact that the two answers agree. Plan. Branch on μ=0\mu=0 versus g=0g=0 and kill the loser on a named condition; then build d(μ)=min⁡xLd(\mu)=\min_xL by substituting the inner minimiser, and maximise the resulting parabola over μ≥0\mu\ge0.

Show the full solution
(a) Step 1 — the branching interrogation, two branches. Standard form: g(x)=x−1≤0g(x)=x-1\le0, and stationarity of L=(x−3)2+μ(x−1)L=(x-3)^2+\mu(x-1) is 2(x−3)+μ=0.2(x-3)+\mu=0. Branch 1, μ=0\mu=0 (the fence does nothing). Then 2(x−3)=02(x-3)=0, so x=3x=3. Check the fence: g(3)=3−1=2>0g(3)=3-1=2>0. The point is outside. Rejected on fence feasibility.
Branch 2, g=0g=0 (pressed against the fence). Then x=1x=1, and stationarity gives 2(1−3)+μ=0,−4+μ=0,μ∗=4  (≥0 ✓).\begin{aligned} 2(1-3)+\mu&=0,\\ -4+\mu&=0,\\ \mu^*&=4\ \ (\ge0\ \checkmark). \end{aligned} All five conditions at (x,μ)=(1,4)(x,\mu)=(1,4): stationarity −4+4=0-4+4=0 ✓; no path to check; fence feasibility g=0≤0g=0\le0 ✓; complementary slackness μg=4(0)=0\mu g=4(0)=0 ✓; μ=4≥0\mu=4\ge0 ✓. So p∗=(1−3)2=4.p^*=(1-3)^2=4.
(b) Step 2 — turn the wall into a fine. L(x,μ)=(x−3)2+μ(x−1).L(x,\mu)=(x-3)^2+\mu(x-1). For a fixed μ\mu this is a parabola in xx opening upward, so its minimum is where the derivative vanishes: ∂L∂x=2(x−3)+μ=0,x=3−μ2,∂2L∂x2=2>0 ⇒ a minimum.\begin{aligned} \frac{\partial L}{\partial x}&=2(x-3)+\mu=0,\\ x&=3-\frac\mu2,\\ \frac{\partial^2L}{\partial x^2}&=2>0\ \Rightarrow\ \text{a minimum.} \end{aligned} Read that inner answer: at zero fine the walker goes straight to 33 and ignores the wall; each unit of fine drags it back by 12\tfrac12.
(c) Step 3 — the dual function. Substitute x=3−μ/2x=3-\mu/2 back into LL. The first bracket becomes −μ/2-\mu/2 and the second becomes 2−μ/22-\mu/2: d(μ)=(−μ2)2+μ(2−μ2)=μ24+2μ−μ22=2μ−μ24.\begin{aligned} d(\mu)&=\Big(-\frac\mu2\Big)^2+\mu\Big(2-\frac\mu2\Big)\\ &=\frac{\mu^2}{4}+2\mu-\frac{\mu^2}{2}\\ &=2\mu-\frac{\mu^2}{4}. \end{aligned} The μ2\mu^2 coefficient is 14−12=−14<0\tfrac14-\tfrac12=-\tfrac14<0, so dd is an upside-down parabola — concave, with a single peak. Every value it takes is a guaranteed floor under p∗p^*: d(0)=0d(0)=0, d(2)=4−1=3d(2)=4-1=3, d(6)=12−9=3d(6)=12-9=3, all at or below 44.
(d) Step 4 — climb the hill and compare. d′(μ)=2−μ2=0,μ∗=4  (≥0 ✓),d∗=2(4)−164=8−4=4.\begin{aligned} d'(\mu)&=2-\frac\mu2=0,\\ \mu^*&=4\ \ (\ge0\ \checkmark),\\ d^*&=2(4)-\frac{16}{4}=8-4=4. \end{aligned} The gap: p∗−d∗=4−4=0,p^*-d^*=4-4=0, zero — strong duality. Recover the primal point from the inner minimiser at μ∗\mu^*: x∗=3−42=1 ✓x^*=3-\frac42=1\ \checkmark which is the same x∗x^* branch 2 produced, and complementary slackness holds there: μ∗g(x∗)=4(1−1)=4(0)=0. ✓\mu^*g(x^*)=4(1-1)=4(0)=0.\ \checkmark Two completely different routes — case analysis on the primal, hill-climbing on the dual — and they meet at the same μ=4\mu=4, the same x=1x=1, the same value 44.

answers at a glance: (a) branch μ=0\mu=0 gives x=3x=3 and dies on fence feasibility (g=2>0g=2>0); branch g=0g=0 gives x∗=1x^*=1, μ∗=4\mu^*=4, all five conditions hold, p∗=4p^*=4. (b) x=3−μ/2x=3-\mu/2, with ∂2L/∂x2=2>0\partial^2L/\partial x^2=2>0. (c) d(μ)=2μ−μ2/4d(\mu)=2\mu-\mu^2/4, a concave (downward) parabola. (d) μ∗=4\mu^*=4, d∗=4d^*=4, gap =0=0; recovered x∗=1x^*=1 and μ∗g(x∗)=0\mu^*g(x^*)=0.

Remember

Rejecting a branch is progress, not failure — but you must name which condition killed it: μ=0\mu=0 here died on feasibility, and a branch that returns μ<0\mu<0 dies on the sign condition instead. The other thing to keep: the dual is built by substituting the inner minimiser back in, so it is a function of μ\mu alone — if an xx is still visible in your d(μ)d(\mu), the substitution was not finished.

Problem 12medium

Minimise f(x,y)=x2+2y2f(x,y)=x^2+2y^2 subject to x+y=1x+y=1, x≥0x\ge0 and y≥0y\ge0. (a) Put it in standard form, say how many cases the interrogation has, and write the Lagrangian. (b) Write the two stationarity equations as expressions for μ1\mu_1 and μ2\mu_2, and use the path to eliminate yy from the second. (c) Work all four cases: for each, give the point, the multipliers, and either the value of ff or the exact condition that rejects it. (d) Give λ∗\lambda^* and say why its sign is legal; give μ1∗,μ2∗\mu_1^*,\mu_2^* and verify directly what they claim about the two fences; and state why the surviving point is the global minimum.

What this tests. A complete four-case interrogation with one path and two fences, and the discipline of rejecting each losing case on a named condition rather than by eye. Plan. Standard form and the Lagrangian; differentiate once in xx and once in yy to get the two fines as formulas; then walk the four patterns in order, each time solving the small linear system the pattern leaves behind and checking what the pattern did not enforce.

Show the full solution
(a) Step 1 — standard form. The path is e=x+y−1=0e=x+y-1=0; the two fences are g1=−x≤0,g2=−y≤0.g_1=-x\le0,\qquad g_2=-y\le0. Two fences means 22=42^2=4 cases. The Lagrangian, with λ\lambda free and μ1,μ2≥0\mu_1,\mu_2\ge0: L=x2+2y2+λ(x+y−1)−μ1x−μ2y.\begin{aligned} L&=x^2+2y^2+\lambda(x+y-1)\\ &\quad-\mu_1x-\mu_2y. \end{aligned}
(b) Step 2 — stationarity, rearranged. ∂L∂x=2x+λ−μ1=0⇒ μ1=2x+λ,∂L∂y=4y+λ−μ2=0⇒ μ2=4y+λ.\begin{aligned} \frac{\partial L}{\partial x}&=2x+\lambda-\mu_1=0\\ &\Rightarrow\ \mu_1=2x+\lambda,\\ \frac{\partial L}{\partial y}&=4y+\lambda-\mu_2=0\\ &\Rightarrow\ \mu_2=4y+\lambda. \end{aligned} The path gives y=1−xy=1-x, so the second becomes μ2=4(1−x)+λ=4−4x+λ.\mu_2=4(1-x)+\lambda=4-4x+\lambda. Everything is now in xx and λ\lambda, which is what makes each case a two-line solve.
(c) Step 3 — case 1: both fences slack (μ1=0, μ2=0\mu_1=0,\ \mu_2=0). 0=2x+λ ⇒ λ=−2x,0=4−4x+λ ⇒ λ=4x−4.\begin{aligned} 0&=2x+\lambda\ \Rightarrow\ \lambda=-2x,\\ 0&=4-4x+\lambda\ \Rightarrow\ \lambda=4x-4. \end{aligned} Equate: −2x=4x−4,6x=4,x=23,y=1−23=13,λ=−2(23)=−43.\begin{aligned} -2x&=4x-4,\\ 6x&=4,\qquad x=\tfrac23,\\ y&=1-\tfrac23=\tfrac13,\\ \lambda&=-2\big(\tfrac23\big)=-\tfrac43. \end{aligned} Everything checks: x>0x>0 and y>0y>0 so both fences are respected, both fines are 00 so complementary slackness holds, and μi=0≥0\mu_i=0\ge0. The value: f=(23)2+2(13)2=49+29=23.f=\Big(\tfrac23\Big)^2+2\Big(\tfrac13\Big)^2=\tfrac49+\tfrac29=\tfrac23. Survives.
Step 4 — the three losers. Case 2: μ1=0\mu_1=0, y=0y=0. Then the path forces x=1x=1, and λ=−2x=−2,μ2=4(0)+λ=−2<0.\begin{aligned} \lambda&=-2x=-2,\\ \mu_2&=4(0)+\lambda=-2<0. \end{aligned} Rejected — a negative fine breaks the sign condition. (A fence is allowed to push, never to pull.)
Case 3: x=0x=0, μ2=0\mu_2=0. Then y=1y=1, and 0=4(1)+λ ⇒ λ=−4,μ1=2(0)+λ=−4<0.\begin{aligned} 0&=4(1)+\lambda\ \Rightarrow\ \lambda=-4,\\ \mu_1&=2(0)+\lambda=-4<0. \end{aligned} Rejected on the same sign condition.
Case 4: both fences touched, x=0x=0 and y=0y=0. Then x+y=0≠1,x+y=0\ne1, so the point is not on the path at all. Rejected on path feasibility — and note this happens before any multiplier is computed.
casepointmultipliersverdict
1 (μ1=μ2=0)(\mu_1=\mu_2=0)(23,13)(\tfrac23,\tfrac13)λ=−43\lambda=-\tfrac43survives, f=23f=\tfrac23
2 (μ1=0, y=0)(\mu_1=0,\ y=0)(1,0)(1,0)λ=−2, μ2=−2\lambda=-2,\ \mu_2=-2rejected: μ2<0\mu_2<0
3 (x=0, μ2=0)(x=0,\ \mu_2=0)(0,1)(0,1)λ=−4, μ1=−4\lambda=-4,\ \mu_1=-4rejected: μ1<0\mu_1<0
4 (x=0, y=0)(x=0,\ y=0)(0,0)(0,0)—rejected: off the path
(d) Step 4 — read the answer. Two computable readings of the surviving multipliers. λ∗=−43<0,\lambda^*=-\tfrac43<0, and that is perfectly legal: only fence multipliers carry a sign restriction. A path may be pushed from either side, so λ\lambda is free. μ1∗=μ2∗=0,\mu_1^*=\mu_2^*=0, which claims both fences are slack. Verify it directly rather than trusting the claim: g1=−x∗=−23<0 ✓g2=−y∗=−13<0 ✓\begin{aligned} g_1&=-x^*=-\tfrac23<0\ \checkmark\\ g_2&=-y^*=-\tfrac13<0\ \checkmark \end{aligned} Both hold with room to spare, so the fences are doing no work — remove them and the answer would not move. Finally, the objective x2+2y2x^2+2y^2 is a bowl and both rules are linear, so the problem is convex: the single surviving point is the global minimum, not just a candidate.

answers at a glance: (a) e=x+y−1e=x+y-1, g1=−xg_1=-x, g2=−yg_2=-y; 44 cases; L=x2+2y2+λ(x+y−1)−μ1x−μ2yL=x^2+2y^2+\lambda(x+y-1)-\mu_1x-\mu_2y. (b) μ1=2x+λ\mu_1=2x+\lambda, μ2=4y+λ=4−4x+λ\mu_2=4y+\lambda=4-4x+\lambda. (c) case 1 survives at (23,13)(\tfrac23,\tfrac13), λ=−43\lambda=-\tfrac43, f=23f=\tfrac23; case 2 μ2=−2\mu_2=-2, case 3 μ1=−4\mu_1=-4, case 4 x+y=0≠1x+y=0\ne1. (d) λ∗=−43\lambda^*=-\tfrac43 is legal because paths are unsigned; μ1∗=μ2∗=0\mu_1^*=\mu_2^*=0 with g1=−23<0g_1=-\tfrac23<0 and g2=−13<0g_2=-\tfrac13<0; convex, so it is the global minimum.

Remember

Every case must die of a named cause: infeasible point, or a negative fine. Those are the only two ways out. The classic slip is demanding λ≥0\lambda\ge0 — the sign condition belongs to fences alone, and a perfectly good answer gets thrown away when a negative λ\lambda is treated as an error. The second slip is forgetting to check the conditions the case pattern did not assume: assuming μ1=0\mu_1=0 does not make x≥0x\ge0 true, it must still be verified.

Problem 13hard

Minimise f(x,y)=x2+y2f(x,y)=x^2+y^2 subject to x+y=4x+y=4 and x≥3x\ge3. (a) Put it in standard form, write the Lagrangian and give the two stationarity equations. (b) Work both cases; give x∗,y∗,λ∗,μ∗x^*,y^*,\lambda^*,\mu^* and p∗p^*, and say what kills the losing case. (c) Minimise LL over (x,y)(x,y) for fixed multipliers and substitute back to get d(λ,μ)d(\lambda,\mu), showing where each of the three quadratic coefficients comes from. (d) Give the dual Hessian, its determinant and trace, and both eigenvalues, and conclude the shape of dd. (e) Solve the dual: give λ∗,μ∗,d∗\lambda^*,\mu^*,d^*, the gap, and the recovered (x∗,y∗)(x^*,y^*). (f) The wall moves to x≥2.9x\ge2.9: give the predicted new p∗p^*, the actual one, the exact value function p∗(c)p^*(c) for c≥2c\ge2, its slope, and the slope's values at c=3c=3 and c=2c=2.

What this tests. The full round trip — primal case analysis, dual construction, dual optimisation, recovery — and then the multiplier read as the price of a wall, including the point where the wall stops being worth anything. Plan. Two cases on the primal; then minimise LL in xx and yy separately, substitute, and collect μ2,λ2,λμ\mu^2,\lambda^2,\lambda\mu coefficient by coefficient; then two linear equations for the dual optimum; finally differentiate the exact value function.

Show the full solution
(a) Step 1 — standard form. Path e=x+y−4=0e=x+y-4=0; fence g=3−x≤0g=3-x\le0. L=x2+y2+λ(x+y−4)+μ(3−x).L=x^2+y^2+\lambda(x+y-4)+\mu(3-x). ∂L∂x=2x+λ−μ=0,∂L∂y=2y+λ=0.\begin{aligned} \frac{\partial L}{\partial x}&=2x+\lambda-\mu=0,\\ \frac{\partial L}{\partial y}&=2y+\lambda=0. \end{aligned}
(b) Step 2 — two cases. Case μ=0\mu=0. Then 2x+λ=02x+\lambda=0 and 2y+λ=02y+\lambda=0 give x=yx=y, and the path gives x=y=2x=y=2. Check the wall: g(2)=3−2=1>0,g(2)=3-2=1>0, outside. Rejected on fence feasibility.
Case g=0g=0. Then x=3x=3, and the path gives y=1y=1: 2(1)+λ=0 ⇒ λ=−2,2(3)+(−2)−μ=0 ⇒ μ=4  (≥0 ✓).\begin{aligned} 2(1)+\lambda&=0\ \Rightarrow\ \lambda=-2,\\ 2(3)+(-2)-\mu&=0\ \Rightarrow\ \mu=4\ \ (\ge0\ \checkmark). \end{aligned} All five hold — stationarity ✓, path 3+1−4=03+1-4=0 ✓, fence g=0≤0g=0\le0 ✓, μg=4(0)=0\mu g=4(0)=0 ✓, μ≥0\mu\ge0 ✓ — so p∗=32+12=10.p^*=3^2+1^2=10.
(c) Step 3 — build the dual. For fixed (λ,μ)(\lambda,\mu), LL is a sum of two upward parabolas, so its minimiser is 2x+λ−μ=0 ⇒ x=μ−λ2,2y+λ=0 ⇒ y=−λ2.\begin{aligned} 2x+\lambda-\mu=0&\ \Rightarrow\ x=\frac{\mu-\lambda}{2},\\ 2y+\lambda=0&\ \Rightarrow\ y=-\frac\lambda2. \end{aligned} Substitute, one term per line: x2=μ24−λμ2+λ24,y2=λ24,λ(x+y−4)=λμ2−λ2−4λ,μ(3−x)=3μ−μ22+λμ2.\begin{aligned} x^2&=\frac{\mu^2}{4}-\frac{\lambda\mu}{2}+\frac{\lambda^2}{4},\\ y^2&=\frac{\lambda^2}{4},\\ \lambda(x{+}y{-}4)&=\frac{\lambda\mu}{2}-\lambda^2-4\lambda,\\ \mu(3-x)&=3\mu-\frac{\mu^2}{2}+\frac{\lambda\mu}{2}. \end{aligned} (For the third line, x+y=μ−λ2−λ2=μ2−λx+y=\frac{\mu-\lambda}{2}-\frac\lambda2=\frac\mu2-\lambda.) Now collect the three quadratic coefficients: μ2: 14−12=−14,λ2: 14+14−1=−12,λμ: −12+12+12=+12,\begin{aligned} \mu^2:&\ \tfrac14-\tfrac12=-\tfrac14,\\ \lambda^2:&\ \tfrac14+\tfrac14-1=-\tfrac12,\\ \lambda\mu:&\ -\tfrac12+\tfrac12+\tfrac12=+\tfrac12, \end{aligned} and the linear part is −4λ+3μ-4\lambda+3\mu, so d(λ,μ)=−μ24−λ22+λμ2−4λ+3μ.d(\lambda,\mu)=-\frac{\mu^2}{4}-\frac{\lambda^2}{2}+\frac{\lambda\mu}{2}-4\lambda+3\mu.
(d) Step 4 — the dual is a hill. Second derivatives: Hd=[−11212−12],H_d=\begin{bmatrix}-1&\tfrac12\\ \tfrac12&-\tfrac12\end{bmatrix}, det⁡Hd=12−14=14>0,tr⁡Hd=−1−12=−32<0.\begin{aligned} \det H_d&=\tfrac12-\tfrac14=\tfrac14>0,\\ \operatorname{tr}H_d&=-1-\tfrac12=-\tfrac32<0. \end{aligned} A positive determinant makes the eigenvalues share a sign; a negative trace makes that sign negative. Explicitly, from λ2+32λ+14=0\lambda^2+\tfrac32\lambda+\tfrac14=0: λ1,2=−3±54=−0.190983, −1.309017.\begin{aligned} \lambda_{1,2}&=\frac{-3\pm\sqrt5}{4}\\ &=-0.190983,\ -1.309017. \end{aligned} (Check: their sum is −32-\tfrac32 and their product is 9−516=14\tfrac{9-5}{16}=\tfrac14 ✓.) Both negative, so dd is concave: one peak, no ridges, no local traps — which is why the dual is always the easy side to optimise.
(e) Step 5 — climb to the top. ∂d∂λ=−λ+μ2−4=0⇒ λ=μ2−4,∂d∂μ=−μ2+λ2+3=0⇒ μ=λ+6.\begin{aligned} \frac{\partial d}{\partial\lambda}&=-\lambda+\frac\mu2-4=0\\ &\Rightarrow\ \lambda=\frac\mu2-4,\\ \frac{\partial d}{\partial\mu}&=-\frac\mu2+\frac\lambda2+3=0\\ &\Rightarrow\ \mu=\lambda+6. \end{aligned} Substitute the second into the first: λ=λ+62−4=λ2−1,λ2=−1,λ∗=−2,μ∗=−2+6=4  (≥0 ✓).\begin{aligned} \lambda&=\frac{\lambda+6}{2}-4=\frac\lambda2-1,\\ \frac\lambda2&=-1,\qquad \lambda^*=-2,\\ \mu^*&=-2+6=4\ \ (\ge0\ \checkmark). \end{aligned} d∗=−164−42+(−2)(4)2−4(−2)+3(4)=−4−2−4+8+12=10.\begin{aligned} d^*&=-\tfrac{16}{4}-\tfrac{4}{2}+\tfrac{(-2)(4)}{2}\\ &\quad-4(-2)+3(4)\\ &=-4-2-4+8+12=10. \end{aligned} So d∗=10=p∗d^*=10=p^*: the gap is 00. Recover the primal point from the inner minimiser: x∗=4−(−2)2=3,y∗=−−22=1. ✓\begin{aligned} x^*&=\frac{4-(-2)}{2}=3,\\ y^*&=-\frac{-2}{2}=1.\ \checkmark \end{aligned}
(f) Step 6 — what the wall is worth. Move it to x≥2.9x\ge2.9, a relaxation of 0.10.1. The multiplier is the price per unit of wall, so predicted p∗≈10−μ∗(0.1)=10−0.4=9.60.\begin{aligned} \text{predicted }p^*&\approx10-\mu^*(0.1)\\ &=10-0.4=9.60. \end{aligned} The truth: the wall is still binding, so x=2.9x=2.9, y=1.1y=1.1, and p∗=(2.9)2+(1.1)2=8.41+1.21=9.62.\begin{aligned} p^*&=(2.9)^2+(1.1)^2\\ &=8.41+1.21=9.62. \end{aligned} Prediction 9.609.60, fact 9.629.62 — off by 0.020.02, the curvature again. Exactly, with the wall at x≥cx\ge c: p∗(c)=c2+(4−c)2,c≥2,dp∗dc=2c−2(4−c)=4c−8.\begin{aligned} p^*(c)&=c^2+(4-c)^2,\qquad c\ge2,\\ \frac{\mathrm dp^*}{\mathrm dc}&=2c-2(4-c)=4c-8. \end{aligned} At c=3c=3 the slope is 44, which is μ∗\mu^*. ✓ At c=2c=2 the slope is 00: there the wall has slid back to the unconstrained answer (2,2)(2,2), the fence stops biting, and its price falls to nothing. For c<2c<2 the wall is slack, p∗p^* stays flat at 88, and μ∗=0\mu^*=0.

answers at a glance: (a) e=x+y−4e=x+y-4, g=3−xg=3-x; 2x+λ−μ=02x+\lambda-\mu=0, 2y+λ=02y+\lambda=0. (b) μ=0\mu=0 gives (2,2)(2,2) with g=1>0g=1>0, rejected; g=0g=0 gives x∗=3, y∗=1, λ∗=−2, μ∗=4x^*=3,\ y^*=1,\ \lambda^*=-2,\ \mu^*=4, p∗=10p^*=10. (c) d=−μ24−λ22+λμ2−4λ+3μd=-\frac{\mu^2}{4}-\frac{\lambda^2}{2}+\frac{\lambda\mu}{2}-4\lambda+3\mu. (d) Hd=[−11212−12]H_d=\begin{bmatrix}-1&\frac12\\ \frac12&-\frac12\end{bmatrix}, det⁡=14\det=\frac14, tr⁡=−32\operatorname{tr}=-\frac32, eigenvalues −0.190983, −1.309017-0.190983,\ -1.309017: concave. (e) λ∗=−2\lambda^*=-2, μ∗=4\mu^*=4, d∗=10d^*=10, gap 00, recovered (3,1)(3,1). (f) predicted 9.609.60, actual 9.629.62; p∗(c)=c2+(4−c)2p^*(c)=c^2+(4-c)^2, slope 4c−84c-8, equal to 44 at c=3c=3 and 00 at c=2c=2.

Remember

At the optimum the multiplier is the slope of the value function, so μ∗\mu^* tells you what the wall is costing you before you re-solve. Follow that slope far enough and it hits zero, at the moment the wall stops touching the answer — after which relaxing it further buys nothing. The slip is quoting the dual optimum without checking μ≥0\mu\ge0: the dual problem is max⁡\max over μ≥0\mu\ge0, and an unconstrained stationary point with μ<0\mu<0 is not the dual answer.

Problem 14hard

A one-dimensional dataset has two points: x1=+1x_1=+1 with y1=+1y_1=+1, and x2=−1x_2=-1 with y2=−1y_2=-1. The largest-margin classifier solves min⁡w,b12w2\min_{w,b}\tfrac12w^2 subject to yi(wxi+b)≥1y_i(wx_i+b)\ge1. (a) Write both constraints in standard form and give the Lagrangian with α1,α2≥0\alpha_1,\alpha_2\ge0. (b) Give the two stationarity equations and reduce the Lagrangian to a function q(α)q(\alpha) of a single variable. (c) Maximise qq: give α∗\alpha^*, d∗d^*, w∗w^*, b∗b^*, the primal value, the gap, the decision boundary, the margin edges, the margin width, and the number of support vectors. (d) A third point x3=3x_3=3 with y3=+1y_3=+1 is added: give α3\alpha_3 and say what happens to the classifier. Then, with a point at x3<1x_3<1 of class +1+1 and the point at −1-1 both binding, derive ww and bb as formulas in x3x_3, and evaluate them, the boundary and the margin at x3=0.5x_3=0.5.

What this tests. Every move of the unit chained together — framing, standard form, Lagrangian, dual, solve, recover, read the slackness — on the problem the whole subject is built toward. Plan. Write the two constraints out; differentiate in ww and in bb (the bb-equation is what collapses two multipliers into one); substitute to get a one-variable concave parabola; solve it; then use αi>0⇒\alpha_i>0\Rightarrow constraint tight to pin bb.

Show the full solution
(a) Step 1 — the two constraints, written out. For i=1i=1: y1(wx1+b)=(+1)(w+b)≥1y_1(wx_1+b)=(+1)(w+b)\ge1. For i=2i=2: y2(wx2+b)=(−1)(−w+b)=w−b≥1y_2(wx_2+b)=(-1)(-w+b)=w-b\ge1. In standard form, g1=1−w−b≤0,g2=1−w+b≤0,\begin{aligned} g_1&=1-w-b\le0,\\ g_2&=1-w+b\le0, \end{aligned} L=12w2+α1(1−w−b)+α2(1−w+b),αi≥0.\begin{aligned} L&=\tfrac12w^2+\alpha_1(1-w-b)\\ &\quad+\alpha_2(1-w+b),\qquad \alpha_i\ge0. \end{aligned}
(b) Step 2 — stationarity, and the collapse to one variable. ∂L∂w=w−α1−α2=0⇒ w=α1+α2,∂L∂b=−α1+α2=0⇒ α1=α2.\begin{aligned} \frac{\partial L}{\partial w}&=w-\alpha_1-\alpha_2=0\\ &\Rightarrow\ w=\alpha_1+\alpha_2,\\ \frac{\partial L}{\partial b}&=-\alpha_1+\alpha_2=0\\ &\Rightarrow\ \alpha_1=\alpha_2. \end{aligned} (These are the two standard identities w=∑iαiyixiw=\sum_i\alpha_iy_ix_i and ∑iαiyi=0\sum_i\alpha_iy_i=0, written out for this data.) Regroup LL: L=12w2−w(α1+α2)−b(α1−α2)+(α1+α2).\begin{aligned} L&=\tfrac12w^2-w(\alpha_1+\alpha_2)\\ &\quad-b(\alpha_1-\alpha_2)+(\alpha_1+\alpha_2). \end{aligned} Write α1=α2=α\alpha_1=\alpha_2=\alpha, so the bb-term vanishes and w=2αw=2\alpha: q(α)=12(2α)2−(2α)(2α)+2α=2α2−4α2+2α=2α−2α2.\begin{aligned} q(\alpha)&=\tfrac12(2\alpha)^2-(2\alpha)(2\alpha)+2\alpha\\ &=2\alpha^2-4\alpha^2+2\alpha\\ &=2\alpha-2\alpha^2. \end{aligned} (Cross-check against ∑iαi−12∑i,jαiαjyiyjxixj\sum_i\alpha_i-\tfrac12\sum_{i,j}\alpha_i\alpha_jy_iy_jx_ix_j: here every product yiyjxixj=1y_iy_jx_ix_j=1, so it reads 2α−12(2α)2=2α−2α22\alpha-\tfrac12(2\alpha)^2=2\alpha-2\alpha^2 — the same function.)
(c) Step 3 — solve, recover, read. q′(α)=2−4α=0,α∗=12  (≥0 ✓),d∗=q(12)=1−12=12.\begin{aligned} q'(\alpha)&=2-4\alpha=0,\\ \alpha^*&=\tfrac12\ \ (\ge0\ \checkmark),\\ d^*&=q\big(\tfrac12\big)=1-\tfrac12=\tfrac12. \end{aligned} Recover the classifier: w∗=α1∗+α2∗=12+12=1.w^*=\alpha_1^*+\alpha_2^*=\tfrac12+\tfrac12=1. Because α1∗=12>0\alpha_1^*=\tfrac12>0, complementary slackness forces its constraint tight: w+b=1,b∗=1−1=0.\begin{aligned} w+b&=1,\\ b^*&=1-1=0. \end{aligned} Consistency: the second constraint gives w−b=1−0=1w-b=1-0=1, also tight, matching α2∗>0\alpha_2^*>0. The primal value is 12(1)2=12=d∗\tfrac12(1)^2=\tfrac12=d^*, so the gap is 00. Geometry: boundary: w∗x+b∗=0 ⇒ x=0,margin edges: w∗x+b∗=±1 ⇒ x=±1,width: 2∣w∗∣=2.\begin{aligned} \text{boundary: }&w^*x+b^*=0\ \Rightarrow\ x=0,\\ \text{margin edges: }&w^*x+b^*=\pm1\ \Rightarrow\ x=\pm1,\\ \text{width: }&\frac{2}{|w^*|}=2. \end{aligned} Both αi>0\alpha_i>0, so both points are support vectors: 2\mathbf 2 of them, out of 22.
(d) Step 4 — a point that does not matter. Adding x3=3x_3=3 with y3=+1y_3=+1 adds the constraint 3w+b≥13w+b\ge1. At the current answer (w,b)=(1,0)(w,b)=(1,0) it reads 3(1)+0=3 ≥1,3(1)+0=3\ \ge1, slack by 22. In standard form g3=1−3w−b=−2<0g_3=1-3w-b=-2<0, and complementary slackness α3g3=0\alpha_3g_3=0 with g3≠0g_3\ne0 forces α3=0.\alpha_3=0. Since w=∑iαiyixiw=\sum_i\alpha_iy_ix_i, a point with αi=0\alpha_i=0 contributes nothing: the classifier does not move, and the point can be deleted from the training set without changing a thing.
Step 5 — now move that point inside. Suppose instead the +1+1 point sits at x3<1x_3<1, close enough that its constraint becomes tight, with the −1-1 point at −1-1 also tight: wx3+b=1,w−b=1 ⇒ b=w−1.\begin{aligned} wx_3+b&=1,\\ w-b&=1\ \Rightarrow\ b=w-1. \end{aligned} Substitute: wx3+w−1=1,w(x3+1)=2,w=2x3+1,\begin{aligned} wx_3+w-1&=1,\\ w(x_3+1)&=2,\\ w&=\frac{2}{x_3+1}, \end{aligned} b=1−wx3=x3+1−2x3x3+1=1−x31+x3.\begin{aligned} b&=1-wx_3=\frac{x_3+1-2x_3}{x_3+1}\\ &=\frac{1-x_3}{1+x_3}. \end{aligned} At x3=0.5x_3=0.5: w=21.5=1.3333,b=0.51.5=0.3333,boundary x=−bw=−0.33331.3333=−0.25,margin =2∣w∣=1.5.\begin{aligned} w&=\frac{2}{1.5}=1.3333,\\ b&=\frac{0.5}{1.5}=0.3333,\\ \text{boundary }x&=-\frac bw=-\frac{0.3333}{1.3333}=-0.25,\\ \text{margin }&=\frac{2}{|w|}=1.5. \end{aligned} Dragging the positive point from 33 (where it was ignored entirely) in to 0.50.5 squeezes the margin from 22 to 1.51.5 and shifts the boundary from 00 to −0.25-0.25. Nothing about the point changed except whether its constraint was tight — and that is the whole difference between a data point that matters and one that does not.

answers at a glance: (a) g1=1−w−b≤0g_1=1-w-b\le0, g2=1−w+b≤0g_2=1-w+b\le0; L=12w2+α1g1+α2g2L=\tfrac12w^2+\alpha_1g_1+\alpha_2g_2. (b) w=α1+α2w=\alpha_1+\alpha_2, α1=α2\alpha_1=\alpha_2; q(α)=2α−2α2q(\alpha)=2\alpha-2\alpha^2. (c) α∗=12\alpha^*=\tfrac12, d∗=12d^*=\tfrac12, w∗=1w^*=1, b∗=0b^*=0, primal 12\tfrac12, gap 00; boundary x=0x=0, edges x=±1x=\pm1, width 22, 22 support vectors. (d) α3=0\alpha_3=0 and the classifier does not move; w=2/(x3+1)w=2/(x_3+1), b=(1−x3)/(1+x3)b=(1-x_3)/(1+x_3); at x3=0.5x_3=0.5, w=1.3333w=1.3333, b=0.3333b=0.3333, boundary −0.25-0.25, margin 1.51.5.

Remember

Complementary slackness is why these classifiers are sparse: αi=0\alpha_i=0 means the point sits strictly outside the margin and can be thrown away, while αi>0\alpha_i>0 means its constraint is tight and it is holding the boundary up. The multiplier is the answer to "which data matter". The slip is solving for bb from stationarity — ∂L/∂b\partial L/\partial b only gives ∑iαiyi=0\sum_i\alpha_iy_i=0 and never mentions bb; bb comes from setting a support vector's constraint to equality.

Next up

Unit 12 · Principal Component Analysis I — coming soon

You have just maximised a quadratic form on the unit circle and watched the multiplier come out as an eigenvalue. That was not a coincidence — it is the whole of principal component analysis in miniature. Unit 12 asks what a cloud of data looks like from its own best angle, why the directions of greatest spread are the eigenvectors of a covariance matrix, and how much you can throw away before the picture stops being the picture.

← All units