5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ For $p=1$, the function is convex (it is the $1$-norm on the positive quadrant). $\endgroup$ – copper.hat Mar 6 '13 at 7:28
  • $\begingroup$ 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 :) $\endgroup$ – Mike Roberts Mar 6 '13 at 7:43
2
$\begingroup$

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 $j\circ 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 $$ \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.

$\endgroup$
  • $\begingroup$ Boom. Awesome. Thanks for your help, user1551 :) $\endgroup$ – Mike Roberts Mar 6 '13 at 7:54
  • $\begingroup$ is this function concave for $p< 1$? $\endgroup$ – L.F. Cavenaghi Sep 2 '18 at 2:50
  • 1
    $\begingroup$ @L.F.Cavenaghi Oh, you mean $p\le0$? Yes it's concave and the same reasoning applies. I had $0<p<1$ in the original edit because that was what the OP asked about. $\endgroup$ – user1551 Sep 4 '18 at 9:42
  • $\begingroup$ @user1551, thank you very much. $\endgroup$ – L.F. Cavenaghi Sep 4 '18 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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