Exercises — Convex optimization — convex sets, convex functions

(a) Convex. Filled ball model example hai — koi dent nahi, koi hole nahi. Koi bhi chord do interior/boundary points ke beech andar rehti hai (figure ka left panel). (b) NOT convex. Ring mein ek hole hai (radius $1$ wali inner disk nikaali gayi hai). Beech se guzarne wali chord hole mein se jaati hai, set se bahar (figure ka right panel). (c) Convex. Half-plane $\{a^{\top }x\le b\}$ convex hota hai: agar $2x_1-y_1\le 3$ aur $2x_2-y_2\le 3$ ho, toh mix karne par $2(\theta x_1+(1-\theta )x_2)-(\theta y_1+(1-\theta )y_2)\le \theta \cdot 3+(1-\theta )\cdot 3=3$ milta hai. Inequality mix ke through seedha pass ho jaati hai kyunki $a^{\top }(\cdot )$ linear hai. (d) NOT convex. Do isolated points: midpoint $(0.5,0.5)$ set mein nahi hai. Convex hone ke liye poora segment present hona chahiye.

(a) Convex (aur concave bhi). $f^{\prime \prime }=0$. Straight line boundary case hai: chord graph ke barabar hoti hai, isliye $\le$ equality ke saath hold karta hai. (b) Concave. $f^{\prime \prime }=-2<0$; yeh ek downward bowl hai (figure ka right panel). Iska negative $x^2$ convex hai (figure ka left panel). (c) Convex. $|x|$ mein $0$ par corner hai, Hessian nahi, isliye definition + triangle inequality use karo: $|\theta x+(1-\theta )y|\le \theta |x|+(1-\theta )|y|$. (d) Neither. $f^{\prime \prime }=-\cos x$ sign change karta hai (positive on $(\frac{\pi }{2},\frac{3\pi }{2})$, negative on $(-\frac{\pi }{2},\frac{\pi }{2})$). Convexity ke liye $f^{\prime \prime }\ge 0$ har jagah chahiye.

Hessian kya hai? Kai variables ke function ke liye, Hessian ${\nabla }^{2}f$ woh matrix hai jisme saare second partial derivatives $[{\partial }^{2}f/\partial x_i\partial x_j]$ hain — yeh har direction mein curvature record karta hai. 1-D mein yeh single number $f^{\prime \prime }(x)$ ban jaata hai. Second-order tool — KYUN: Hessian test kehta hai convex $⟺f^{\prime \prime }\ge 0$ har jagah, kyunki $f^{\prime \prime }$ measure karta hai ki tangent-slope kaise change hoti hai; agar slope sirf increase hoti hai, toh graph upar curl karta hai aur apne tangents ke upar rehta hai. Compute karo: $f^{\prime }(x)=4x^3$, $f^{\prime \prime }(x)=12x^2\ge 0$ for all $x$. Isliye $f$ convex hai. ✔ Strictly convex? $f^{\prime \prime }(0)=0$, isliye sufficient condition "$f^{\prime \prime }>0$ everywhere" $x=0$ par fail karti hai. Lekin strict convexity strict "$<$" chord inequality se define hoti hai, jo $x^4$ satisfy karta hai (iska graph kabhi straight segment nahi contain karta). Isliye $x^4$ strictly convex hai $f^{\prime \prime }(0)=0$ hone ke bawajood: "$f^{\prime \prime }>0$ everywhere" sufficient hai, necessary nahi.

KYUN Hessian: higher dimensions mein "upar curl karta hai" ban jaata hai "second derivatives ki matrix (Hessian, L2.1 mein defined) positive semidefinite hai" (dekho Positive Definite Matrices). Hum ${\nabla }^{2}f⪰0$ test karte hain. ${\nabla }^{2}f=\left(\begin{array}{cc}{f}_{xx}& f_{xy}\\ f_{yx}& f_{yy}\end{array}\right)=\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right).$ Ek symmetric $2\times 2$ matrix positive semidefinite hai iff uska trace $\ge 0$ aur determinant $\ge 0$. Trace $=4>0$; determinant $=2\cdot 2-1\cdot 1=3>0$. Dono eigenvalues positive hain, isliye ${\nabla }^{2}f\succ 0$. Hence $f$ strictly convex hai. ✔

Reminder — epigraph. $f$ ka epigraph woh set hai jisme saare points graph par ya uske upar hain: $\text{epi}(f)=\{(x,t):t\ge f(x)\}$. Parent note se ek key fact: $f$ convex hai iff $\text{epi}(f)$ ek convex set hai. Hum ise part (c) mein use karenge. (a) Convex. Convex functions ke nonnegative-weighted sums convex hote hain: chord inequalities add karo, weights $\ge 0$ direction maintain karte hain. $3f+5g$ qualify karta hai. (b) NOT guaranteed. $-g$ concave hai; convex + concave kuch bhi ho sakta hai. Example: $f=x^2$, $g=2x^2$ deta hai $f-g=-x^2$ (concave). Isliye nahi. (c) Convex. Convex functions ka pointwise maximum convex hota hai. Reason via epigraphs: ek point $(x,t)$ dono graphs par ya upar hota hai exactly jab $t\ge \max \{f(x),g(x)\}$, isliye $\text{epi}(\max \{f,g\})=\text{epi}(f)\cap \text{epi}(g)$. Do convex sets ka intersection convex hota hai, isliye $\max \{f,g\}$ convex hai. (d) NOT guaranteed. Do convex functions ka product necessarily convex nahi hota. Lo $f(x)=x^2$ (convex) aur $g(x)=e^{-x}$ (convex, kyunki $g^{\prime \prime }=e^{-x}>0$). Unka product $h(x)=x^2{e}^{-x}$ mein $h^{\prime \prime }(x)=e^{-x}(x^2-4x+2)$ hai, jo roots $2-\sqrt{2}\approx 0.586$ aur $2+\sqrt{2}\approx 3.414$ ke beech $x$ ke liye negative hai. Isliye $h$ us interval par concave hai — product $\mathbb{R}$ par convex nahi hai. Koi general guarantee nahi.

$Ax\le b$ ki har row ek inequality $a_i^{\top }x\le b_i$ hai — ek half-space, jo convex hai (L1.1c). Poori feasible set in saare half-spaces ka intersection hai. Kyunki intersection convexity preserve karta hai (chord har ek mein $\Rightarrow$ chord sabme $\Rightarrow$ chord intersection mein), polyhedron convex hai. Isliye hi Linear Programming convex regions par optimize karta hai. Neeche wala triangle teen half-planes $x\ge 0$, $y\ge 0$, $x+y\le 1$ ka intersection hai — andar ke koi bhi do points, segment andar hi rehta hai.

Maano $S=e^{x_1}+e^{x_2}$. First derivatives: $\frac{\partial f}{\partial x_i}=\frac{e^{x_i}}{S}=:p_i,p_1+p_2=1,p_i>0.$ $p_i$ probabilities jaise hain (positive, sum 1). Second derivatives se Hessian milta hai: ${\nabla }^{2}f=\left(\begin{array}{cc}{p}_1(1-p_1)& -p_1{p}_2\\ -p_1{p}_2& p_2(1-p_2)\end{array}\right).$ Kyunki $p_1+p_2=1$ hai, $1-p_1=p_2$ aur $1-p_2=p_1$ hai, isliye ${\nabla }^{2}f=\left(\begin{array}{cc}{p}_1{p}_2& -p_1{p}_2\\ -p_1{p}_2& p_1{p}_2\end{array}\right)=p_1{p}_2\left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right).$ PSD check: trace $=2p_1{p}_2\ge 0$, determinant $=(p_1{p}_2{)}^2-(p_1{p}_2{)}^2=0\ge 0$. Dono eigenvalues ($0$ aur $2p_1{p}_2$) $\ge 0$ hain, isliye ${\nabla }^{2}f⪰0$. Hence log-sum-exp convex hai (strictly nahi — direction $(1,1)$ mein eigenvalue $0$ reflect karta hai ki saare inputs mein constant add karna $f$ ko linearly shift karta hai). ✔

Idea: do points group karo, phir teesra merge karo. Maano ${\lambda }_3<1$ (warna trivial). Likho ${\sum }_{i=1}^3{\lambda }_i{x}_i=(1-{\lambda }_3)\underset{=:y}{\underbrace{\left(\frac{{\lambda }_1}{1-{\lambda }_3}{x}_1+\frac{{\lambda }_2}{1-{\lambda }_3}{x}_2\right)}}+{\lambda }_3{x}_3.$ Inner weights $\frac{{\lambda }_1}{1-{\lambda }_3}+\frac{{\lambda }_2}{1-{\lambda }_3}=\frac{{\lambda }_1+{\lambda }_2}{1-{\lambda }_3}=1$, isliye $y$ ek genuine two-point convex combination hai. Step 1 (outer split): $y$ aur $x_3$ par dial $\theta =1-{\lambda }_3$ ke saath two-point convexity apply karo: $f(\sum {\lambda }_i{x}_i)\le (1-{\lambda }_3)f(y)+{\lambda }_{3}f(x_3).$ Step 2 (inner split): $y$ par phir se two-point convexity apply karo: $f(y)\le \frac{{\lambda }_1}{1-{\lambda }_3}f(x_1)+\frac{{\lambda }_2}{1-{\lambda }_3}f(x_2).$ Step 3 (substitute): plug in karo; $(1-{\lambda }_3)$ denominators cancel kar deta hai: $f(\sum {\lambda }_i{x}_i)\le {\lambda }_{1}f(x_1)+{\lambda }_{2}f(x_2)+{\lambda }_{3}f(x_3).■$ Yehi "ek point peel off karo, baaki renormalize karo" induction saare $n$ ke liye deta hai.

Global part. Maano $x^{\star }$ local min hai lekin koi $y\in C$ hai jiske liye $f(y)<f(x^{\star })$. Segment point $z_{\theta }=\theta y+(1-\theta )x^{\star }$ banao. Kyunki $C$ convex hai, $z_{\theta }\in C$ for all $\theta \in [0,1]$. Convexity deta hai: $f(z_{\theta })\le \theta f(y)+(1-\theta )f(x^{\star })=f(x^{\star })+\theta (f(y)-f(x^{\star }))<f(x^{\star })$ har $\theta \in (0,1]$ ke liye, kyunki $f(y)-f(x^{\star })<0$. Lekin jab $\theta \to 0^{+}$, $z_{\theta }\to x^{\star }$, isliye $x^{\star }$ ke arbitrarily close points ka value strictly chhota hoga — yeh contradict karta hai ki $x^{\star }$ local minimum hai. Isliye aisa koi $y$ exist nahi karta: $x^{\star }$ global hai. ∎ Strictly convexity ke under uniqueness. Maano do distinct global minimizers $a\ne b$ hain jiske liye $f(a)=f(b)=m$. Midpoint $\theta =\frac{1}{2}$ lo; strict convexity deta hai: $f\left(\frac{a+b}{2}\right)<\frac{1}{2}f(a)+\frac{1}{2}f(b)=m,$ ek aisa point jiska value supposed minimum se neeche hai — impossible. Isliye minimizer unique hai. ∎

Setup. $f$ convex hai (Hessian $=2I\succ 0$); constraint $\{x+y=1\}$ ek line hai, isliye convex set. Convex objective over convex feasible set $\Rightarrow$ koi bhi stationary point global minimum hai (L5.1), aur KKT/Lagrange conditions sufficient hain, sirf necessary nahi.

(i) Substitution. $y=1-x$ rakho: $g(x)=x^2+(1-x{)}^2=2x^2-2x+1$ minimize karo. Phir $g^{\prime }(x)=4x-2=0\Rightarrow x=\frac{1}{2}$, isliye $y=\frac{1}{2}$. Value $f=\frac{1}{4}+\frac{1}{4}=\frac{1}{2}$.

(ii) Lagrange. $L=x^2+y^2-\lambda (x+y-1)$. Stationarity: ${\partial }_{x}L=2x-\lambda =0,{\partial }_{y}L=2y-\lambda =0\Rightarrow x=y=\frac{\lambda }{2}.$ Constraint $x+y=1\Rightarrow \lambda =1$, isliye $x=y=\frac{1}{2}$, (i) se match karta hai. Geometrically gradient $\nabla f=(2x,2y)$ line ke perpendicular hona chahiye, jo $x=y$ force karta hai — line ka origin ke sabse close point.

Answer: minimizer $(\frac{1}{2},\frac{1}{2})$, minimum value $\boxed{\frac{1}{2}}$.

Convex set = segment andar rehta hai ::: filled region, koi dents/holes nahi. Convex function test (twice-diff) ::: ${\nabla }^{2}f⪰0$ har jagah. Convex $f$ ka local min over convex $C$ ::: automatically global hota hai. Pointwise max of convex functions ::: convex; pointwise min ::: generally nahi.