# Convexity of Log-Sum-Exp

Consider a matrix $$A \in \mathbb{R}^{m \times n}$$. Let $$a_i^T$$ be the $$i^{th}$$ row of $$A$$. Define $$f(x) = \log \left( \sum \limits_{i = 1}^m \exp(a_i^Tx) \right)$$ for $$x \in \mathbb{R}^n$$. I'm looking to show that $$f$$ is convex in its domain.

In particular, I'm hoping to use the second order characterization of convexity and show that $$\nabla^2 f(x) \succcurlyeq 0$$. I've written the gradient down as the $$n$$-dimensional vector $$\nabla f(x)$$, where the $$j^{th}$$ element (for $$1 \leq j \leq n$$) is given by $$\frac{\sum \limits_{i = 1}^m a_{ij} \exp (a_i^Tx)}{\sum \limits_{i = 1}^m \exp (a_i^Tx)}$$. However, I'm having trouble writing down the Hessian from this. I think it should be relatively easy then to show that for any non-zero $$v \in \mathbb{R}^n$$, $$v^T\nabla^2f(x)v \geq 0$$. How would I go about completing this proof?

• You've computed $\partial f / \partial x_j$ for each $j$. The $(j,k)$ entry of the Hessian is $\partial^2 f / (\partial x_j \partial x_k)$, which can be obtained by taking an additional partial derivative of a particular entry in your gradient. – angryavian Mar 10 at 23:48

I don't think proving its Hessian matrix is PSD to show the convexity of log-sum-exp function is a proper way. Analyzing the convexity of composite function may be more effective.

However, I still try to compute the Hessian matrix here. Let us reformulate the function $$$$f(x) = \log(I^T \exp(Ax)),$$$$ where $$I \in \mathbb{R}^n$$ is an all-one vector. Then the gradient of $$f$$ is $$$$\nabla f(x) = \frac{A^T \left(\exp(Ax) \circ I \right)}{I^T \exp(Ax)} = \frac{A^T \exp(Ax)}{I^T \exp(Ax)},$$$$ which is actually the OP computed result.

And the Hessian matrix of $$f$$ is $$$$\nabla^2 f(x) = \frac{A^T \operatorname{Diag}(\exp(Ax))A}{(I^T \exp(Ax))^2}.$$$$ Due to $$\operatorname{Diag}(\exp(Ax)) \ge 0$$, the hessian matrix is PSD.