4.10.17
Intuition Bada picture (WHY convexity matter karta hai)Optimization mein hum ek region ke upar ek function ko minimize karna chahte hain. Sabse bada darr yeh hai ki hum ek local minimum mein fas jaayein jo global minimum nahi hai. Convexity woh geometric property hai jo local minima ko khatam karti hai : agar region AUR function dono "bowl-shaped" hain — koi dent nahi — toh har local minimum automatically global minimum hota hai. Yahi ek fact hai jiske wajah se convex problems woh hain jo hum actually reliably aur bade scale par solve kar sakte hain.
Ek set C ⊆ R n convex hai agar har do points x , y ∈ C θ ∈ [ 0 , 1 ] θ x + ( 1 − θ ) y ∈ C . set ke kisi bhi do points ko milane wala poora line segment set ke andar hi rehta hai .
WHAT hai θ x + ( 1 − θ ) y θ 0 1 y θ = 0 x θ = 1 convex combination hai.
WHY yeh definition? "Koi dent nahi, koi hole nahi." Ek disk convex hai; ek crescent moon nahi hai (ek chord bahar ja sakta hai). Ek donut nahi hai (ek chord hole se cross karta hai).
Worked example Convexity test karna
Convex: R n { x : ∥ x − c ∥ ≤ r } { x : a ⊤ x ≤ b } Not convex: unit circle { x : ∥ x ∥ = 1 } { x : ∥ x ∥ ≥ 1 }
Why ek half-space convex hai (step): lo x , y a ⊤ x ≤ b , a ⊤ y ≤ b a ⊤ ( θ x + ( 1 − θ ) y ) = θ a ⊤ x + ( 1 − θ ) a ⊤ y ≤ θ b + ( 1 − θ ) b = b Why yeh step? a ⊤ ( ⋅ )
Definition Convex functionf : R n → R convex hai agar uska domain ek convex set hai aur sabhi x , y θ ∈ [ 0 , 1 ] f ( θ x + ( 1 − θ ) y ) ≤ θ f ( x ) + ( 1 − θ ) f ( y ) . graph par do points ke beech ka chord (seedhi line) graph ke upar ya uspe hi rehta hai . Strictly convex agar x = y , θ ∈ ( 0 , 1 ) < Concave = − f
WHY yeh inequality? LHS = function ki actual height midpoint-jaisi jagah par. RHS = wahan chord ki height. Convex matlab bowl apne khud ke chords ke upar kabhi bulge nahi karta.
Intuition Dono definitions ke beech ka linkEk function convex hota hai iff uska epigraph epi ( f ) = {( x , t ) : t ≥ f ( x )} upar ya uspar sab kuch — ek convex set hai. Toh convex functions simply woh functions hain jinka "upar-wala region" ek convex set hai. Ek concept, do chehra.
Worked example Functions ko classify karna
f ( x ) = x 2 f ′′ = 2 ≥ 0 f ( x ) = e x f ′′ = e x > 0 f ( x ) = log x f ′′ = − 1/ x 2 < 0 f ( x ) = ∥ x ∥ Step: ∥ θ x + ( 1 − θ ) y ∥ ≤ θ ∥ x ∥ + ( 1 − θ ) ∥ y ∥ Why? triangle ineq + absolute homogeneity. (0 definition use ki, Hessian nahi.)f ( x , y ) = x 2 + y 2 = ( 2 0 0 2 ) ⪰ 0
Common mistake Classic errors ko steel-man karnaMistake 1: "Boundary circle ∥ x ∥ = 1
Kyun sahi lagta hai: "round = koi corner nahi = convex." Fix: convexity filled region ke baare mein hai, na boundary curve ke baare mein. Closed disk ∥ x ∥ ≤ 1 circle (sirf rim) nahi hai — ek chord khaali middle se guzarta hai. Convexity ≠ smoothness.
Mistake 2: "f f ′′ > 0
Kyun sahi lagta hai: parabolas mein f ′′ = 2 > 0 Fix: convex ko sirf f ′′ ≥ 0 f ′′ = 0 f ′′ > 0 har jagah strict convexity ke liye sufficient hai lekin necessary nahi — jaise f ( x ) = x 4 f ′′ ( 0 ) = 0 < x 4
Mistake 3: "Ek convex aur ek concave function ka sum... kuch achha hota hai."
Kyun sahi lagta hai: symmetry. Fix: convex + convex = convex (chords add hote hain), lekin convex + concave kuch bhi ho sakta hai. Convexity sirf nonnegative combinations se preserve hoti hai: ∑ α i f i , α i ≥ 0
Recall Feynman: 12-saal ke bachche ko explain karoSocho ek skate ramp jo bowl ki shape mein hai. Koi bhi marble andar kahin bhi giraa do — woh hamesha ek hi sabse neeche wale point par aata hai. Yahi convex function hai: sirf ek bottom hai, isliye tum kabhi ek nakli "low spot" par nahi rukoge. Ek convex set woh region hai jisme koi dent nahi, koi hole nahi: koi bhi do jagah chuno usme, unke beech seedha string kheecho, string kabhi region se bahar nahi jaayegi. Optimization hai "bottom dhundo"; convexity guarantee karta hai ki bottom dhoondna aasaan hai aur sirf ek hi hai.
"Chord upar, set beech mein, tangent neeche."
Convex function : chord graph ke upar rehta hai.
Convex set : segment beech mein rehta hai (andar).
First-order: tangent graph ke neeche rehti hai.
Linear Programming — feasible region = half-spaces ka intersection = convex polyhedron.Gradient Descent — ek convex objective ke liye yeh global min par converge karta hai (na ki local par), provided usual algorithmic conditions hold karein: sensible step-size rule aur smoothness/Lipschitz-gradient assumptions. Convexity local-min traps hataati hai; yeh akele convergence guarantee nahi karta.Lagrange Multipliers and KKT Conditions — KKT convexity ke under sufficient ban jaata hai (sirf necessary nahi).Positive Definite Matrices — Hessian test ∇ 2 f ⪰ 0 Jensen's Inequality — convexity inequality ko expectations tak generalize kiya.Norms and Inner Products — har norm ek convex function hai.
Ek convex set define karo. Sabhi x , y ∈ C , θ ∈ [ 0 , 1 ] θ x + ( 1 − θ ) y ∈ C
Ek convex function define karo. f ( θ x + ( 1 − θ ) y ) ≤ θ f ( x ) + ( 1 − θ ) f ( y )
Convex set aur convex function ke beech geometric link kya hai? f ⟺ {( x , t ) : t ≥ f ( x )}
First-order convexity condition kya hai? f ( y ) ≥ f ( x ) + ∇ f ( x ) ⊤ ( y − x )
Second-order convexity condition kya hai? Hessian ∇ 2 f ( x ) ⪰ 0 x f ′′ ≥ 0
Convexity global minima kyun guarantee karta hai? Paas mein ek better point + segment-staying-inside + chord inequality local-minimality ka contradiction karta hai, isliye local = global.
Kya circle ∥ x ∥ = 1 Nahi — ek chord khaali interior se guzarta hai. Closed disk ∥ x ∥ ≤ 1
Sets ki convexity kya preserve karta hai? Intersection aur affine images (aur isliye polyhedra { x : A x ≤ b }
Functions ki convexity kya preserve karta hai? Nonnegative weighted sums, convex functions ka max, affine map ke saath composition.
Kya strict convexity ke liye f ′′ > 0 Nahi — f ′′ > 0 x 4 f ′′ ( 0 ) = 0 f ′′ ≥ 0
Every local min is global
Reliable large-scale solving
