# Minimize $\mbox{trace}(AX)$ over $X$ with a positive semidefinite $X$

I want to minimize $\mbox{trace}(AX)$ over $X$, under the constraint that $X$ is positive semidefinite. I guess the solution should be bounded only for a positive semidefinite $A$, and it's zero, or the solution should be minus infinity. If this is correct, can anyone tell me why? or if it is wrong, please tell me the correct solution. Thank you very much!!

• the zero matrix is positive semi-definite :) – reuns Apr 18 '16 at 2:08
• Can you explain it more? I still didn't get it. – Ben Wu Apr 18 '16 at 3:27
• Guys I think it is just a standard SDP problem. But I still wonder how to solve it. Can't find the solution in the textbook :( – Ben Wu Apr 18 '16 at 21:23

If $\mathrm X \in \mathbb R^{n \times n}$ is symmetric and positive definite, then there is a matrix $\mathrm Y \in \mathbb R^{r \times n}$ such that

$$\mathrm X = \mathrm Y^T \mathrm Y$$

If $\mathrm A \in \mathbb R^{n \times n}$ is also symmetric, then it has an eigendecomposition of the form $\mathrm A = \mathrm Q \Lambda \mathrm Q^T$, where $\mathrm Q$ is orthogonal. Hence,

$$\mbox{tr} (\mathrm A \mathrm X) = \mbox{tr} (\mathrm A \mathrm Y^T \mathrm Y) = \mbox{tr} (\mathrm Y \mathrm A \mathrm Y^T) = \mbox{tr} (\mathrm Y \mathrm Q \Lambda \mathrm Q^T \mathrm Y^T) = \mbox{tr} (\mathrm Y \mathrm Q \Lambda (\mathrm Y \mathrm Q)^T)$$

Let $\mathrm Z := \mathrm Y \mathrm Q$. Hence,

$$\begin{array}{rl} \mbox{tr} (\mathrm Y \mathrm Q \Lambda (\mathrm Y \mathrm Q)^T) = \mbox{tr} (\mathrm Z \Lambda \mathrm Z^T) &= \mbox{tr} \left(\displaystyle\sum_{k=1}^n \lambda_k (\mathrm A) \mathrm z_k \mathrm z_k^T\right)\\\\ &= \displaystyle\sum_{k=1}^n \lambda_k (\mathrm A) \, \mbox{tr} \left(\mathrm z_k \mathrm z_k^T\right)\\\\ &= \displaystyle\sum_{k=1}^n \lambda_k (\mathrm A) \|\mathrm z_k\|_2^2\\\\ &\geq \lambda_{\min} (\mathrm A) \displaystyle\sum_{k=1}^n \|\mathrm z_k\|_2^2\\\\ &= \lambda_{\min} (\mathrm A) \, \mbox{tr} (\mathrm Z^T \mathrm Z)\end{array}$$

where

$$\mbox{tr} (\mathrm Z^T \mathrm Z) = \mbox{tr} (\mathrm Q^T \mathrm Y^T \mathrm Y \mathrm Q) = \mbox{tr} (\mathrm Q^T \mathrm X \mathrm Q) = \mbox{tr} (\mathrm X)$$

Thus,

$$\mbox{tr} (\mathrm A \mathrm X) \geq \lambda_{\min} (\mathrm A) \, \mbox{tr} (\mathrm X)$$

If $\lambda_{\min} (\mathrm A) < 0$, we can make $\mbox{tr} (\mathrm A \mathrm X)$ arbitrarily large and negative, i.e., there is no (finite) minimum. If $\mathrm A$ is positive semidefinite, then $\mbox{tr} (\mathrm A \mathrm X) \geq 0$, i.e., the minimum is zero.

Let $A\in M_n(\mathbb{R})$; there are a symmetric $S$ and a skew-symmetric $K$ s.t. $A=S+K$; thus $tr(AX)=tr(SX)+tr(KX)=tr(SX)$ (since $X$ is symmetric, $tr(KX)=0$). We may assume that $S=diag(\lambda_1,\cdots,\lambda_p,\mu_1,\cdots,\mu_q,0_r)$ where $\lambda_i>0,\mu_j<0,p+q+r=n$.

If $q>0$, then take $X=diag(0_p,xI_q,0_r)$ with $x>0$. Therefore $\inf_X(tr(AX))=-\infty$.

If $q=0$, then $S\geq 0$ and the eigenvalues of $SX$ are $\geq 0$; therefore $\inf_X(tr(AX))=0$.