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

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.

• The trace of the product of two positive semidefinite matrices is always nonnegative. When $X$ is close to zero, the trace of $AX$ is also close to zero. Therefore the infimum is zero. Mar 15, 2020 at 11:36
• @user1551 :X must be positive definite matrix Mar 15, 2020 at 12:43
• @hichemhb That doesn't change anything; the argument still applies and the infimum is zero. If we instead had a constraint of $\operatorname{Tr}(X) = a$, we would have a non-zero infimum. Mar 15, 2020 at 14:22
• @user1551 i saw your answer in (math.stackexchange.com/questions/239352/… ) however I did not understand the utility of the two theorems annones and the finding on the matrix Q. i think that we can use the same idea ? Mar 15, 2020 at 17:40
• In your new edit, does "PSD" mean "positive semidefinite"? Can $A$ and $X$ be singular? Mar 15, 2020 at 18:14

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