4
$\begingroup$

Is $\text{Trace}(e^{XA+A^TX})$ a convex function of $X$? $X$ is diagonal and positive definite, $A$ is symmetric negative definite definite.

And by the way, what is the best way to solve a problem of the form:

$\text{min}.$ $\text{Trace}(e^{XA+A^TX})$

s.t. $X$ diagonal, $X_{ii}>0$ and $1^T X 1<x$

where $X$ is the variable and $A$ is symmetric negative definite, $x>0$, $x \in R$

$\endgroup$
  • $\begingroup$ A minor thing: since $A$ is symmetric, why didn't you drop the transpose? $\endgroup$ – Alt Jul 30 '15 at 16:15
1
$\begingroup$

Let $D$ (resp. $D^+$) be the set of diagonal matrices (resp. diagonal positive matrices). Let $f:X\in D^+\rightarrow tr(e^{XA+AX})$. We seek $\min_X f(X)$ under the condition $tr(X)=\sum_i x_{i,i}=x$.

Fortunately the first derivative of $f$ is easy to calculate. For every $H\in D$, $f'_X(H)=tr(e^{XA+AX}(HA+AH))$ ; the Lagrange condition of our problem can be written: there is $\lambda\in\mathbb{R}$ s.t., for every $H\in D$,$f'_X(H)+\lambda tr(H)=0$ or $tr((Ae^{XA+AX}+e^{XA+AX}A+\lambda I)H)=0$. That is equivalent to the following $n$ equalities:

(*) for every $i$, $(Ae^{XA+AX}+e^{XA+AX}A+\lambda I)_{i,i}=0$.

Remark 1. If $tr(X)<x$, then put $\lambda=0$ in the previous formula.

Remark 2. Unfortunately the second derivative of $f$ is difficult to calculate.

EDIT 1: @ questioner , Tim Notke (a highschool basketball coach) said « Hard work beats talent when talent fails to work hard ».

If we search the critical points, then necessarily $tr(X)=x$ and even $\lambda >0$. Indeed $XA+AX$ symmetric implies that $e^{XA+AX}$ is symmetric $>0$. Thus $spectrum(Ae^{XA+AX})\subset \mathbb{R}^{*-}$ and $tr(Ae^{XA+AX})<0$. Finally, the relations (*) imply that $\lambda>0$ and therefore $tr(X)=x$.

EDIT 2. Let $S_n$ be the set of real symmetric matrices. $X\in S_n\rightarrow e^X$ is not a matrix convex function. Yet $X\in S_n\rightarrow \log(tr(e^X))$ is a spectral matrix function and is convex. cf. convexity of matrix "soft-max" (log trace of matrix exponential)

Thus $g:X\in S_n\rightarrow tr(e^X)$ is also convex. Here we consider $f:X\in S_n\rightarrow g(XA+AX)$ and for every symmetric $H$, $f''_X(H,H)=g''_{XA+AX}(HA+AH,HA+AH)\geq 0$. Finally, for every symmetric $A$, $f$ is convex over $S_n$.

$\endgroup$
  • $\begingroup$ So, what about convexity?! What can be used with the sole first derivate of f?! $\endgroup$ – questioner Jan 4 '15 at 6:26
  • $\begingroup$ Careful there. He offers a partial solution. That sounds a bit ungrateful. $\endgroup$ – Michael Grant Jan 4 '15 at 7:01
  • $\begingroup$ @loup: this sounds a bit vague. What do you mean exactly by $f'_X(H)$? why does X is still appearing in it? (thank you for the quote anyway.) Furthermore, the constraint is inequality not equality, which is why, I think that you have to KKT instead of Lagrange Condition. $\endgroup$ – questioner Jan 5 '15 at 23:24
  • $\begingroup$ @ questioner , 1. the derivative $f'_X$ is a linear function over $D$ (see a book about differential calculus). Note that (star) is equivalent to $\nabla (f+\lambda tr)(X)=0$. 2. Since $f$ and $tr(X)$ are convex, the required minimum -if it exists- is reached on the edge, that is for $tr(X)=x$. 3. The necessary part of KKT condition is a direct consequence of Lagrange's theory (one line proof). 4. (star) is difficult to solve numerically. Perhaps it is better to use the convexity of $f$. You can ask Michael Grant ; he is a specialist in the subject. $\endgroup$ – loup blanc Jan 6 '15 at 9:31

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.