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?

$\endgroup$
1
  • $\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
    Commented Mar 10, 2020 at 23:48

1 Answer 1

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .