Homework 4

Due: Nov. 2, 14:00:00

First and second order conditions for convexity

1. We claimed that a function $f(x)$$f(x)$ differentiable on an open convex set is a strictly convex function if and only if $f(y)>f(x)+\mathrm{\nabla }f(x{)}^T\cdot (y-x)$$f(y)>f(x)+\nabla f(x)^T\cdot(y-x)$ for all $x\ne y$$x\neq y$. The "$⟸$$\impliedby$" direction is easy. We now prove the "$⟹$$\implies$" direction. Suppose $f(x)$$f(x)$ is a differentiable and strictly convex function. Fix $x\ne y$$x\neq y$, and let $d=y-x$$d = y-x$.

   • Show that for all $0<\alpha <1$$0<\alpha<1$, we have $\frac{f(x+\alpha d)-f(x)}{\alpha }<f(y)-f(x)$$\frac{f(x+\alpha d)-f(x)}{\alpha} < f(y)-f(x)$.
   • For all $0<\alpha <\beta <1$$0<\alpha < \beta < 1$, show that $\frac{f(x+\alpha d)-f(x)}{\alpha }<\frac{f(x+\beta d)-f(x)}{\beta }$$\frac{f(x+\alpha d)-f(x)}{\alpha} < \frac{f(x+\beta d)-f(x)}{\beta}$.
   • Use above results to show that $f(y)>f(x)+\mathrm{\nabla }f(x{)}^T\cdot (y-x)$$f(y)>f(x)+\nabla f(x)^T\cdot(y-x)$.

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

   • Show that $f(x)=x^4$$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$$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$$x \in \mathbb{R}^2$ such that ${\mathrm{\nabla }}^{2}f(x)\nsucc 0$$\nabla^2 f(x)\not\succ0$ (i.e., there exists $v\ne \mathbf{0}\in {\mathbb{R}}^2$$v\neq \mathbf{0}\in \mathbb{R}^2$ such that $v^T{\mathrm{\nabla }}^{2}f(x)v\le 0$$v^T \nabla^2f(x) v \leq 0$).

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

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

4. We've showed that any norm is a convex function. In particular, for all $p\ge 1$$p\geq 1$, $L_p$$L_p$-norm defined by $\Vert x\Vert \triangleq (\sum _{i=1}^n{\left|x_i\right|}^p{)}^{1/p}$$\lVert x\rVert\triangleq (\sum_{i=1}^n \abs{x_i}^p)^{1/p}$ is a convex function on ${\mathbb{R}}^n$$\mathbb{R}^n$. Now we consider the case where $0<p<1$$0<p<1$.

   Is the function $f(x)=(\sum _{i=1}^n{\left|x_i\right|}^p{)}^{1/p}$$f(x) = (\sum_{i=1}^n \abs{x_i}^p)^{1/p}$ convex or concave? Prove your conclusion.

Convexity-preserving operations

5. Let $f(x)=\log \left(\sum _{i=1}^n{e}^{w_i^T\cdot x+b_i}\right)$$f(x) = \log (\sum_{i=1}^n e^{w_i^T\cdot x+b_i})$ where $w_i,x\in {\mathbb{R}}^m$$w_i, x\in \mathbb{R}^m$ and $b_i\in \mathbb{R}$$b_i\in \mathbb{R}$. We are going to show that $f(x)$$f(x)$ is a convex function on ${\mathbb{R}}^m$$\mathbb{R}^m$.

   Let $g(y)=\log \left(\sum _{i=1}^n{e}^{y_i}\right)$$g(y) = \log (\sum_{i=1}^n e^{y_i})$ where $y\in {\mathbb{R}}^n$$y\in \mathbb{R}^n$.

   • Use Hölder's inequality to show that $g(\theta y_1+\overline{\theta }{y}_2)\le \theta g(y_1)+\overline{\theta }g(y_2)$$g(\theta y_1+\bar{\theta} y_2) \leq \theta g(y_1) +\bar{\theta} g(y_2)$ for all $\theta \in [0,1]$$\theta \in [0,1]$.
   • Use composition rules to verify the convexity of $f(x)$$f(x)$.

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

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

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

Optimization problems

7. Determine whether the following optimization problem is a convex optimization or not. Give your reasons.

   $\underset{x_1,x_2}{min}{x}_1^2+x_2^2-2x_1{x}_2+x_1+x_2$$\min_{x_1,x_2} x_1^2+x_2^2 -2 x_1x_2+x_1+x_2$

   subject to $(x_1-x_2{)}^2+4x_1{x}_2+e^{x_2-x_1}\le 0$$(x_1-x_2)^2+ 4x_1x_2 + e^{x_2-x_1} \leq 0$, and $5x_1-7x_2=0$$5x_1-7x_2=0$.

Questionnaire

• How long does it take you to do this homework?
• If $1$$1$ represents "very easy" and $10$$10$ represents "too hard", how difficult do you feel this homework is? (You can give different points for different problems.)