Convex optimization — convex sets, convex functions: Question bank

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

True or false — justify karo

Inme se har ek ka jawab ek reason ke saath dena hai, sirf verdict nahi. Verdict toh sasta part hai.

Empty set

\emptyset

convex hai.

True — definition "har ek pair

x, y

ke liye segment andar rehta hai" vacuously satisfy hoti hai jab test karne ke liye koi pair hi nahi; violate karne ke liye kuch hai hi nahi.

Ek single point

{p}

convex hai.

True — sirf ek hi pair hai

x = y = p

, aur

θ p + (1 - θ) p = p

set mein rehta hai saare

θ

ke liye; ek degenerate segment phir bhi segment hai.

Do convex sets ka union hamesha convex hota hai.

False — do disjoint disks lo; ek mein ek point aur doosre mein ek point ko jodne wala segment khali gap cross karta hai. (Intersection preserve hota hai, union nahi.)

Agar

f

convex hai toh

- f

convex hai.

False —

- f

concave hai; uski chords graph ke neeche rehti hain. Sirf woh functions jo convex aur concave dono hain woh affine hain

a^{⊤} x + b

Ek straight line

f (x) = m x + c

convex hai.

True — chord graph ke barabar hai, toh "chord on or above graph" equality ke saath hold karta hai; equivalently

f^{''} = 0 \geq 0

. Yeh simultaneously concave bhi hai.

Set

{x : ∥ x ∥ = 1}

(sphere shell) convex hai.

False — do antipodal points lo; unka midpoint

0

hai, jiska norm

0 \neq = 1

hai, toh segment shell se bahar chala jaata hai. Sirf filled ball

∥ x ∥ \leq 1

convex hai.

Agar

f

aur

g

dono convex hain, toh

f + g

convex hai.

True — do chord inequalities ko term by term add karo; do "bowls" ka sum phir bhi ek bowl hai. Zyada generally koi bhi

\sum α_{i} f_{i}

jahan

α_{i} \geq 0

convex rehta hai.

Do convex functions ka maximum

max (f, g)

convex hai.

True — uska epigraph do epigraphs ka intersection hai (ek point

max (f, g)

ke upar hai iff woh dono ke upar hai), aur intersection convexity preserve karta hai. (Contrast:

min

of convex functions need not be convex.)

f (x) = x^{4}

strictly convex hai even though

f^{''} (0) = 0

True — strict convexity chord inequality hai strict "

<

" ke saath, jo

x^{4}

satisfy karta hai;

f^{''} > 0

sab jagah strict convexity ke liye sufficient hai par necessary nahi.

Har convex function differentiable hota hai.

False —

f (x) = ∣ x ∣

convex hai (triangle inequality) par

0

par kink hai. Convexity domain ke interior par continuity force karta hai, par differentiability nahi.

Spot the error

Neeche har statement mein ek flaw hai. Use naam do.

"Circle round dikhta hai bina corners ke, toh woh convex hona chahiye."

Error smoothness aur convexity ko confuse karta hai: convexity filled region aur uske chords ke baare mein hai, corners ki absence ke baare mein nahi. Ek square (saare corners) convex hai; ek circle rim (koi corners nahi) convex nahi hai.

f

convex hai, toh usse

f^{''} > 0

sab jagah chahiye."

Convexity sirf

f^{''} \geq 0

maangti hai; weak inequality essential hai. Lines (

f^{''} = 0

) convex hain, aur

x^{4}

strictly convex hai despite

f^{''} (0) = 0

"Convex plus concave kuch achha deta hai, symmetry se."

Aisi koi guarantee nahi hai —

f

convex

+

g

concave kuch bhi ho sakta hai. Convexity sirf convex functions ke nonnegative combinations ke under preserve hoti hai, mixed curvatures se nahi.

"Kyunki gradient descent convex objectives par kaam karta hai, koi bhi step size global minimum tak pahunch jaayegi."

Convexity local-minimum traps hatati hai par convergence khud guarantee nahi karti; tumhe phir bhi sensible step-size rule aur smoothness (Lipschitz-gradient) assumptions chahiye. Dekho Gradient Descent.

"Set

{x : ∥ x ∥ \geq 1}

(ball ke bahar) convex hai kyunki norms convex hain."

Ek convex function

∥ x ∥

convex sublevel sets

{∥ x ∥ \leq r}

deta hai, superlevel sets nahi. Exterior fail karta hai: shell par do opposite points jodo aur segment andar dip karta hai jahan

∥ x ∥ < 1

"KKT conditions solve ho gayi, toh maine minimum dhundh liya — hamesha."

General mein KKT sirf necessary hai. Yeh global minimum ke liye sufficient tab banta hai jab problem convex ho; warna ek KKT point saddle ya max ho sakta hai. Dekho Lagrange Multipliers and KKT Conditions.

"Hessian mere point par positive definite hai, toh poora function convex hai."

Local Hessian check convexity certify karta hai sirf tab jab

\nabla^{2} f ⪰ 0

domain par har jagah ho, ek point par nahi. Convexity ek global property hai. Dekho Positive Definite Matrices.

Why questions

Convexity "local minimum = global minimum" true kyun banati hai, ek sentence mein?

Agar koi door point lower hota, toh usse jaane wala segment (convex set mein rehta hua), chord inequality se, "local" min se neeche nearby points produce karta — locality ko contradict karta; toh koi lower point exist nahi kar sakta.

First-order condition

f (y) \geq f (x) + \nabla f (x)^{⊤} (y - x)

\nabla f = 0 \Rightarrow

global min ke peeche "engine" kyun hai?

Yeh kehta hai graph har tangent ke upar hai; agar

\nabla f (x) = 0

toh tangent height

f (x)

par flat hai, toh

f (y) \geq f (x)

saare

y

ke liye — yeh exactly global minimum hai.

Ek convex function ka domain khud ek convex set kyun hona chahiye?

Definition require karta hai chord inequality

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

domain mein har

x, y

ke liye hold kare, toh point

θ x + (1 - θ) y

domain mein hona chahiye (warna

f

wahan defined hi nahi hai) — aur "domain mein

θ x + (1 - θ) y

saare

x, y, θ

ke liye" exactly yeh statement hai ki domain convex hai.

Har norm ek convex function kyun hai?

Triangle inequality plus absolute homogeneity dete hain

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

, jo khud chord inequality hai. Dekho Norms and Inner Products.

Jensen's inequality sirf convexity definition "grown up" kyun hai?

Do-point chord inequality kisi bhi weighted average tak extend hoti hai aur phir expectations tak, deti hai

f (E [X]) \leq E [f (X)]

— definition apply ki gayi probability-weighted convex combination par. Dekho Jensen's Inequality.

Half-spaces ka intersection (ek polyhedron) hamesha convex kyun hota hai?

Har half-space convex hai, aur intersection convexity preserve karta hai, toh koi bhi

{x : A x \leq b}

convex hai — yeh exactly linear program ka feasible region hai. Dekho Linear Programming.

Hum care kyun karte hain ki epigraph convex hai na ki sirf graph?

Graph (ek surface) khud kabhi convex set nahi hota; convexity ko "graph ke upar/par region convex hai" ke roop mein recast karna humein saare set-based tools (intersection, half-spaces) ko functions par reuse karne deta hai.

Edge cases

Convex combination

θ x + (1 - θ) y

kya hoti hai jab

x = y

Yeh collapse hokar single point

x

ban jaati hai har

θ

ke liye — ek degenerate segment; isi liye singletons convexity test trivially pass karte hain.

Kya ek set convex hai agar segment condition sirf

θ = \frac{1}{2}

(midpoints) ke liye hold kare?

Generally nahi — yeh "midpoint convexity" poori convexity mein upgrade hoti hai sirf ek extra topological hypothesis ke under, jaise set real vector space mein closed (ya locally bounded) ho; iske bina ek pathological midpoint-convex set convex hone mein fail ho sakta hai, toh true definition saare

θ \in [0, 1]

maangti hai.

Function

f (x) = 0

(constant) convex hai, concave hai, ya kuch nahi?

Dono — ek constant affine hai, uska chord equality ke saath graph ke barabar hai, convex (

\leq

) aur concave (

\geq

) dono satisfy karta hai simultaneously; yeh convex hai par strictly convex nahi.

Kya ek strictly convex function ke ek se zyada global minimizers ho sakte hain?

Nahi — agar do distinct points dono minimum attain karte, toh unke midpoint par strict chord inequality strictly lower value deti, ek contradiction; toh minimizer, agar exist karta hai, unique hai.

Kya ek convex function hamesha apna minimum attain karta hai?

Zaruri nahi —

f (x) = e^{x}

R

par strictly convex hai par uska infimum

0

kabhi reach nahi hota; tumhe minimizer exist hone ki guarantee ke liye closed bounded (compact) domain ya coercivity chahiye.

Kya poora space

R^{n}

convex hai?

Haan —

R^{n}

ke do points ke beech koi bhi segment phir bhi

R^{n}

mein hai; yeh sabse bada convex set hai aur "no constraints" feasible region hai.

∥ x ∥_{p}

ki convexity ka kya hota hai jab

p

1 se neeche jaata hai?

0 < p < 1

ke liye function

∥ x ∥_{p}

triangle inequality fail karta hai, toh yeh norm nahi hai aur uska unit ball non-convex hai (star/pinched shape); ball ki convexity ke liye

p \geq 1

chahiye.

Recall Ek-line self-test

Agar tum "local = global kyun," "tangent neeche kyun rehti hai," aur "circle rim convex kyun nahi" — teeno ka jawab ek poori sentence mein de sakte ho, toh tum yeh topic own karte ho.

Connections

Linear Programming — half-spaces ke intersections ke roop mein polyhedra.
Gradient Descent — convexity traps hatati hai par step-size/smoothness care ki zaroorat nahi hatati.
Lagrange Multipliers and KKT Conditions — convexity ke under KKT sufficient hai.
Positive Definite Matrices — global Hessian test.
Jensen's Inequality — expectations ke liye convexity.
Norms and Inner Products — norms convex hain.