# Show that this function is convex?

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...

• Did you compute the Hessian? – copper.hat Sep 18 '14 at 3:36
• Yes I did - let me edit it in to the question. – John Sep 18 '14 at 3:41
• 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. – Michael Grant Sep 18 '14 at 3:41
• 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. – Michael Grant Sep 18 '14 at 5:09
• Thanks for your help. Managed to get it. Basically yes I wrote it out and then cleverly defined vectors and used Cauchy Schwarz : ) – John Sep 18 '14 at 6:09

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.