Exercises — Convex optimization — convex sets, convex functions

(a) Convex. A filled ball is the model example — no dents, no holes. Any chord between two interior/boundary points stays inside (left panel of the figure). (b) NOT convex. The ring has a hole (the inner disk of radius $1$ is removed). A chord across the middle passes through the hole, leaving the set (right panel of the figure). (c) Convex. A half-plane $\{a^{\top }x\le b\}$ is convex: if $2x_1-y_1\le 3$ and $2x_2-y_2\le 3$, then mixing gives $2(\theta x_1+(1-\theta )x_2)-(\theta y_1+(1-\theta )y_2)\le \theta \cdot 3+(1-\theta )\cdot 3=3$. The inequality passes straight through the mix because $a^{\top }(\cdot )$ is linear. (d) NOT convex. Two isolated points: the midpoint $(0.5,0.5)$ is not in the set. To be convex, the whole segment must be present.

(a) Convex (and concave). $f^{\prime \prime }=0$. A straight line is the boundary case: chord equals the graph, so $\le$ holds with equality. (b) Concave. $f^{\prime \prime }=-2<0$; it is a downward bowl (right panel of the figure). Its negative $x^2$ is convex (left panel). (c) Convex. $|x|$ has a corner, not a Hessian at $0$, so use the definition + triangle inequality: $|\theta x+(1-\theta )y|\le \theta |x|+(1-\theta )|y|$. (d) Neither. $f^{\prime \prime }=-\cos x$ changes sign (positive on $(\frac{\pi }{2},\frac{3\pi }{2})$, negative on $(-\frac{\pi }{2},\frac{\pi }{2})$). Convexity requires $f^{\prime \prime }\ge 0$ everywhere.

What is the Hessian? For a function of several variables, the Hessian ${\nabla }^{2}f$ is the matrix of all second partial derivatives $[{\partial }^{2}f/\partial x_i\partial x_j]$ — it records the curvature in every direction. In 1-D it collapses to the single number $f^{\prime \prime }(x)$. Second-order tool — WHY: the Hessian test says convex $⟺f^{\prime \prime }\ge 0$ everywhere, because $f^{\prime \prime }$ measures how the tangent-slope changes; if the slope only increases, the graph curls upward and stays above its tangents. Compute: $f^{\prime }(x)=4x^3$, $f^{\prime \prime }(x)=12x^2\ge 0$ for all $x$. So $f$ is convex. ✔ Strictly convex? $f^{\prime \prime }(0)=0$, so the sufficient condition "$f^{\prime \prime }>0$ everywhere" fails at $x=0$. But strict convexity is defined by the chord inequality with strict "$<$", which $x^4$ satisfies (its graph never contains a straight segment). So $x^4$ is strictly convex despite $f^{\prime \prime }(0)=0$: "$f^{\prime \prime }>0$ everywhere" is sufficient, not necessary.

WHY the Hessian: in higher dimensions "curves upward" becomes "the matrix of second derivatives (the Hessian, defined in L2.1) is positive semidefinite" (see Positive Definite Matrices). We test ${\nabla }^{2}f⪰0$. ${\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).$ A symmetric $2\times 2$ matrix is positive semidefinite iff its trace $\ge 0$ and determinant $\ge 0$. Trace $=4>0$; determinant $=2\cdot 2-1\cdot 1=3>0$. Both eigenvalues positive, so ${\nabla }^{2}f\succ 0$. Hence $f$ is strictly convex. ✔

Reminder — epigraph. The epigraph of $f$ is the set of all points on or above its graph: $\text{epi}(f)=\{(x,t):t\ge f(x)\}$. A key fact (from the parent note) is that $f$ is convex iff $\text{epi}(f)$ is a convex set. We use this in part (c). (a) Convex. Nonnegative-weighted sums of convex functions are convex: add the chord inequalities, weights $\ge 0$ keep the direction. $3f+5g$ qualifies. (b) NOT guaranteed. $-g$ is concave; convex + concave can be anything. Example: $f=x^2$, $g=2x^2$ gives $f-g=-x^2$ (concave). So no. (c) Convex. The pointwise maximum of convex functions is convex. Reason via epigraphs: a point $(x,t)$ lies on or above both graphs exactly when $t\ge \max \{f(x),g(x)\}$, so $\text{epi}(\max \{f,g\})=\text{epi}(f)\cap \text{epi}(g)$. The intersection of two convex sets is convex, hence $\max \{f,g\}$ is convex. (d) NOT guaranteed. The product of two convex functions need not be convex. Take $f(x)=x^2$ (convex) and $g(x)=e^{-x}$ (convex, since $g^{\prime \prime }=e^{-x}>0$). Their product $h(x)=x^2{e}^{-x}$ has $h^{\prime \prime }(x)=e^{-x}(x^2-4x+2)$, which is negative for $x$ between the roots $2-\sqrt{2}\approx 0.586$ and $2+\sqrt{2}\approx 3.414$. So $h$ is concave on that interval — the product is not convex on $\mathbb{R}$. No general guarantee.

Each row of $Ax\le b$ is one inequality $a_i^{\top }x\le b_i$ — a half-space, which is convex (L1.1c). The full feasible set is the intersection of all these half-spaces. Since intersection preserves convexity (chord in each $\Rightarrow$ chord in all $\Rightarrow$ chord in the intersection), the polyhedron is convex. This is exactly why Linear Programming optimizes over convex regions. The triangle below is the intersection of three half-planes $x\ge 0$, $y\ge 0$, $x+y\le 1$ — any two points inside, the segment stays inside.

Let $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.$ The $p_i$ are like probabilities (positive, summing to 1). Second derivatives give the Hessian ${\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).$ Since $p_1+p_2=1$ we have $1-p_1=p_2$ and $1-p_2=p_1$, so ${\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$. Both eigenvalues ($0$ and $2p_1{p}_2$) are $\ge 0$, so ${\nabla }^{2}f⪰0$. Hence log-sum-exp is convex (not strictly — the eigenvalue $0$ along direction $(1,1)$ reflects that adding a constant to all inputs shifts $f$ linearly). ✔

Idea: group two points, then merge the third. Assume ${\lambda }_3<1$ (else trivial). Write ${\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.$ The inner weights $\frac{{\lambda }_1}{1-{\lambda }_3}+\frac{{\lambda }_2}{1-{\lambda }_3}=\frac{{\lambda }_1+{\lambda }_2}{1-{\lambda }_3}=1$, so $y$ is a genuine two-point convex combination. Step 1 (outer split): apply two-point convexity to $y$ and $x_3$ with dial $\theta =1-{\lambda }_3$: $f(\sum {\lambda }_i{x}_i)\le (1-{\lambda }_3)f(y)+{\lambda }_{3}f(x_3).$ Step 2 (inner split): apply two-point convexity again to $y$: $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; the $(1-{\lambda }_3)$ cancels the denominators: $f(\sum {\lambda }_i{x}_i)\le {\lambda }_{1}f(x_1)+{\lambda }_{2}f(x_2)+{\lambda }_{3}f(x_3).■$ The same "peel off one point, renormalize the rest" induction gives all $n$.

Global part. Suppose $x^{\star }$ is a local min but some $y\in C$ has $f(y)<f(x^{\star })$. Form the segment point $z_{\theta }=\theta y+(1-\theta )x^{\star }$. Because $C$ is convex, $z_{\theta }\in C$ for all $\theta \in [0,1]$. Convexity gives $f(z_{\theta })\le \theta f(y)+(1-\theta )f(x^{\star })=f(x^{\star })+\theta (f(y)-f(x^{\star }))<f(x^{\star })$ for every $\theta \in (0,1]$, since $f(y)-f(x^{\star })<0$. But as $\theta \to 0^{+}$, $z_{\theta }\to x^{\star }$, so points arbitrarily close to $x^{\star }$ have strictly smaller value — contradicting that $x^{\star }$ is a local minimum. Hence no such $y$ exists: $x^{\star }$ is global. ∎ Uniqueness under strict convexity. Suppose two distinct global minimizers $a\ne b$ with $f(a)=f(b)=m$. Take the midpoint $\theta =\frac{1}{2}$; strict convexity gives $f\left(\frac{a+b}{2}\right)<\frac{1}{2}f(a)+\frac{1}{2}f(b)=m,$ a point with value below the supposed minimum — impossible. So the minimizer is unique. ∎

Setup. $f$ is convex (Hessian $=2I\succ 0$); the constraint $\{x+y=1\}$ is a line, hence a convex set. Convex objective over convex feasible set ⇒ any stationary point is the global minimum (L5.1), and KKT/Lagrange conditions are sufficient, not merely necessary.

(i) Substitution. Put $y=1-x$: minimize $g(x)=x^2+(1-x{)}^2=2x^2-2x+1$. Then $g^{\prime }(x)=4x-2=0\Rightarrow x=\frac{1}{2}$, so $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$, so $x=y=\frac{1}{2}$, matching (i). Geometrically the gradient $\nabla f=(2x,2y)$ must be perpendicular to the line, forcing $x=y$ — the closest point of the line to the origin.

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

Convex set = segment stays inside ::: filled region, no dents/holes. Convex function test (twice-diff) ::: ${\nabla }^{2}f⪰0$ everywhere. Local min of convex $f$ over convex $C$ ::: is automatically global. Pointwise max of convex functions ::: convex; pointwise min ::: generally not.