We claimed that a function

differentiable on an open convex set is a$f(x)$ *strictly*convex function if and only if for all$f(y)>f(x)+\mathrm{\nabla}f(x{)}^{T}\cdot (y-x)$ . The "$x\ne y$ " direction is easy. We now prove the "$\phantom{\rule{0.278em}{0ex}}}\u27f8{\textstyle \phantom{\rule{0.278em}{0ex}}$ " direction. Suppose$\phantom{\rule{0.278em}{0ex}}}\u27f9{\textstyle \phantom{\rule{0.278em}{0ex}}$ is a differentiable and strictly convex function. Fix$f(x)$ , and let$x\ne y$ .$d=y-x$ - Show that for all
, we have$0<\alpha <1$ .$\frac{f(x+\alpha d)-f(x)}{\alpha}<f(y)-f(x)$ - For all
, show that$0<\alpha <\beta <1$ .$\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)$

- Show that for all
The second-order condition tells us that a twice differentiable

is$f(x)$ *strictly*convex if has$f(x)$ for all${\mathrm{\nabla}}^{2}f(x)\succ 0$ , but not vice versa. Here we verify two examples.$x\in \mathrm{dom}f$ - Show that
is a strictly convex function.$f(x)={x}^{4}$ - Show that
is a strictly convex function, and there exists$f:{\mathbb{R}}^{2}\to \mathbb{R},f({x}_{1},{x}_{2})={x}_{1}^{2}+{x}_{2}^{4}$ such that$x\in {\mathbb{R}}^{2}$ (i.e., there exists${\mathrm{\nabla}}^{2}f(x)\nsucc 0$ such that$v\ne \mathbf{0}\in {\mathbb{R}}^{2}$ ).${v}^{T}{\mathrm{\nabla}}^{2}f(x)v\le 0$

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

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

We've showed that any norm is a convex function. In particular, for all

,$p\ge 1$ -norm defined by${L}_{p}$ is a convex function on$\Vert x\Vert \triangleq (\sum _{i=1}^{n}{\left|{x}_{i}\right|}^{p}{)}^{1/p}$ . Now we consider the case where${\mathbb{R}}^{n}$ .$0<p<1$ Is the function

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

Let

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

where$g(y)=\mathrm{log}\left(\sum _{i=1}^{n}{e}^{{y}_{i}}\right)$ .$y\in {\mathbb{R}}^{n}$ - Use Hölder's inequality to show that
for all$g(\theta {y}_{1}+\overline{\theta}{y}_{2})\le \theta g({y}_{1})+\overline{\theta}g({y}_{2})$ .$\theta \in [0,1]$ - Use composition rules to verify the convexity of
.$f(x)$

- Use Hölder's inequality to show that
Let

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

is a convex function.$f(x)$ (Hint: Express

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

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}-2{x}_{1}{x}_{2}+{x}_{1}+{x}_{2}$ subject to

, and$({x}_{1}-{x}_{2}{)}^{2}+4{x}_{1}{x}_{2}+{e}^{{x}_{2}-{x}_{1}}\le 0$ .$5{x}_{1}-7{x}_{2}=0$

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