Vtyjkyuk

Please forgive my ignorance. I have a quick silly question about a statement given without proof in Convex Optimization by Boyd and Vandenberghe (page 87).

Suppose $mathbbR_+^n$ is the set of vectors $v$ such that every coordinate of $v$ is real-valued and non-negative. Suppose $z in mathbbR_+^n$. Suppose that $z_i$ refers to the $i^th$ coordinate of $z$. Suppose $x$ is a scalar such that $x geq 0$ and suppose that $p$ is a scalar such that $0 < p leq 1$.

Consider the functions,

beginalign
i(z) & = sum_i=1^n z_i^p
\\
j(x) & = x^frac1p
endalign

Boyd and Vandenberghe claim without proof that the function,

$$h(z) = j(i(z))=left( sum_i=1^n z_i^p right)^frac1p$$

is a concave function of $z$. Why is this true?

I understand that $z_i^p$ is a non-decreasing concave function of $z_i$. Therefore $i(z)$ is a concave function of $z$. I also understand that $j(x)$ is a non-decreasing convex function of $x$.

However, this is where my understanding breaks down. Since $i(z)$ is concave and non-decreasing in each $z_i$, but $j(x)$ is convex, I don't know of any composition rule I can apply to arrive at the conclusion that $h(z)$ is concave. What am I missing?

The convex function $j$ of a concave function $i$ is not necessarily concave. For example, if $j$ is strictly convex and $i$ is a constant function, then $jcirc i$ is strictly convex.

In your case, the $p$-"norm" is concave when $p<1$ because the Hessian matrix is negative semidefinite. More specifically, let $S=sum z_i^p$. Then
$$
fracpartial^2 S^1/ppartial z_i partial z_j
=(1-p)S^1/p-2 left( z_i^p-1z_j^p-1 - S z_i^p-2 delta_ij right).
$$
So the Hessian matrix is given by $H=(1-p)S^1/p-2 D(uu^T-SI)D$, where $u=(z_1^p/2,ldots,z_n^p/2)^T$ and $D=operatornamediag(z_1^p/2-1,ldots,z_n^p/2-1)$. As the eigenvalues of the matrix $uu^T-SI$ are $0$ (simple eigenvalue) and $-S$ (with multiplicity $n-1$), $H$ is negative semidefinite.