Convex optimization — convex sets, convex functions: Visual walkthrough

4.10.17 · D2 · Maths › Advanced Topics (Elite Level) › Convex optimization — convex sets, convex functions

Hum parent note ke central theorem ko unpack kar rahe hain:

Ek convex set $C$ par ek convex function $f$ ke liye, har local minimum ek global minimum hota hai.

Aao is sentence ka har word earn karte hain.

Step 1 — "Beech wala point" ka matlab kya hai

KYA. Koi bhi do points uthao. Unhe $x$ aur $y$ bolte hain. Unke "beech" ka point kuch aise likha jaata hai: $z_{θ} = θ y + (1 - θ) x .$ Har piece ko dheere padho:

$θ$ (Greek letter "theta") ek dial hai jo hum $0$ se $1$ tak ghumaate hain.
$(1 - θ)$ bas "jo bacha hua hai" hai, taaki dono weights milake hamesha $1$ ho jaayein.
Jab $θ = 0$ : humein $0 \cdot y + 1 \cdot x = x$ milta hai. Hum $x$ par khade hain.
Jab $θ = 1$ : humein $1 \cdot y + 0 \cdot x = y$ milta hai. Hum $y$ par khade hain.
Jab $θ = \frac{1}{2}$ : humein exact midpoint milta hai.

YEH formula kyun, koi aur kyun nahi? Kyunki yeh straight-line ka recipe hai. Jab hum dial $θ$ ko smoothly $0$ se $1$ tak ghumaate hain, point $z_{θ}$ straight segment par slide karta hai $x$ se $y$ tak — koi curve nahi, koi jump nahi. Yeh do points ke beech ka sabse simple "path" hai, aur neeche ki har idea is ek segment par tiki hui hai.

PICTURE. Dot straight line par slide karta hai jab dial $θ$ ghoomta hai.

Figure — Convex optimization — convex sets, convex functions

Step 2 — Convex SET kya guarantee karta hai

KYA. Ek set $C$ (soch lo: page par ek shaded region) convex hai jab: koi bhi $x, y$ andar se uthao, aur unke beech ka poora segment bhi andar rahe. Symbols mein, $x, y \in C ⟹ z_{θ} = θ y + (1 - θ) x \in C for all θ \in [0, 1] .$

ISKA KYUN ZAROORAT HAI. Hamara theorem ek point se doosre tak feasible region se bahar nikalein bina chalne ke baare mein hai. Convex set exactly yeh guarantee hai ki straight walk kabhi edge se nahi girta. Kisi dent (ya hole) waali region mein segment bahar ja sakta hai — aur phir Step 5 mein jo walk hum karte hain woh illegal ho jaata.

PICTURE. Left: ek convex blob — har chord andar rahta hai. Right: ek dented "bean" — ek chord bahar nikal jaata hai (red). Yahi escaping chord hai jo convexity forbid karta hai.

Recall Kyun "circle" convex NAHI hai lekin "disk" hai

Disk filled region hai — chords andar rahte hain. Circle sirf rim hai; ek chord seedha khaali middle se kat ke rim se bahar chala jaata hai. Convexity filled region ke baare mein hai, smoothness ke baare mein kabhi nahi. Circle vs disk — kaun sa convex hai? ::: Filled disk $∥ x ∥ \leq 1$ convex hai; rim $∥ x ∥ = 1$ nahi.

Step 3 — Convex FUNCTION kya guarantee karta hai

KYA. Ab region ke upar ek height lagao. Ek function $f$ ek point leta hai aur ek number return karta hai — graph par uski height. Hum $f$ ko convex kehte hain jab, kisi bhi do points $x, y$ ke liye, $beech mein actual height f (θ y + (1 - θ) x) \leq straight chord ki height θ f (y) + (1 - θ) f (x) .$ Term by term:

Left side in-between point $z_{θ}$ par graph ki real height hai.
Right side chord ki height hai — woh straight line jo do graph points $(x, f (x))$ aur $(y, f (y))$ ke beech khiinchi gayi — same $θ$ par evaluate ki gayi. Dhyan do, weight $θ$ multiply karta hai $f (y)$ ko (match karta hai jaise $θ$ multiply karta hai $y$ ko $z_{θ}$ ke andar), aur $(1 - θ)$ multiply karta hai $f (x)$ ko.
" $\leq$ " kehta hai: real graph chord se kabhi upar nahi jaata.

YEH "bowl-shaped" kyun hai. Bowl neeche ki taraf bulge karta hai; woh kisi string ke upar kabhi nahi bulge karta jo uske acroos khiinchi gayi ho. Yahi precisely hai "graph on or below every chord" — equivalently "chord upar". Yeh single inequality hi ek convex function ki poori personality hai.

PICTURE. Blue bowl; do points ke beech ek chord (orange) khincha hua; vertical green gap dikhata hai ki chord graph ke upar baithta hai beech mein har jagah.

Step 4 — "Local minimum" vs "global minimum": woh cheez jisse hum darte hain

KYA. Pehle, point $x^{⋆}$ ka ek neighbourhood matlab hai "usse kisi chhoti radius $ε > 0$ ke andar ke saare points" — woh chota disk ${z : ∥ z - x^{⋆} ∥ < ε}$ , jahan $∥ z - x^{⋆} ∥$ hai $z$ se $x^{⋆}$ ki doori (dekho Norms and Inner Products).

Ek global minimum $x^{⋆}$ woh point hai jahan $f (x^{⋆}) \leq f (z)$ har $z$ ke liye poori region mein — kuch bhi kahin bhi neeche nahi.
Ek local minimum $x^{⋆}$ zyada weak hai: koi koi radius $ε > 0$ exist karta hai aise ki $f (x^{⋆}) \leq f (z)$ har $z$ ke liye jo $x^{⋆}$ se $ε$ distance ke andar ho. Yeh sirf apne chhote neighbourhood ke andar lowest hai — ek dip jisme tum fas sakte ho bhale hi door koi gehri valley ho.

YEH distinction poora game kyun hai. Optimization algorithms (jaise Gradient Descent) locally apna raasta feel karte hain — woh sirf apne paon ke neeche chhoti radius ke andar ki zameen dekhte hain. Ek bumpy (non-convex) landscape par woh ek shallow dip mein settle ho sakte hain aur victory declare kar sakte hain, asli bottom miss karte hue. Yeh theorem jo hum prove karne waale hain kehta hai: ek convex bowl par yeh trap exist nahi kar sakta.

PICTURE. Upar: ek wavy non-convex curve jisme ek fake dip (red) aur asli bottom (green) hai — ek marble red mein fas sakti hai. Neeche: ek convex bowl — sirf ek bottom, koi trap nahi.

Step 5 — Proof: maano ek trap exist karta hai, phir use destroy karo

Yahi payoff hai. Hum contradiction se argue karte hain: hum pretend karte hain ki ek fake trap exist karta hai aur dikhate hain ki convex inequality ise impossible bana deti hai.

HUM KYA ASSUME KARTE HAIN. Maano $x^{⋆}$ ek local minimum hai, lekin kahin door ek point $y$ baitha hai jo strictly neeche hai: $f (y) < f (x^{⋆}) .$

HUM KYA KARTE HAIN — $x^{⋆}$ se $y$ ki taraf chalo. Kyunki $C$ ek convex set hai (Step 2), poora segment legal hai, isliye hum ek tiny step le sakte hain: $z_{θ} = θ y + (1 - θ) x^{⋆}, θ bahut chhota aur positive.$ Yahan $θ$ small ka matlab hai $z_{θ}$ bilkul $x^{⋆}$ ke paas hai — Step 4 ke neighbourhood (radius $ε$ ) ke andar.

CONVEXITY KYA FORCE KARTA HAI. Step 3 ki convex-function inequality apply karo in exact points par: $f (z_{θ}) \leq θ f (y) + (1 - θ) f (x^{⋆}) .$ Ab right-hand side ko dhyan se dekho. Kyunki $f (y) < f (x^{⋆})$ , $f (x^{⋆})$ ka "share" $θ$ ko chhotey number $f (y)$ se replace karna average ko strictly neeche khiinchta hai: $θ f (y) + (1 - θ) f (x^{⋆}) < θ f (x^{⋆}) + (1 - θ) f (x^{⋆}) = f (x^{⋆}) .$ Dono lines chain karte hue: $f (z_{θ}) < f (x^{⋆}) .$

YEH CONTRADICTION KYUN HAI. Humne ek aisa point $z_{θ}$ dhundh liya jo (a) $x^{⋆}$ ke arbitrarily close hai (kyunki $θ$ tiny hai, isliye $z_{θ}$ radius $ε$ ke andar baitha hai) par (b) $x^{⋆}$ se strictly neeche hai. Yahi woh cheez hai jo " $x^{⋆}$ ek local minimum hai" forbid karta hai. Assumption "ek lower $y$ exist karta hai" collapse ho jaata hai. Isliye koi bhi point $x^{⋆}$ se neeche nahi hai — yeh global hai. $■$

PICTURE. $x^{⋆}$ se $y$ ki taraf tiny step chord (orange) par land karta hai, jo convexity $f (x^{⋆})$ ki height par flat dashed line ke neeche rakhta hai — isliye wahan graph aur neeche hai.

Step 6 — Tangent view: wahi baat neeche se

KYA — pehle, tools, zero se. Ek smooth (differentiable) $f$ ke liye humein do cheezein chahiye:

Gradient $\nabla f (x)$ (bolo "grad $f$ ") simply $x$ par graph ka slope hai: ek dimension mein yeh ordinary derivative $f^{'} (x)$ hai; zyada dimensions mein yeh har direction mein slopes ki list hai. Yeh steepest-uphill direction mein point karta hai.
Dot product $\nabla f (x)^{⊤} (y - x)$ slope ko displacement $(y - x)$ se multiply karta hai aur results add karta hai — yeh padhta hai flat slope kitni height predict karta hai agar tum $x$ se $y$ tak chalo. (" $^{⊤}$ " bas matlab hai "line them up aur multiply-then-sum"; dekho Norms and Inner Products.) Ek dimension mein yeh simply $f^{'} (x) \cdot (y - x)$ hai.

Ab convexity ka doosra face: graph har tangent line ke upar rahta hai: $f (y) \geq x par height f (x) + tangent ki predicted rise \nabla f (x)^{⊤} (y - x) .$ " $\geq$ " kehta hai ki real graph hamesha us flat prediction se kam se kam utna uuncha hai.

BOTTOM DHUNDHNE MEIN YEH KYUN MATTER KARTA HAI. Slope zero karo: $\nabla f (x^{⋆}) = 0$ . Phir inequality ban jaati hai $f (y) \geq f (x^{⋆})$ har $y$ ke liye — ek instant certificate ki $x^{⋆}$ global bottom hai. Isliye "slope $= 0$ " sirf ek candidate nahi balki ek convex bowl par guarantee hai.

TWO-DIMENSIONAL CURVATURE TEST KE BAARE MEIN KYA? Ek twice-differentiable $f$ ke liye Hessian $\nabla^{2} f (x)$ hota hai — second derivatives ki table (saare "slope khud kaise change hota hai" numbers). Hum kehte hain yeh positive semidefinite hai, likha $\nabla^{2} f (x) ⪰ 0$ (symbol " $⪰ 0$ " matlab hai "har direction mein upar ya flat curves karta hai, kabhi neeche nahi"), exactly jab $f$ convex ho. Ek dimension mein yeh jaane-maane $f^{''} (x) \geq 0$ mein collapse ho jaata hai. $⪰$ ki poori kahani ke liye dekho Positive Definite Matrices.

PICTURE. $x$ par tangent (orange) poore blue graph ke neeche slide karta hai; green gap $f (y) - [tangent height]$ kabhi negative nahi hota. Flat tangent par, graph ka lowest point seedha uspe baitha hai.

Step 7 — Edge aur degenerate cases (taaki kabhi surprise na ho)

Convexity ke soft edges hain. Yahan boundary situations hain, har ek dikhaya gaya hai taaki koi scenario unseen na rahe.

Case A — flat line. $f (x) = c$ (horizontal graph) convex hai: chord graph ke barabar hai, isliye " $\leq$ " equality ke saath hold karta hai. Lekin yeh strictly convex nahi hai (Step 3) — chord graph ko touch karta hai strictly upar rehne ki bajay. Yahan har point simultaneously local aur global minimum hai — ek poori flat valley. Theorem phir bhi hold karta hai (har ek global hai), lekin minimizer unique nahi hai. Flatness exactly wajah hai kyun Step 5 mein uniqueness ke liye humein strict convexity chahiye thi.

Case B — kink. $f (x) = ∣ x ∣$ mein $0$ par ek sharp corner hai aur wahan koi slope nahi, isliye Step 6 ka tangent test tip par apply nahi ho sakta. Phir bhi yeh genuinely convex hai (uske chords upar rehte hain) aur $0$ par uska minimum global hai. Lesson: convexity ke liye smoothness ki zaroorat nahi; jab tangent test fail ho jaaye, chord definition Step 3 par wapas jaao.

Case C — khaali beech (non-convex domain). Agar $C$ mein hole ya dent hai, Step 5 ka " $y$ ki taraf tiny step" $C$ se bahar ja sakta hai — walk illegal ho jaati hai aur guarantee gaayab ho jaati hai. Isliye dono set aur function convex hone chahiye; koi bhi drop karo aur traps wapas aa sakte hain.

PICTURE. Teen panels: (A) flat valley — kaafi saare minima; (B) $∣ x ∣$ global-min kink ke saath; (C) ek dented domain jahan straight walk bahar nikal jaata hai (red).

Ek-picture summary

Upar sab kuch ek frame mein compress ho jaata hai: ek convex region par ek convex bowl, uska lowest point marked, ek tiny arrow dikhata hai ki kisi allegedly-lower point ki taraf step karna tumhe usi slope pe aur neeche le jaata hai — isliye pehla bottom jo tumhe mila, wahi aur sirf wahi bottom hai.

Recall Feynman retelling — poora walkthrough plain words mein

Ek smooth skate-bowl imagine karo jisme koi dent nahi, koi hole nahi (yahi convex set hai — Step 2). Surface khud bowl ki tarah jhukti hai, kisi string ke upar kabhi nahi bulge karti jo tum uske across khiincho (yahi convex function hai — Step 3). Ab ek marble giraao aur use kisi low spot, $x^{⋆}$ , par settle hone do. Kya kahin aur koi secret gehra spot $y$ ho sakta hai? $x^{⋆}$ se seedha $y$ ki taraf baby step lo. Kyunki bowl har string ke neeche jhukti hai, woh baby step already wahan se neeche hai jahan se tum start kiye the (Step 5). Lekin tum abhi settle kiye the — tumhare bilkul paas kuch bhi neeche nahi hona chahiye tha! Contradiction. Isliye koi secret gehra spot exist nahi karta: tumhara pehla bottom hi asli bottom hai. Aur slope ki najar se (Step 6), jis pal tumhare paon ke neeche zameen flat ho jaati hai, tumhara global bottom par hona guaranteed hai. Sirf kuch wrinkles: ek perfectly flat valley mein kaafi saare equally-low spots hain (ek single ke liye strict sag chahiye), ek sharp V-kink mein test karne ke liye koi slope nahi lekin phir bhi kaam karta hai, aur agar region mein hole hai toh tumhara straight walk edge se gir sakta hai — isliye dono region aur surface dent-free hone chahiye.

Connections

Gradient Descent — locally neeche ki taraf chalta hai; convexity wahi hai jo "downhill" ko global bottom tak pahunchata hai.
Lagrange Multipliers and KKT Conditions — Step 6 ka "slope $= 0$ global min certify karta hai" isliye KKT convexity ke under sufficient ban jaata hai.
Positive Definite Matrices — multi-dimensional "curves upward" test $\nabla^{2} f ⪰ 0$ aur $⪰$ symbol.
Jensen's Inequality — Step 3 chord inequality averages tak generalize hoti hai.
Norms and Inner Products — Step 6 ka dot product $\nabla f (x)^{⊤} (y - x)$ aur distance $∥ z - x^{⋆} ∥$ ; aur har norm (jaise Case B mein $∣ x ∣$ ) convex hai.
Linear Programming — yahan convex set polyhedral feasible region hai.