Analytical solution for a neat semidefinite program (SDP)

317 Views Asked by At

Let $A \in S^{n}_{+}$ be a positive semi-definite matrix with all entries being non-negative. I wonder if there is an analytical solution to the following SDP in correlation matrix $X \in S^{n}_{+}$

$$\begin{array}{ll} \underset{X \in S^{n}_{+}}{\text{minimize}} & \mbox{Tr} (A X)\\ \text{subject to} & X_{ii} = 1, \quad \forall i \in [n]\end{array}$$

Does this optimization problem have an analytical solution?


To share some idea on the objective, consider the spectral decomposition of matrix $A$

$$A = \sum_{k} \lambda_k y_k y^{T}_k$$

with $\lambda_k > 0$ being the positive eigenvalues of matrix $A$ and $y_k \in \mathbb{R}^{n}$ the corresponding eigenvectors. The objective is to minimize the weighted sum of variances, i.e.,

$$\mbox{Tr} (A X) = \sum_{k} \lambda_k y^{T}_k X y_k$$

The dual problem is

$$\begin{array}{ll} \underset{D \text{ is diagonal}}{\text{maximize}} & \mbox{Tr}(D)\\ \text{subject to} & A \succeq D\end{array}$$

The problem is so neat, so I wonder if there is any hope to have an analytical solution.