0
$\begingroup$

So I'm supposed to show that this function is convex, but I have no idea how to go about it...I've been told to use Cauchy Schwarz in order to show that the Hessian is non-negative definite, but I'm not sure how to do that. The function is:

$$f(x) = log(e^{x_1} + \dots + e^{x_n})$$

The Hessian is:

For $i \neq j$:

$$\frac{\partial^2 f}{\partial x_i \partial x_j} = \frac{-e^{x_i+x_j}}{\left(\sum e^{x_i}\right)^2}$$

For $ i = j$:

$$\frac{\partial^2 f}{\partial x_i^2} = \frac{e^{x_i}\sum {e^{x_i}}-e^{2x_j}}{\left(\sum e^{x_i}\right)^2}$$

After this, writing out an expression for $v^THv$ gives:

$$\sum \frac{\partial^2 f}{\partial x_i^2}v_i^2 + 2\sum\frac{\partial^2 f}{\partial x_ix_j}v_iv_j$$

It's clear the first term is non-negative. I'm not sure what to do about the second term though...

$\endgroup$
  • $\begingroup$ Did you compute the Hessian? $\endgroup$ – copper.hat Sep 18 '14 at 3:36
  • $\begingroup$ Yes I did - let me edit it in to the question. $\endgroup$ – John Sep 18 '14 at 3:41
  • $\begingroup$ Indeed. Please show all your work up to and including the Hessian itself. And once you compute the Hessian, go ahead and give us a formula for $v^THv$, which is supposed to be positive for all $v$. That's actually what you use Cauchy Schwarz to prove. $\endgroup$ – Michael Grant Sep 18 '14 at 3:41
  • $\begingroup$ You haven't really written out the formula for $v^THv$. Instead you kept the partial derivatives in there. That is obscuring the structure of the Hessian. I honestly cannot remember off the top of my head exactly what the answer is; I would have to work it out. But I know this is the right direction. $\endgroup$ – Michael Grant Sep 18 '14 at 5:09
  • $\begingroup$ Thanks for your help. Managed to get it. Basically yes I wrote it out and then cleverly defined vectors and used Cauchy Schwarz : ) $\endgroup$ – John Sep 18 '14 at 6:09
1
$\begingroup$

I find it easier to first work with $f(x) = \log \phi(x)$. This gives ${\partial f(x) \over \partial x} = {1 \over \phi(x)} {\partial \phi(x) \over \partial x} $, and continuing, we get ${\partial^2 f(x) \over \partial x^2} = {1 \over \phi(x)^2}\left( \phi(x) {\partial^2 \phi(x) \over \partial x^2} - {\partial \phi(x) \over \partial x}^T {\partial \phi(x) \over \partial x} \right)$, so to verify positive semi-definiteness, we can just deal with the term in brackets, a slight simplification.

In particular, as Michael wrote in the comments, we need only verify that $v^T \left( \phi(x) {\partial^2 \phi(x) \over \partial x^2} - {\partial \phi(x) \over \partial x}^T {\partial \phi(x) \over \partial x} \right) v \ge 0$.

Since $\phi(x) = \sum_i e^{x_i}$ is separable, the derivatives have a particularly easy form, ${\partial \phi(x) \over \partial x} = \begin{bmatrix}e^{x_1} & \cdots & e^{x_n} \end{bmatrix}$ and ${\partial^2 \phi(x) \over \partial x^2} = \operatorname{diag} (e^{x_1},...,e^{x_n} )$, and so we get the expression $ \sum_i \sum_j e^{x_i} e^{x_j} ( v_j^2 - v_i v_j)$. If we swap $i,j$ and add we get $ \sum_i \sum_j e^{x_i} e^{x_j} ( v_j^2 - v_i v_j) = {1 \over 2} \sum_i \sum_j e^{x_i} e^{x_j} ( v_i^2+v_j^2 - 2v_i v_j)$, and since $v_i^2+v_j^2 - 2v_i v_j = (v_i-v_j)^2 \ge 0$, we obtain the desired result.

Note: Here is a slightly simpler way: Show $f(y)-f(x) \ge {\partial f(x) \over \partial x}(y-x)$ instead.

Expanding, we want to show that $\log ({ \phi(y) \over \phi(x) }) \ge { 1 \over \phi(x) }{\partial \phi(x) \over \partial x}(y-x)$, which is the same as showing $\log ( { \sum_k e^{y_k} \over \sum_k e^{x_k} } ) = \log ( \sum_k { e^{x_k} \over \sum_i e^{x_i} } e^{y_k-x_k}) \ge \sum_k { e^{x_k} \over \sum_i e^{x_i} } (y_k-x_k)$.

Let $\mu_k = { e^{x_k} \over \sum_i e^{x_i} } $ and notice that these are convex multipliers, so we want to show $\log ( \sum_k \mu_k e^{y_k-x_k}) \ge \sum_k \mu_k (y_k-x_k)$, which follows since $\log$ is concave.

$\endgroup$

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.