Convex optimization — convex sets, convex functions: Foundations

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

Is page mein kuch bhi assume nahi kiya gaya. parent note ka har squiggle yahan ground up se build kiya gaya hai, ek aisi order mein jahan har symbol earn hota hai pehle agle symbol ke use se. Upar se neeche padho.

0. Sabse pehle ke symbols: numbers, points, aur $R^{n}$

Picture. $R^{1}$ ek line hai. $R^{2}$ ek flat sheet hai — ek point $(x_{1}, x_{2})$ hota hai, ek address "daayein $x_{1}$ jao, upar $x_{2}$ jao". $R^{3}$ aapke aas-paas ki space hai. $3$ se aage draw nahi kar sakte, lekin rules bilkul same rehte hain, isliye hum $R^{2}$ picture karte hain aur trust karte hain.

Topic ko iski zaroorat kyun hai. Optimization poochhta hai "kaun sa point best hai?" — yeh tab tak nahi pooch sakte jab tak pata nahi ki "point" kya hai aur woh kis "space" mein rehta hai. Baaki sab $R^{n}$ ke upar decoration hai.

1. Points ko mix karna: scalar multiplication aur vector addition

" $θ x + (1 - θ) y$ " ka sense banane se pehle, humein pata hona chahiye ki ek point ko stretch karna aur do points ko add karna matlab kya hai. Yeh do operations $R^{n}$ ki poori grammar hain.

Yeh kaisa dikhta hai — figure padho. Figure mein $x$ ko $\frac{1}{2} x$ tak scale kiya gaya hai (chhota, same direction), aur do arrows tip-to-tail add kiye gaye hain. Ek baar aap stretch aur add kar sakte hain, toh aap koi bhi mix $θ x + (1 - θ) y$ bana sakte hain: $x$ ko $θ$ se scale karo, $y$ ko $1 - θ$ se scale karo, phir do scaled arrows add karo.

Figure — Convex optimization — convex sets, convex functions

Topic ko iski zaroorat kyun hai. Har convex combination, har gradient step, har chord literally "scale, phir add" hai. Yahi do moves hain; chapter ka baaki hissa bas clever numbers choose karta hai scale karne ke liye.

2. Ek set, aur do points ke beech ka line segment

Ab is poore chapter ka sabse important construction: do points ke beech ka line segment, ek knob $θ$ ke saath likha gaya jise aap slide kar sakte hain. Yeh purely Section 1 ke scale-and-add operations se bana hai.

Yeh kaisa dikhta hai — figure padho. Jaise $θ$ $0$ se $1$ tak slide karta hai:

$θ = 0$ par: point $0 \cdot x + 1 \cdot y = y$ hai (aap $y$ par khadhe hain),
$θ = 1$ par: point $1 \cdot x + 0 \cdot y = x$ hai (aap $x$ par pahunch gaye),
$θ = \frac{1}{2}$ par: point $\frac{1}{2} x + \frac{1}{2} y$ hai, exact midpoint.

Toh formula $y$ se $x$ tak ke straight segment ko trace karta hai, aur $θ$ us par aapki position hai. Do weights $θ$ aur $1 - θ$ hamesha $1$ mein add hote hain — yahi "adds to $1$ " exactly aapko segment par rakhta hai aur kabhi usne door nahi hone deta.

Topic ko iski zaroorat kyun hai. "Koi dent nahi, koi hole nahi" — yeh symbols mein kehna hoga. Iske liye ek hi tool hai: do points lo, unke beech ka straight segment chalo, poochho ki segment andar rehta hai ya nahi. Yahi sawaal convexity hai.

3. Dot product aur $a^{⊤} x$ — flat walls kaise likhi jaati hain

Parent note mein half-spaces ${x : a^{⊤} x \leq b}$ jaisi likhi hain. Uske liye teen naye symbols chahiye: $a^{⊤}$ , dot product, aur $\leq$ ek poore expression par.

Yeh kaisa dikhta hai. Arrow $a$ fix karo. Equation $a^{⊤} x = b$ (ek fixed number $b$ ke liye) ek flat wall draw karta hai — 2-D mein ek line, 3-D mein ek plane — $a$ ke "right angles" par. $b$ upar-neeche slide karne se woh wall parallel mein shift ho jaati hai. Figure dekho: arrow $a$ wall ke aaar-paar point karta hai, aur $a^{⊤} x$ maapata hai ki point $x$ $a$ ki direction mein kitna dur gaya hai.

Topic ko iski zaroorat kyun hai. Half-space flat boundary wala sabse simple possible convex region hai. Bahut saare stack karo ("intersect" karo) aur tum ek polyhedron nikaalte ho — har linear program ka feasible region. Isliye $a^{⊤} x \leq b$ woh atom hai jisse convex feasible regions bante hain. Dot product norms aur inner products mein aur gradient (Section 6) mein bhi aata hai.

4. Vector ki length: norm $∥ x ∥$

Yeh kaisa dikhta hai. ${x : ∥ x ∥ \leq r}$ = "centre se $r$ distance ke andar saare points" = ek filled ball (2-D mein disk). ${x : ∥ x ∥ = r}$ = "exactly $r$ distance par points" = sirf rim. Same $r$ , wildly different sets — filled disk convex hai, rim nahi.

Topic ko iski zaroorat kyun hai. Balls convex set ka standard example hain, aur norm function $f (x) = ∥ x ∥$ triangle inequality se bana convex function ka standard example hai: $∥ u + v ∥ \leq ∥ u ∥ + ∥ v ∥ ("detour kabhi seedha jaane se chhota nahi hota") .$ Yahi picture hai "every norm is convex" ke peeche, aur yeh seedha Norms and Inner Products se link karta hai.

5. Graph, chord, aur epigraph

Yeh kaisa dikhta hai — figure padho. Bowl-shaped graph par do points lo aur unke beech chord draw karo. Convex function ke liye chord curve ke upar ya curve par baitta hai (bowl kabhi apni khud ki strings se upar bulge nahi karta). Epigraph — curve ke upar ki sand — toh ek dent-free region hai, yaani ek convex set. Yahi is poore topic ka deep secret hai: ek function convex hai exactly tab jab uska "above-region" ek convex set hai. Ek idea, do hats.

Topic ko iski zaroorat kyun hai. Yeh inequality is poore chapter ka engine hai: yeh "koi fake dips nahi" force karti hai, isliye convex function ka exactly ek bottom hota hai.

6. Bahut directions mein slopes: gradient $\nabla f$ aur Hessian $\nabla^{2} f$

Calculus se convexity test karne ke liye humein landscapes ke liye "slope" aur "curvature" chahiye.

Second derivative kyun, first kyun nahi? Convexity bending ke baare mein hai, tilting ke nahi. Ek straight ramp tilt karta hai ( $f^{'} \neq = 0$ ) lekin bend nahi karta ( $f^{''} = 0$ ) — aur ek ramp convex hai. Sirf second derivative bend dekhta hai, jo exactly "bowl-shaped" ka matlab hai. Isliye curvature test $f^{''}$ use karta hai, $f^{'}$ nahi.

Isliye first-order convexity test $f (y) \geq f (x) + \nabla f (x)^{⊤} (y - x)$ is tarah dikhta hai: right-hand side flat tangent plane ka prediction hai, aur convex ka matlab hai true surface hamesha us flat prediction ke upar baitta hai. Yeh woh object bhi hai jise Gradient Descent downhill follow karta hai ( $\nabla f$ ke against chalo).

Topic ko iski zaroorat kyun hai. Ek se zyada dimension mein ek surface ek axis ke along upar aur doosre ke along neeche curve kar sakti hai (saddle). Ek single number yeh capture nahi kar sakta; Hessian aur test $⪰ 0$ kar sakta hai, direction by direction, $v^{⊤} M v$ ke through.

7. Prerequisite map

Yahan hai yeh foundations topic ke do central definitions mein kaise flow karte hain.

Equipment checklist

Har sawaal padho, out loud jawab do, phir reveal karo. Agar koi bhi trip kare, parent note tackle karne se pehle uska section upar se dobara padho.

x \in C

ka plain words mein kya matlab hai?

Point

x

set

C

ka member hai (C ke andar rehta hai).

{x : x > 0}

mein colon ka kya matlab hai?

"Aisa ki" — un saare

x

ka collection jo uske baad wali rule satisfy karte hain.

λ x

aur

x + y

kaise compute karte hain?

x

ke har coordinate ko

λ

se scale karo;

x

aur

y

ko coordinate by coordinate add karo (tip-to-tail arrows).

Jaise

θ

0 \to 1

slide karta hai,

θ x + (1 - θ) y

kahan jaata hai?

y

(at

θ = 0

) se

x

(at

θ = 1

) tak ke straight segment ke along,

θ = \frac{1}{2}

par midpoint hit karte hue.

Convex set ki definition batao.

Saare

x, y \in C

aur saare

θ \in [0, 1]

ke liye,

θ x + (1 - θ) y \in C

— poora segment andar rehta hai.

Convex function ki definition batao.

f (θ x + (1 - θ) y) \leq θ f (x) + (1 - θ) f (y)

saare

x, y

aur

θ \in [0, 1]

ke liye — chord graph ke upar ya graph par rehti hai.

Weights

θ

aur

1 - θ

ka sum

1

kyun hona chahiye?

Taaki combined point exactly

x

aur

y

ke beech segment par rahe, kabhi usne door na jaaye.

Dot product

a^{⊤} x

kis tarah ka object hai — vector ya number?

Ek single number (yeh do vectors ko ek "alignment" value mein collapse karta hai).

{x : a^{⊤} x \leq b}

ki kya shape hai?

Ek half-space — flat wall

a^{⊤} x = b

ke ek taraf saare points.

R^{n}

mein norm

∥ x ∥

ka general formula?

∥ x ∥ = x_{1}^{2} + x_{2}^{2} + \dots + x_{n}^{2}

{∥ x ∥ \leq 1}

aur

{∥ x ∥ = 1}

mein kya difference hai?

Pehla filled disk hai (convex); doosra sirf rim circle hai (not convex).

f

ka epigraph kaisa dikhta hai?

Graph ke upar ya graph par sab kuch — surface ke upar daali gayi sand;

{(x, t) : t \geq f (x)}

Partial derivative

\partial f / \partial x_{i}

kya maapati hai?

Sirf

x_{i}

direction mein

f

ka slope, baaki saare coordinates fixed rakh ke.

Curvature test

f^{'}

ki jagah

f^{''}

kyun use karta hai?

Convexity bending ke baare mein hai, jo sirf

f^{''}

detect kar sakta hai;

f^{'}

sirf tilt maapata hai, aur ek tilted straight ramp phir bhi convex hai.

Hessian

\nabla^{2} f

ki entries kya hain, aur woh symmetric kyun hai?

Entry

ij

hai

\partial^{2} f / \partial x_{i} \partial x_{j}

; second derivatives ki symmetry entry

ij

ko entry

j i

ke barabar banati hai.

\nabla^{2} f ⪰ 0

ka kya matlab hai, spell out karo?

Har direction

v

ke liye,

v^{⊤} \nabla^{2} f v \geq 0

— surface har direction mein upar bend karti hai (ya flat rehti hai).

Connections

Parent topic — poora convexity note
Linear Programming — Section 3 ka half-space stack hokar feasible polyhedron banta hai.
Norms and Inner Products — norm (Section 4) aur dot product (Section 3) formalised.
Gradient Descent — Section 6 ke gradient arrow ko downhill follow karta hai.
Positive Definite Matrices — Section 6 ka Hessian test $⪰ 0$ .
Jensen's Inequality — Section 5 ki chord picture ko averages tak push kiya.
Lagrange Multipliers and KKT Conditions — convexity set hone ke baad gradients par build karta hai.