# Analytical solution for a neat semidefinite program (SDP)

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.

• One other way to notate the minimization is as $\min_{X\in S_+^n}$. That's a small thing but it makes the domain a bit more transparent. Feb 24 '21 at 18:25
• @Semiclassical Thanks! I have adopted the notation. Feb 24 '21 at 18:37
• Feb 24 '21 at 18:47
• Since $X$ is a correlation matrix, it can be written as $V^T V$ where the columns of $V$ are all unit vectors. (This is a special case of what's stated in Rodrigo's link.) As such, your weighted sum of variances can be expressed as $$\sum_k \lambda_k y_k^\top V^\top V y_k = \sum_k \lambda_k \|V y_k\|^2.$$ Here I am less confident about how to proceed, but this is certainly is bounded below by 0 (as it should be---$X\succeq 0$, after all) and only achieves this value if $Vy_k=0$ for all $k$. So we want to pick $V$ with kernel containing most of the $y_k$. Feb 24 '21 at 20:36
• I just realized: The elliptope terminology originates from papers of Laurent and Poljak in the 90s. The second such paper (as far as I know) is Laurent and Poljak 1996, and section 5 is explicitly about this exact minimization problem. They don't solve it, but they do give the context in which it appears. Moreover, that seems a good starting point for a literature hunt to determine the present status of the problem. Feb 25 '21 at 0:15