Show that the following function is convex. $$ f(x) = \log \left( e^{x_1} + \cdots + e^{x_n} \right) $$
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 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...
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.