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

Question

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!!

Answer 1

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.

Answer 2

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$.