First-order optimality conditions — gradient = 0

---

WHAT is the condition?

---

WHY is it true? (derivation from scratch)

We derive it; we never just quote it.

Step 1 — write the difference quotient. $\frac{f(x^*+h)-f(x^*)}{h}.$ Why this step? The derivative is the limit of this quotient; we squeeze it from both sides.

Step 2 — approach from the right ($h\to 0^+$). Numerator $\ge 0$, denominator $>0$, so quotient $\ge 0$, hence $f'(x^*)=\lim_{h\to0^+}(\cdots)\ge 0.$ Why? A limit of non-negative numbers is non-negative.

Step 3 — approach from the left ($h\to 0^-$). Numerator $\ge 0$, denominator $<0$, so quotient $\le 0$, hence $f'(x^*)\le 0.$

Step 4 — combine. $f'(x^*)\ge0$ and $f'(x^*)\le0$ force $\boxed{f'(x^*)=0.}$ Why this works: differentiability means the left and right limits must agree, and we trapped that common value between $\le0$ and $\ge0$.

Step — repeat for every $i$. Every partial derivative vanishes:

\quad\Longleftrightarrow\quad \nabla f(x^*)=\mathbf 0.$$ > [!formula] Directional-derivative version (the deepest reason) > The directional derivative in unit direction $u$ is $D_u f(x^*)=\nabla f(x^*)\cdot u$. > If $\nabla f(x^*)\ne 0$, choose $u=-\nabla f/\lVert\nabla f\rVert$. Then > $$D_u f = -\lVert \nabla f(x^*)\rVert < 0,$$ > meaning $f$ **decreases** along $u$ — so $x^*$ wasn't a minimum. Contradiction. Hence $\nabla f(x^*)=\mathbf{0}$. ![[4.10.18-First-order-optimality-conditions-—-gradient-=-0.png]] --- ## Worked examples > [!example] 1-D: classify $f(x)=x^3-3x$ > **Step 1** $f'(x)=3x^2-3$. *Why?* FONC needs the derivative. > **Step 2** Set $f'=0\Rightarrow x^2=1\Rightarrow x=\pm1$. *Why?* Stationary points are the candidates. > **Step 3** $f''(x)=6x$: $f''(1)=6>0$ (min), $f''(-1)=-6<0$ (max). *Why?* FONC can't tell max from min; the second-order test does. > [!example] 2-D: minimise $f(x,y)=x^2+xy+y^2-3y$ > **Step 1** Compute the gradient: > $$\nabla f=\begin{pmatrix}2x+y\\ x+2y-3\end{pmatrix}.$$ > *Why?* Each component is a partial derivative. > **Step 2** Set $=\mathbf0$: $2x+y=0,\;x+2y=3$. > **Step 3** Solve: from the first $y=-2x$; substitute: $x+2(-2x)=3\Rightarrow -3x=3\Rightarrow x=-1,\;y=2$. > *Why?* This is the only stationary point. > **Step 4** Hessian $H=\begin{pmatrix}2&1\\1&2\end{pmatrix}$ has eigenvalues $1,3>0$ ⟹ positive definite ⟹ **strict local (here global) minimum** at $(-1,2)$, value $-3$. > [!example] Saddle warning: $f(x,y)=x^2-y^2$ > **Step 1** $\nabla f=(2x,-2y)=\mathbf0\Rightarrow (0,0)$. > **Step 2** Along $x$-axis $f=x^2$ (rises); along $y$-axis $f=-y^2$ (falls). *Why this matters:* gradient is zero yet it's **neither** max nor min — a saddle. Proof that FONC alone is not enough. > [!mistake] Steel-man: "I forgot the boundary" > **Why it feels right:** all calculus problems we practise are "unconstrained", so we hunt only where $\nabla f=0$. > **Why it's wrong:** the derivation assumed $x^*$ is **interior** (we could step in *both* directions). On a closed domain, the min can sit on the boundary where the gradient need *not* vanish (it may point *outward*). > **Fix:** also check boundary points / use Lagrange/KKT conditions for constraints. --- ## #flashcards/maths State the first-order necessary condition for an interior local optimum. ::: $\nabla f(x^*)=\mathbf{0}$ (every partial derivative is zero). Is $\nabla f=0$ sufficient for a minimum? ::: No — it is only necessary; the point may be a max or a saddle. Give the one-line contradiction proof. ::: If $\nabla f\ne0$, step along $u=-\nabla f/\lVert\nabla f\rVert$; then $D_uf=-\lVert\nabla f\rVert<0$, so $f$ decreases — not a min. What is a stationary/critical point? ::: A point where $\nabla f=\mathbf0$. Why does the proof require an *interior* point? ::: We must be able to move in both $+h$ and $-h$ directions; boundary blocks one side. What classifies a stationary point after FONC? ::: The second-order test using the Hessian (definiteness / eigenvalue signs). Counterexample where $f'(0)=0$ but $0$ is not an extremum. ::: $f(x)=x^3$ (inflection); or $f(x,y)=x^2-y^2$ (saddle). $D_u f(x^*)=?$ ::: $\nabla f(x^*)\cdot u$, the dot product of gradient with the unit direction. --- > [!recall]- Feynman: explain to a 12-year-old > Imagine you're blindfolded on a smooth hilly field and you want the lowest spot. You feel the slope under your feet. If the ground tilts *any* way, you step downhill and get lower — so you're not at the bottom yet. Only when the ground feels perfectly **flat** could you possibly be at the very bottom. That "flatness in every direction" is what "gradient = zero" means. But careful: the top of a hill *and* a horse-saddle shape are flat too! So flat is a *clue*, not a *guarantee* — you still have to look around to know which one you're standing on. > [!mnemonic] > **"Flat is a finalist, not the winner."** Gradient $=0$ gets you onto the shortlist; the Hessian judges the contest. --- ## Connections - [[Gradient and directional derivatives]] — the tool that powers the proof. - [[Hessian matrix and second-order conditions]] — decides max / min / saddle. - [[Saddle points]] — the trap FONC can't catch alone. - [[Lagrange multipliers]] — FONC generalised to *constrained* problems. - [[Gradient descent]] — algorithm that literally chases $\nabla f \to 0$. - [[Convex functions]] — where stationary ⟹ global minimum. ## 🖼️ Concept Map ```mermaid flowchart TD F[Local interior optimum] -->|implies| FONC[FONC: grad f = 0] FONC -->|defines| SP[Stationary point] Diff[Difference quotient] -->|h to 0 plus| Ge[f' >= 0] Diff -->|h to 0 minus| Le[f' <= 0] Ge -->|combine| Zero1[f'=0 in 1D] Le -->|combine| Zero1 Zero1 -->|freeze coords| Multi[Every partial = 0] Multi -->|equivalent to| FONC Dir[Directional derivative Du = grad·u] -->|pick u = -grad| Contra[f decreases if grad not 0] Contra -->|proves| FONC SP -->|necessary not sufficient| Saddle[Max, min or saddle] Saddle -->|classify via| Hessian[Second-order Hessian test] ``` ## 🔊 Hinglish (regional understanding) > [!intuition]- Hinglish mein samjho > Socho tum ek smooth pahaadi field pe ho aur tumhe sabse neeche (minimum) ya sabse upar (maximum) pahunchna hai. Gradient $\nabla f$ ek arrow hai jo steepest uphill direction batata hai. Agar yeh arrow zero nahi hai, matlab koi na koi direction abhi bhi uphill ya downhill hai — to tum aur improve kar sakte ho. Iska seedha matlab: kisi bhi *interior* optimum pe gradient zero hona hi chahiye. Yahi hai **first-order necessary condition**: $\nabla f(x^*) = 0$. > > Lekin yahan ek important trap hai. Gradient zero hona **necessary** hai, **sufficient** nahi. Yani har minimum pe gradient zero hota hai, par har "gradient zero" point minimum nahi hota. Maximum pe bhi zero, aur saddle point (jaise $x^2 - y^2$) pe bhi zero. $x^3$ ka example dekho — $x=0$ pe derivative zero, par na max na min, sirf inflection. Isliye gradient = 0 sirf **candidates** (stationary points) deta hai; final faisla second-order test (Hessian ke eigenvalues) karta hai. > > Proof ka intuition bahut clean hai: agar $\nabla f \ne 0$ hota, to hum direction $u = -\nabla f/\lVert\nabla f\rVert$ me ek chhota step lete aur $D_u f = -\lVert\nabla f\rVert < 0$, yani $f$ kam ho jaata — to woh point minimum tha hi nahi. Contradiction! Isliye minimum pe gradient zero hi hoga. Bas dhyaan rakhna yeh argument tabhi chalta hai jab point **andar** (interior) ho — boundary pe tum dono directions me move nahi kar sakte, isliye wahan Lagrange/KKT lagti hai. ![[audio/4.10.18-First-order-optimality-conditions-—-gradient-=-0.mp3]]