Homework 4

Deadline: Nov. 2, 22:00:00

First and second order conditions for convexity

1. The second-order condition tells us that a twice differentiable $f(x)$ is strictly convex if $f(x)$ has $\nabla^2 f(x) \succ 0$ for all $x\in \mathrm{dom} f$, but not vice versa. Here we verify two examples.

   • Show that $f(x) = x^4$ is a strictly convex function.
   • Show that $f:\mathbb{R}^2\to \mathbb{R}, f(x_1,x_2)=x_1^2+x_2^4$ is a strictly convex function, and there exists $x \in \mathbb{R}^2$ such that $\nabla^2 f(x)\not\succ0$ (i.e., there exists $v\neq \mathbf{0}\in \mathbb{R}^2$ such that $v^T \nabla^2f(x) v \leq 0$).

2. For each of the following functions determine whether it is convex, concave, or neither.

   • $f(x_1, x_2) = 1/(x_1x_2)$ on $\mathbb{R}_{>0}^2$.
   • $f(x_1, x_2) = x_1^2/(x_2+1)$ on $\mathbb{R}_{>0}^2$.
   • $f(x_1, x_2) = x_1^\alpha\cdot x_2^{1-\alpha}$ on $\mathbb{R}_{>0}^2$, where $0\leq \alpha \leq 1$.

3. We've showed that any norm is a convex function. In particular, for all $p\geq 1$, $L_p$-norm defined by $\lVert x\rVert_p \triangleq (\sum_{i=1}^n |x_i|^p)^{1/p}$ is a convex function on $\mathbb{R}^n$.

   Now we consider the case where $0<p<1$. Is the function $f(x) = (\sum_{i=1}^n |x_i|^p)^{1/p}$ convex or concave, or neither? Prove your conclusion.

Convexity-preserving operations

4. Let $f(x) = \sum_{i=1}^r |x|_{[i]}$ on $\mathbb{R}^n$, where $r\leq n$ is a fixed integer, $|x|$ denotes the vector with $|x|_i = |x_i|$, and $|x|_{[i]}$ is the $i$-th largest component of $|x|$. In other words, $|x|_{[1]}, |x|_{[2]}, \ldots, |x|_{[n]}$ are the absolute values of the components of $x$, sorted in nonincreasing order.

   Show that $f(x)$ is a convex function.

   (Hint: Express $f(x)$ as the pointwise maximum of a family of convex functions.)