0
$\begingroup$

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?

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – angryavian Mar 10 at 23:48
0
$\begingroup$

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 \begin{equation} f(x) = \log(I^T \exp(Ax)), \end{equation} where $I \in \mathbb{R}^n$ is an all-one vector. Then the gradient of $f$ is \begin{equation} \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)}, \end{equation} which is actually the OP computed result.

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

| cite | improve this answer | | | | |
$\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.