Convex optimization — convex sets, convex functions: Worked examples

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

Scenario matrix

Cell	Case class	Kya mushkil hai	Example
A	Convex set, definition se prove karo	general segment ko handle karna padega, saare $θ$ ke liye	Ex 1
B	Not convex set — counterexample banao	specific $x, y, θ$ exhibit karne honge jo escape karte hain	Ex 2
C	1-D function, smooth, $f^{''} \geq 0$ test	$f^{''}$ ka sign, aur $f^{''} = 0$ edge case	Ex 3
D	1-D function, non-smooth (kink) — no Hessian	definition pe wapas jaana padega	Ex 4
E	Multivariable, Hessian PSD test, saare cases	eigenvalues / definiteness incl. degenerate	Ex 5
F	Composition / combination rules	kaun se operations convexity preserve karte hain	Ex 6
G	Real-world word problem (optimization)	words → convex program translate karo, global-min theorem use karo	Ex 7
H	Exam twist — ek false-looking claim ko disprove karo	limiting/degenerate behaviour	Ex 8

Worked example Ex 1 — Cell A · Ek ball convex hai (raw definition se prove karo)

Statement. Dikhao ki closed ball $B = {x \in R^{n} : ∥ x - c ∥ \leq r}$ convex hai, centre $c$ aur radius $r \geq 0$ ke liye.

Forecast: guess karo kyun segment ek ball se escape nahi kar sakta — kya triangle inequality kaam kar rahi hai ya Hessian?

Do members lo. Let $x, y \in B$ , so $∥ x - c ∥ \leq r$ and $∥ y - c ∥ \leq r$ . Koi bhi $θ \in [0, 1]$ lo; let $z = θ x + (1 - θ) y$ . Yeh step kyun? Ek convex set ki definition ek statement hai har pair aur har $θ$ ke baare mein — isliye hume ek fully general pair se shuru karna padega, koi special wala nahi.
$z$ ki centre se distance measure karo. Likho $c = θ c + (1 - θ) c$ (valid hai kyunki $θ + (1 - θ) = 1$ ), so $z - c = θ (x - c) + (1 - θ) (y - c) .$ Yeh step kyun? Hume $∥ z - c ∥$ chahiye; centre ko convex combination ke roop mein rewrite karne se difference cleanly split ho jaata hai.
Triangle inequality apply karo, phir absolute homogeneity ( $∥ α v ∥ = ∣ α ∣ ∥ v ∥$ , aur $θ, 1 - θ \geq 0$ ): $∥ z - c ∥ \leq θ ∥ x - c ∥ + (1 - θ) ∥ y - c ∥ \leq θ r + (1 - θ) r = r .$ Yeh step kyun? Norm khud convex hai — triangle inequality exactly woh tool hai jo ek inequality ko ek weighted average ke through push karta hai. Isliye yahan Hessian nahi, balki yahi natural engine hai.
Conclude karo. $∥ z - c ∥ \leq r$ matlab $z \in B$ . Kyunki $x, y, θ$ arbitrary the, $B$ is convex. $■$

Verify: degenerate cases confirm karte hain ki kuch break nahi hota. $r = 0$ → $B = {c}$ , ek single point: $c$ se $c$ tak ka segment sirf $c$ hai, abhi bhi andar. $θ = 0$ → $z = y \in B$ ; $θ = 1$ → $z = x \in B$ . Saare endpoints aur point-set limit pass karte hain.

Figure s01 (below). Violet disk ball $B$ hai; do navy dots ek arbitrary pair $x, y$ hain; magenta segment unhe join karta hai; orange dot $z = \frac{1}{2} x + \frac{1}{2} y$ hai, disk ke andar baitha hua — step 4 ki picture. Centre se arrow radius $r$ ko mark karta hai jise step 3 kabhi exceed nahi karta.

Figure — Convex optimization — convex sets, convex functions

Worked example Ex 2 — Cell B · Unit

circle (rim) convex NAHI hai Statement. Prove karo ki $S = {x \in R^{2} : ∥ x ∥ = 1}$ (circle khud, disk nahi) convex nahi hai.

Forecast: ek "for all" claim ko disprove karne ke liye tumhe sirf ek escaping segment chahiye. Kaun se do points sabse clean counterexample denge?

$S$ ke do members lo. $x = (1, 0)$ aur $y = (- 1, 0)$ lo. Dono ke liye $∥ x ∥ = ∥ y ∥ = 1$ , isliye dono circle pe hain. Yeh step kyun? Diametrically opposite points woh segment dete hain jo seedha centre ke through jaata hai — sabse obvious escape.
Midpoint lo ( $θ = \frac{1}{2}$ ): $z = \frac{1}{2} x + \frac{1}{2} y = (0, 0)$ . Yeh step kyun? Ek concrete $θ$ hi counterexample ke liye kaafi hai.
Membership check karo. $∥ z ∥ = ∥ (0, 0) ∥ = 0 \neq = 1$ , so $z \in / S$ . Yeh step kyun? Humne ek pair aur ek $θ$ dhundha jo definition violate karta hai — yahi "convex" ki logical negation hai.
Conclude karo. $S$ is not convex. $■$ (Contrast: filled disk $∥ x ∥ \leq 1$ is convex — Ex 1 with $c = 0, r = 1$ .)

Verify: sanity — yahan chord ki length $2$ hai, diameter, aur uska midpoint centre se distance $0$ pe hai, empty middle ke andar. Yahi parent note ki Mistake 1 hai: round $\neq =$ convex.

Figure s02 (below). Sirf violet rim set $S$ hai (beech khali hai). Magenta chord $x = (1, 0)$ aur $y = (- 1, 0)$ ko join karta hai; uska orange midpoint origin pe land karta hai — ek point rim pe nahi, exactly woh escape jo step 3 mein mili.

Worked example Ex 3 — Cell C · Smooth 1-D, including the

$f^{''} = 0$ trap Statement. Har ek ko apne natural domain pe classify karo convex / strictly convex / concave / neither ke roop mein: (a) $f (x) = x^{4}$ , (b) $g (x) = x^{3}$ , (c) $h (x) = 3 x + 2$ .

Forecast: in mein se kaun strictly convex hai jabki $f^{''} = 0$ kahin pe hai?

(a) $f^{''} (x) = 12 x^{2}$ . Yeh saare $x$ ke liye $\geq 0$ hai, isliye $f$ convex hai. Yeh $0$ ke barabar sirf single point $x = 0$ pe hota hai. Yeh step kyun? Second-order test $f^{''} \geq 0$ convexity certify karta hai; ek single zero usse khatam nahi karta. Kya yeh strictly convex hai? Yahan precise justification hai (sirf picture nahi). Strict convexity ke liye sufficient condition: agar $f^{''} (x) \geq 0$ har jagah hai aur $f^{''} > 0$ except on a set with no interval (isolated points), toh $f$ strictly convex hai. Reason: strict convexity equivalent hai $f^{'}$ ke strictly increasing hone ke; aur $f^{'}$ strictly increasing hoti hai jab bhi $f^{''} \geq 0$ ho aur $f^{''} > 0$ off isolated points, kyunki kisi bhi interval $[a, b]$ pe hume milta hai $f^{'} (b) - f^{'} (a) = \int_{a}^{b} f^{''} > 0$ (integrand isolated points ke alawa positive hai, isliye integral strictly positive hi rehta hai). $x^{4}$ ke liye: $f^{''} = 12 x^{2} > 0$ except at isolated point $x = 0$ , isliye $f^{'} = 4 x^{3}$ strictly increasing hai, hence $x^{4}$ strictly convex hai. Yahi parent ki Mistake 2 hai: $f^{''} > 0$ har jagah sufficient hai lekin necessary nahi.
(b) $g^{''} (x) = 6 x$ . $x > 0$ ke liye positive, $x < 0$ ke liye negative. Sign flip hota hai, isliye $g$ $[0, \infty)$ pe convex hai, $(- \infty, 0]$ pe concave hai, aur poore $R$ pe neither hai. Yeh step kyun? Convexity puri stated domain ke liye ek property hai; kahin bhi ek sign change globally disqualify kar deta hai.
(c) $h^{''} (x) = 0$ har jagah. Toh $h^{''} \geq 0$ (convex) aur $h^{''} \leq 0$ (concave). Ek straight line dono convex aur concave hoti hai — lekin strictly kuch bhi nahi, kyunki uske chords graph ke saath coincide karte hain (equality, isliye strict definition ka " $<$ " fail karta hai). Yeh step kyun? Woh boundary case cover karta hai jahan $f^{''} = 0$ pore interval pe hota hai, sirf isolated points pe nahi — isliye step 1 ka sufficient condition apply nahi hota, aur strictness genuinely fail karti hai.

Verify: (a) ke liye numeric chord check $x = - 1, y = 1, θ = \frac{1}{2}$ pe: LHS $f (0) = 0$ , RHS $\frac{1}{2} (1) + \frac{1}{2} (1) = 1$ ; $0 < 1$ ✔ strict. (c) ke liye $x = 0, y = 2, θ = \frac{1}{2}$ pe: LHS $h (1) = 5$ , RHS $\frac{1}{2} (2) + \frac{1}{2} (8) = 5$ ; $5 = 5$ ✔ equality confirm karta hai "both, not strict."

Worked example Ex 4 — Cell D · Non-smooth function: no Hessian, definition use karo

Statement. Kya $f (x) = ∣ x ∣$ convex hai? Iske $0$ pe ek corner hai jahan $f^{'}$ exist nahi karta.

Forecast: kink pe Hessian test unavailable hai. Uski jagah kaun sa tool aata hai?

Obstruction note karo. $f^{'} (x) = + 1$ for $x > 0$ , $- 1$ for $x < 0$ , $0$ pe undefined. Toh $f^{''} (0)$ exist nahi karta — second-order test corner pe inapplicable hai. Yeh step kyun? Tumhe pehchanna hoga kab ek test legal hai. Hessian test ke liye twice-differentiability chahiye, jo yahan fail hoti hai.
Raw chord definition pe wapas jao. Kisi bhi $x, y$ aur $θ \in [0, 1]$ ke liye, triangle inequality aur absolute homogeneity use karo: $∣ θ x + (1 - θ) y ∣ \leq ∣ θ x ∣ + ∣ (1 - θ) y ∣ = θ ∣ x ∣ + (1 - θ) ∣ y ∣.$ Yeh step kyun? Definition ko derivatives ki zaroorat nahi — yeh corners pe, cusps pe, har jagah kaam karta hai. Triangle inequality lifting kar rahi hai, exactly Ex 1 ki tarah.
Result padho. Yahi precisely $f (θ x + (1 - θ) y) \leq θ f (x) + (1 - θ) f (y)$ hai: $f = ∣ x ∣$ is convex. Yeh step kyun? Derived line ko definition se match karna proof close karta hai.
Strict? Nahi: $[0, \infty)$ pe, $∣ x ∣ = x$ linear hai, isliye wahan chords graph ke saath coincide karte hain (equality) — strict definition ka " $<$ " us poore interval pe fail hota hai. Convex lekin not strictly.

Verify: $x = - 2, y = 4, θ = \frac{1}{2}$ pe: LHS $∣1∣ = 1$ , RHS $\frac{1}{2} (2) + \frac{1}{2} (4) = 3$ ; $1 \leq 3$ ✔. $x = 2, y = 4$ pe (same sign): LHS $∣3∣ = 3$ , RHS $\frac{1}{2} (2) + \frac{1}{2} (4) = 3$ ; $3 = 3$ ✔ (equality — hence not strict).

Worked example Ex 5 — Cell E · Multivariable Hessian: PSD, PD, aur degenerate case

Statement. $R^{2}$ pe har function ke liye Hessian se convexity decide karo: (a) $f = x^{2} + x y + y^{2}$ , (b) $g = x^{2} - y^{2}$ , (c) $h = (x + y)^{2}$ .

Forecast: in mein se ek convex hai lekin strictly nahi — uska Hessian PSD hai lekin PD nahi. Kaun sa?

Test yaad karo. $f$ is convex $⟺$ Hessian $\nabla^{2} f ⪰ 0$ (positive semidefinite) har jagah. " $⪰ 0$ " matlab saare eigenvalues $\geq 0$ ; strictly convex guaranteed hai " $≻ 0$ " se (saare $> 0$ ). Yeh step kyun? Test karne se pehle exact threshold name karna padega — yahi PSD criterion hai.
(a) $\nabla^{2} f = (2112)$ . Eigenvalues solve karo $(2 - λ)^{2} - 1 = 0 \Rightarrow λ = 1, 3$ . Dono $> 0$ → positive definite → strictly convex. Yeh step kyun? Constant Hessian matlab "everywhere" automatic hai; eigenvalues sign class decide karte hain.
(b) $\nabla^{2} g = (20 0 - 2)$ , eigenvalues $2$ aur $- 2$ . Negative eigenvalue → indefinite → neither convex nor concave (ek saddle). Yeh step kyun? Ek negative eigenvalue hi PSD ko break karne ke liye kaafi hai, hence convexity fail hoti hai.
(c) $\nabla^{2} h = (2222)$ , eigenvalues $0$ aur $4$ . Saare $\geq 0$ → PSD but not PD → convex but NOT strictly. Zero eigenvalue flat valley $x + y = const$ ki direction mein point karta hai jahan function constant hai, isliye strict " $<$ " us poori line pe fail karta hai. Yeh step kyun? Yeh degenerate case hai: " $= 0$ " eigenvalue woh direction hai jahan koi curvature nahi — minima ki ek poori flat trough, isliye koi unique minimiser nahi.

Verify: eigenvalue products = determinants: (a) $det = 3$ , $λ$ -product $1 \cdot 3 = 3$ ✔; (b) $det = - 4 = 2 \cdot (- 2)$ ✔; (c) $det = 0 = 0 \cdot 4$ ✔. Traces: (a) $4 = 1 + 3$ ✔, (c) $4 = 0 + 4$ ✔.

Figure s03 (below). $h = (x + y)^{2}$ ka ek contour map. Orange dashed line flat valley $x + y = 0$ hai (zero-eigenvalue direction, jahan $h = 0$ poori jagah); magenta arrow eigenvalue- $4$ direction mein uphill point karta hai jahan curvature positive hai. Har jagah convex, lekin dashed line ke along flat — hence strictly convex nahi.

Worked example Ex 6 — Cell F · Combination rules (kaun se operations convexity preserve karte hain)

Statement. $f_{1} (x) = x^{2}$ (convex) aur $f_{2} (x) = e^{x}$ (convex) diye gaye hain, decide karo: (a) kya $3 f_{1} + 5 f_{2}$ convex hai? (b) kya $f_{1} - f_{2}$ necessarily convex hai? (c) kya $max {f_{1} (x), f_{2} (x)}$ convex hai?

Forecast: exactly ek fail ho sakta hai. Kaun sa operation safe nahi hai?

(a) Nonnegative weighted sum. Convex $+$ convex, weights $3, 5 \geq 0$ ke saath, convex hai: chords add hote hain, aur nonnegative constant se scale karna " $\leq$ " preserve karta hai. Toh $3 f_{1} + 5 f_{2}$ is convex. Yeh step kyun? Yahi parent note ka safe rule hai: $\sum α_{i} f_{i}$ convex jab saare $α_{i} \geq 0$ hon.
(b) Difference. Convex $-$ convex $=$ convex $+$ concave, jo kuch bhi ho sakta hai. Concretely $f_{1} - f_{2}$ ka second derivative $2 - e^{x}$ hai, jo $x > lo g 2$ hote hi negative ho jaata hai. Toh yeh not convex hai. Yeh step kyun? Subtraction ek negative weight smuggle kar deta hai, jo exactly wahi hai jo safe rule forbid karta hai — yahi parent ki Mistake 3 hai.
(c) Pointwise maximum. Page-top definition se yaad karo ki kisi function ka epigraph uske graph ke upar ya uspe sab kuch hota hai, $epi (f) = {(x, t) : t \geq f (x)}$ , aur $f$ convex hai iff uska epigraph ek convex set hai. Ab $max {f_{1}, f_{2}}$ ka epigraph exactly ${(x, t) : t \geq f_{1} (x) and t \geq f_{2} (x)} = epi (f_{1}) \cap epi (f_{2})$ hai — do convex sets ka intersection, jo convex hai (parent note). Toh $max {x^{2}, e^{x}}$ is convex. Yeh step kyun? "Max = intersection of epigraphs" ek function claim ko us set fact mein badal deta hai jo hum pehle hi prove kar chuke hain.

Verify: (b) $x = 2$ pe: $f_{1}^{''} - f_{2}^{''} = 2 - e^{2} \approx 2 - 7.389 = - 5.389 < 0$ ✔ (convexity broken). (a) $x = 1$ pe: second derivative $3 \cdot 2 + 5 e \approx 6 + 13.59 > 0$ ✔.

Worked example Ex 7 — Cell G · Word problem: sabse sasti fence, guaranteed global

Statement. Ek farmer ko exactly $A = 100 m^{2}$ area ek rectangle mein enclose karna hai. Fence ki cost har side pe per metre same hai. Perimeter $P$ minimize karo. Dikhao ki problem ek change of variable ke baad convex hai, aur minimiser dhundho — phir argue karo ki yeh global optimum hai.

Forecast: sirf width ke function ke roop mein raw perimeter — kya yeh convex hai? Compute karne se pehle shape guess karo.

Setup karo. Width $w > 0$ , height $= A / w$ (area constraint). Perimeter $P (w) = 2 w + 2 A / w = 2 w + 200/ w$ . Yeh step kyun? Constraint ko substitution se eliminate karo taaki hum ek variable minimize kar sakein.
Convexity check karo. $P^{''} (w) = \frac{d}{d w} (2 - \frac{200}{w ^{2}}) = \frac{400}{w ^{3}}$ . $w > 0$ ke liye yeh $> 0$ hai, isliye $P$ domain $w > 0$ pe strictly convex hai. Yeh step kyun? (Convex) feasible set ${w > 0}$ pe convexity matlab koi bhi stationary point unique global minimiser hai — parent note ka theorem ("every local min is global"). Doosre traps ki chinta karne ki zaroorat nahi.
Minimize karo. $P^{'} (w) = 2 - 200/ w^{2} = 0 \Rightarrow w^{2} = 100 \Rightarrow w = 10$ set karo (lete hain $w > 0$ ). Phir height $= 100/10 = 10$ : ek square. Minimum perimeter $P (10) = 2 (10) + 200/10 = 40$ m. Yeh step kyun? Strictly convex 1-D function ke liye, $P^{'} = 0$ single global minimum pin kar deta hai. Gradient Descent se connection: convex objective matlab gradient methods yahan koi local-min trap ke bina land karte hain.
Uniqueness. Strict convexity $\Rightarrow$ at most ek minimiser, toh square the answer hai.

Verify: perimeter check $P (10) = 40$ . Ek non-square feasible point $w = 5$ (height $20$ ) se compare karo: $P (5) = 10 + 40 = 50 > 40$ ✔ aur $w = 20$ (height $5$ ): $P (20) = 40 + 10 = 50 > 40$ ✔ — dono bure, confirm karta hai ki $40$ min hai.

Worked example Ex 8 — Cell H · Exam twist: ek plausible-but-false claim

Statement. True ya false: "Agar $f$ aur $g$ dono convex hain, toh unka product $f g$ convex hai." Proof ya counterexample do.

Forecast: convex ka sum convex hota hai — kya yahi charm products pe bhi kaam karta hai? Kuch bhi trust mat karo.

Simple pieces se probe karo. $f (x) = x$ aur $g (x) = x$ lo. Dono linear hain, hence convex (aur concave). Unka product $f (x) g (x) = x^{2}$ hai — yahan convex. Yeh step kyun? Ek passing case ek universal claim prove nahi karta; yeh sirf disprove karne mein fail hota hai. Hume dhundhte rehna hoga.
Sign-changing factor try karo. $f (x) = x$ ( $R$ pe convex) aur $g (x) = x^{2}$ (convex) lo. Product $p (x) = x^{3}$ . Phir $p^{''} (x) = 6 x$ , jo $x < 0$ ke liye negative hai. Yeh step kyun? Deliberately test karo jahan ek factor negative ho jaata hai — wahan ek product curvature "flip" kar sakta hai.
Definition se confirm karo (sirf $p^{''}$ nahi). $x = - 2, y = 0, θ = \frac{1}{2}$ lo. Toh $p (θ x + (1 - θ) y) = p (- 1) = - 1$ , jabki $θ p (x) + (1 - θ) p (y) = \frac{1}{2} (- 8) + \frac{1}{2} (0) = - 4$ . Convexity requirement " $p (mid) \leq chord$ " padhti hai $- 1 \leq - 4$ , jo false hai — chord graph ke neeche jaati hai. Yeh step kyun? Ek watertight disproof mein chord definition ka ek explicit violating triple $(x, y, θ)$ exhibit karna chahiye, $p^{''} < 0$ signal ko back up karte hue.
FALSE conclude karo. Negative $p^{''}$ on $(- \infty, 0)$ aur explicit chord violation dono ke saath, claim is false: convex functions ka product convex hona zaruri nahi. (Bonus: products are convex agar dono factors convex, nonnegative, aur same direction mein monotone hon — naive claim teeno guards hata deta hai.)

Verify: $p^{''} (- 1) = 6 (- 1) = - 6 < 0$ ✔ (not convex). Chord violation $x = - 2, y = 0, θ = \frac{1}{2}$ pe: LHS $p (- 1) = - 1$ , RHS $\frac{1}{2} (- 8) + \frac{1}{2} (0) = - 4$ ; required $- 1 \leq - 4$ is false ✔ — non-convex confirm karta hai.

Examples matrix ko kaise tile karte hain

Recall Aage badhne se pehle self-check karo

Jab function mein corner ho toh kaun sa test use karte hain? ::: Definition (chord inequality), kyunki Hessian test ke liye twice-differentiability chahiye. Eigenvalues $0$ aur $4$ wala Hessian matlab function hai...? ::: Convex lekin not strictly — zero-eigenvalue direction mein flat (minima ki valley). Do convex functions ka product — hamesha convex? ::: Nahi — e.g. $x \cdot x^{2} = x^{3}$ $R$ pe convex nahi hai. Square sabse saste perimeter wala rectangle guaranteed global kyun hai? ::: $P (w) = 2 w + 200/ w$ $w > 0$ pe strictly convex hai, isliye uska unique stationary point global min hai. Strictly convex ki precise definition? ::: $f (θ x + (1 - θ) y) < θ f (x) + (1 - θ) f (y)$ for all $x \neq = y, θ \in (0, 1)$ — chord graph ke strictly upar except endpoints pe.

Connections

Parent topic — woh definitions jinhe yeh examples exercise karte hain.
Norms and Inner Products — triangle inequality jo Ex 1 aur Ex 4 ko power deti hai.
Positive Definite Matrices — Ex 5 ka Hessian eigenvalue test.
Gradient Descent — Ex 7 ka convex objective globally converge karta hai.
Linear Programming — half-spaces ke intersections ke roop mein polyhedra (Ex 6 ka intersection idea).
Jensen's Inequality — Ex 3/Ex 4 ki chord inequality averages tak generalize hoti hai.