Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 $\mathbb{R}_+^n$ is the set of vectors $v$ such that every coordinate of $v$ is real-valued and non-negative. Suppose $z \in \mathbb{R}_+^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,

\begin{align} i(z) & = \sum_{i=1}^{n} {z_i^p} \\\\ j(x) & = x^{\frac{1}{p}} \end{align}

Boyd and Vandenberghe claim without proof that the function,

$$h(z) = j(i(z))=\left( \sum_{i=1}^{n} {z_i^p} \right)^{\frac{1}{p}}$$

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?

share|improve this question
    
For $p=1$, the function is convex (it is the $1$-norm on the positive quadrant). –  copper.hat Mar 6 '13 at 7:28
    
I agree that for $p = 1$, $h(z)$ is convex. Indeed, for $p = 1$, $h(z)$ is convex and concave on the domain $\mathbb{R}_+^n$. However, I still don't understand why $h(z)$ is concave when $0 < p < 1$. Thanks for your help, copper.hat :) –  Mike Roberts Mar 6 '13 at 7:43

1 Answer 1

up vote 1 down vote accepted

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

You may show that the $p$-norm is concave when $0<p<1$ by showing that its Hessian matrix is negative semidefinite. More specifically, let $S=\sum z_i^p$. Then $$ \frac{\partial^2 S^{1/p}}{\partial z_i \partial z_j} =(1-p)S^{1/p-2} \left( z_i^{p-1}z_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=\operatorname{diag}(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.

share|improve this answer
    
Boom. Awesome. Thanks for your help, user1551 :) –  Mike Roberts Mar 6 '13 at 7:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.