Minimize the Trace of 2 PSD Matrices Product Subject to a Constraint on the Trace

Question

Given $ A \in \mathcal{S}_{+}^{n \times n} $ (PSD Matrix) with $ \lambda_{max} \left( A \right) < 1 $ solve the following optimization problem:

$$ \arg \min_{X \in \mathcal{S}_{+}^{n \times n}} \operatorname{Tr} \left( A X \right), \; \text{subject to} \; \operatorname{Tr} \left( X \right) \geq a $$

Where $ a \geq 0 $ is a given parameter.

Answer 1

We may assume that $A=\operatorname{diag}(\mathbf a)$, where the entries of $\mathbf a=(a_1,a_2,\ldots,a_n)$ are arranged in descending order. Let the diagonal of $X$ be $\mathbf x$. Since $\operatorname{tr}(AX)=\langle\mathbf a,\mathbf x\rangle$ and $\operatorname{diag}(\mathbf x)$ is positive definite when $\mathbf x>0$ entrywise, we may further assume that $X=\operatorname{diag}(\mathbf x)$. Therefore, if we denote $$ S=\left\{\mathbf x:\ \mathbf x>0,\ \langle\mathbf x,\mathbf 1\rangle\ge a\right\} $$ where $\mathbf 1=(1,1,\ldots,1)$, the problem reduces to finding $\inf_{\mathbf x\in S} \langle\mathbf x,\mathbf a\rangle$.

Let $\mathbf x_0=(0,\ldots,0,a)$. It isn't hard to see that

• $\mathbf x_0$ is an accumulation point of $S$ and $\langle\mathbf x_0,\mathbf a\rangle=aa_n$,
• $\langle\mathbf x,\mathbf a\rangle\ge\langle\mathbf x_0,\mathbf a\rangle$ for every $\mathbf x\in S$
• $\langle\mathbf x,\mathbf a\rangle>\langle\mathbf x_0,\mathbf a\rangle$ for every $\mathbf x\in S$ if $a_1>a_n$ or $a_n>0=a$.

It follows that $\inf_{\mathbf x\in S} \langle\mathbf x,\mathbf a\rangle=aa_n$ and this infimum value is unattainable unless $a_1=a_n$ and (i) $a_n=0$ or (ii) $a>0$, i.e. unless (i) $A=0$ or (ii) $A$ is a positive multiple of the identity matrix and $a>0$.