0

From Boyd & Vandenberghe's Convex Optimization, the second last example of 3.14 is as follows.


enter image description here


I am not able to follow why $h(z)$ would be convex. We can write it as $h(z) = (g(z))^{\frac1p}$, where

$$g(z) = \sum_{i=1}^k \max \{z_i, 0\}^p $$

I am able to follow why $g(z)$ is convex, but not able to follow why $h(z)$ would be too. I think trying to prove convexity from $g(z)$ is not a good idea as we are not considering the power of $p$ used in $g$.

user1953366
  • 191
  • 7

2 Answers2

3

I haven't ever read Boyd's book, but I hope the following Minkowski inequality is helpful: For any $a_i,b_i\in\mathbb R$ and $p\geqslant 1$, we have $$ \Big(\sum_{i=1}^n|a_i+b_i|^p\Big)^{1/p}\leqslant\Big(\sum_{i=1}^n|a_i|^p\Big)^{1/p}+\Big(\sum_{i=1}^n|b_i|^p\Big)^{1/p}. $$ The convexity of $h$ follows, as we show below.


We write vectors as $\mathbf{x} = (x_1, \dots x_n)$. For each $i \in [n]$, define the function $g_i : \mathbb{R}^n \to \mathbb{R}$ as $$ g_i(\mathbf{x}) = \max(x_i, 0 ) \enspace, $$ which is convex and non-negative. We will now show that

$$ h(\mathbf{x}) = \left( \sum_{i=1}^n g_i(\mathbf{x})^p \right)^{1/p} $$

is convex, using Minkowski's inequality.

Let $0\leqslant \lambda \leqslant1$ and let $\mathbf{x}, \mathbf{y} \in \mathbb{R}^n$. Observe that $$ \begin{aligned} h \big( \lambda \mathbf{x} + (1-\lambda) \mathbf{y} \big) &= \Big(\sum_{i=1}^k g_i(\lambda \mathbf{x} +(1-\lambda) \mathbf{y} )^p\Big)^{1/p} \\ &\leqslant \Big(\sum_{i=1}^k \big(\lambda g_i(\mathbf{x})+(1-\lambda)g_i(\mathbf{y}) \big)^p\Big)^{1/p} \\ &\leqslant\Big(\sum_{i=1}^k(\lambda g_i(\mathbf{x})^p \Big)^{1/p}+\Big(\sum_{i=1}^k((1-\lambda)g_i(\mathbf{y}))^p\Big)^{1/p} \\ &=\lambda \Big(\sum_{i=1}^k g_i(\mathbf{x})^p\Big)^{1/p}+(1-\lambda) \Big(\sum_{i=1}^k g_i(\mathbf{y})^p\Big)^{1/p} \\ &= \lambda h(\mathbf{x}) + (1-\lambda) h(\mathbf{y}) \enspace, \end{aligned} $$ where the first inequality follows from convexity of each $g_i$ and the second inequality is Minkowski's inequality, taking $a_i = \lambda g_i(\mathbf{x})$ and $b_i = (1-\lambda) g_i(\mathbf{y})$.

0

It is quite simple. The function $f(t) = \| t \|_p = (\sum_{i=1}^k t_i^p)^{1/p}$ is convex since it's a norm for $p \geq 1$, and all norms are convex. Moreover, $f(z)$ is increasing in every component $t_i$ when $t \geq 0$.

The functions $\phi_i(z) = \max \{ z_i, 0\}$ are also convex as a maximum of two convex functions, and their range is non-negative.

Thus, $$ h(z) = \left( \sum_{i=1}^k \max\{ z_i, 0 \}^p \right)^{1/p} = f(\phi_1(z), \dots, \phi_k(z)) $$ is convex as a composition of a convex non-decreasing function onto convex functions.