11
$\begingroup$

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.

$\endgroup$
15
  • $\begingroup$ 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. $\endgroup$
    – Semiclassical
    Feb 24, 2021 at 18:25
  • $\begingroup$ @Semiclassical Thanks! I have adopted the notation. $\endgroup$
    – zxzx179
    Feb 24, 2021 at 18:37
  • $\begingroup$ $A$ is mathworld.wolfram.com/DoublyNonnegativeMatrix.html $\endgroup$
    – Rodrigo de Azevedo
    Feb 24, 2021 at 18:47
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Semiclassical
    Feb 24, 2021 at 20:36
  • 1
    $\begingroup$ 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. $\endgroup$
    – Semiclassical
    Feb 25, 2021 at 0:15

0

Reset to default

You must log in to answer this question.