First-order optimality conditions — gradient = 0

4.10.18 · Maths › Advanced Topics (Elite Level)

WHAT hai yeh condition?

WHY sach hai yeh? (derivation from scratch)

Hum ise derive karte hain; kabhi sirf quote nahi karte.

Step 1 — difference quotient likho. $\frac{f ( x ^{*} + h ) - f ( x ^{*} )}{h} .$ Yeh step kyun? Derivative is quotient ki limit hai; hum ise dono sides se squeeze karte hain.

Step 2 — right se approach karo ( $h \to 0^{+}$ ). Numerator $\geq 0$ , denominator $> 0$ , toh quotient $\geq 0$ , isliye $f^{'} (x^{*}) = lim_{h \to 0^{+}} (\dots) \geq 0.$ Kyun? Non-negative numbers ki limit non-negative hoti hai.

Step 3 — left se approach karo ( $h \to 0^{-}$ ). Numerator $\geq 0$ , denominator $< 0$ , toh quotient $\leq 0$ , isliye $f^{'} (x^{*}) \leq 0.$

Step 4 — combine karo. $f^{'} (x^{*}) \geq 0$ aur $f^{'} (x^{*}) \leq 0$ milke force karte hain $f^{'} (x^{*}) = 0.$ Yeh kyun kaam karta hai: differentiability ka matlab hai left aur right limits agree karni chahiye, aur humne us common value ko $\leq 0$ aur $\geq 0$ ke beech trap kar liya.

Step — har $i$ ke liye repeat karo. Har partial derivative zero ho jaata hai:

\quad\Longleftrightarrow\quad \nabla f(x^*)=\mathbf 0.$$ > [!formula] Directional-derivative version (sabse gehri wajah) > Unit direction $u$ mein directional derivative hai $D_u f(x^*)=\nabla f(x^*)\cdot u$. > Agar $\nabla f(x^*)\ne 0$, toh $u=-\nabla f/\lVert\nabla f\rVert$ choose karo. Tab > $$D_u f = -\lVert \nabla f(x^*)\rVert < 0,$$ > matlab $f$ $u$ ke along **decrease** karta hai — toh $x^*$ minimum tha hi nahi. Contradiction. Isliye $\nabla f(x^*)=\mathbf{0}$. ![[4.10.18-First-order-optimality-conditions-—-gradient-=-0.png]] --- ## Worked examples > [!example] 1-D: $f(x)=x^3-3x$ classify karo > **Step 1** $f'(x)=3x^2-3$. *Kyun?* FONC ke liye derivative chahiye. > **Step 2** $f'=0$ set karo $\Rightarrow x^2=1\Rightarrow x=\pm1$. *Kyun?* Stationary points candidates hote hain. > **Step 3** $f''(x)=6x$: $f''(1)=6>0$ (min), $f''(-1)=-6<0$ (max). *Kyun?* FONC max aur min mein fark nahi kar sakta; second-order test karta hai. > [!example] 2-D: $f(x,y)=x^2+xy+y^2-3y$ minimise karo > **Step 1** Gradient compute karo: > $$\nabla f=\begin{pmatrix}2x+y\\ x+2y-3\end{pmatrix}.$$ > *Kyun?* Har component ek partial derivative hai. > **Step 2** $=\mathbf0$ set karo: $2x+y=0,\;x+2y=3$. > **Step 3** Solve karo: pehle equation se $y=-2x$; substitute karo: $x+2(-2x)=3\Rightarrow -3x=3\Rightarrow x=-1,\;y=2$. > *Kyun?* Yeh ek hi stationary point hai. > **Step 4** Hessian $H=\begin{pmatrix}2&1\\1&2\end{pmatrix}$ ke eigenvalues $1,3>0$ hain ⟹ positive definite ⟹ $(-1,2)$ par **strict local (yahan global) minimum**, value $-3$. > [!example] Saddle warning: $f(x,y)=x^2-y^2$ > **Step 1** $\nabla f=(2x,-2y)=\mathbf0\Rightarrow (0,0)$. > **Step 2** $x$-axis ke along $f=x^2$ (badhta hai); $y$-axis ke along $f=-y^2$ (girta hai). *Yeh kyun matter karta hai:* gradient zero hai phir bhi yeh **na** max hai **na** min — ek saddle hai. Proof ki FONC akela kaafi nahi. > [!mistake] Steel-man: "Maine boundary bhool gayi/gaya" > **Kyun sahi lagta hai:** saare calculus problems jo hum practise karte hain "unconstrained" hain, toh hum sirf wahan dhundte hain jahan $\nabla f=0$. > **Kyun galat hai:** derivation ne assume kiya tha ki $x^*$ **interior** hai (hum *dono* directions mein step le sakte the). Ek closed domain par, min boundary par baith sakta hai jahan gradient zero **nahi** hona chahiye (woh baahir ki taraf point kar sakta hai). > **Fix:** boundary points bhi check karo / constraints ke liye Lagrange/KKT conditions use karo. --- ## #flashcards/maths Interior local optimum ke liye first-order necessary condition kya hai? ::: $\nabla f(x^*)=\mathbf{0}$ (har partial derivative zero hai). Kya $\nabla f=0$ minimum ke liye sufficient hai? ::: Nahi — yeh sirf necessary hai; point max ya saddle bhi ho sakta hai. One-line contradiction proof batao. ::: 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. Stationary/critical point kya hota hai? ::: A point where $\nabla f=\mathbf0$. Proof mein *interior* point kyun chahiye? ::: We must be able to move in both $+h$ and $-h$ directions; boundary blocks one side. FONC ke baad stationary point ko kaun classify karta hai? ::: The second-order test using the Hessian (definiteness / eigenvalue signs). Counterexample jahan $f'(0)=0$ par $0$ extremum nahi hai. ::: $f(x)=x^3$ (inflection); or $f(x,y)=x^2-y^2$ (saddle). $D_u f(x^*)=?$ ::: $\nabla f(x^*)\cdot u$, gradient aur unit direction ka dot product. --- > [!recall]- Feynman: 12-saal ke bachhe ko explain karo > Socho tum ek smooth pahadi field mein aankhon par patti baandhe ho aur tumhe sabse neechi jagah chahiye. Tum apne paanv ke neeche dhaalu feel karte ho. Agar zameen *kisi bhi* taraf jhukti hai, tum neeche ki taraf kadam uthao ge aur aur neeche pahunch jaoge — toh tum abhi tak talay nahi ho. Sirf jab zameen bilkul **flat** lage tabhi tum bilkul talay ho sakte ho. Yahi "har direction mein flatness" hai jo "gradient = zero" ka matlab hai. Lekin dhyan raho: pahadi ke upar aur horse-saddle shape bhi flat hoti hain! Toh flat ek *clue* hai, *guarantee* nahi — tumhe abhi bhi dekhna hoga ki tum kahan khade ho. > [!mnemonic] > **"Flat is a finalist, not the winner."** Gradient $=0$ tumhe shortlist mein laata hai; Hessian contest ka judge hai. --- ## Connections - [[Gradient and directional derivatives]] — woh tool jo proof ko power deta hai. - [[Hessian matrix and second-order conditions]] — decide karta hai max / min / saddle. - [[Saddle points]] — woh trap jo FONC akela nahi pakad sakta. - [[Lagrange multipliers]] — FONC *constrained* problems ke liye generalised. - [[Gradient descent]] — algorithm jo literally $\nabla f \to 0$ chase karta hai. - [[Convex functions]] — jahan 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] ```