Closed form solution of an SDP

370 Views Asked by At

Given symmetric positive definite matrices $A$, $M_1$ and $M_2$, is there any closed form solution for the following convex problem in $X$?

$$\begin{array}{ll} \text{maximize} & \mbox{tr}(AX)\\ \text{subject to} & \begin{bmatrix} M_1 & X\\ X^\top & M_2\end{bmatrix} \succeq 0\end{array}$$

1

There are 1 best solutions below

0
On BEST ANSWER

Let $Y=M_1^{-1/2} X M_2^{-1/2}$, so $X=M_1^{1/2} Y M_2^{1/2}$. Then the objective can be written $$\mathop{\textrm{Tr}}(AX) = \mathop{\textrm{Tr}}(AM_1^{1/2} Y M_2^{1/2}) = \mathop{\textrm{Tr}}(M_2^{1/2}AM_1^{1/2} Y) = \mathop{\textrm{Tr}}(BY)$$ where $B=M_2^{1/2}AM_1^{1/2}$. The constraint becomes $$\begin{bmatrix} M_1 & M_1^{1/2} Y M_2^{1/2} \\ M_2^{1/2} Y^T M_1^{1/2} & M_2 \end{bmatrix} = \begin{bmatrix} M_1^{1/2} & 0 \\ 0 & M_2^{1/2} \end{bmatrix} \begin{bmatrix} I & Y \\ Y^T & I \end{bmatrix} \begin{bmatrix} M_1^{1/2} & 0 \\ 0 & M_2^{1/2} \end{bmatrix} \succeq 0 $$ allowing us to drop the left and right terms to reduce this to $$\begin{bmatrix} I & Y \\ Y^T & I \end{bmatrix} \succeq 0 \quad\Longleftrightarrow\quad \|Y\|_2\leq 1$$ So the problem reduces to $$\begin{array}{ll} \text{maximize} & \mathop{\textrm{Tr}}(BY) \\ \text{subject to} & \|Y\|_2\leq 1 \end{array}$$ But this is just the definition of the dual norm for $\|\cdot\|_2$, applied to $B$ (technically, to $B^T$). So the optimal value is $$\sum_{i=1}^n \sigma_i(B) = \sum_{i=1}^n \sigma_i(M_2^{1/2}AM_1^{1/2})$$ Now we can read off the answer by inspection. If $B=U\Sigma V^T$ is the SVD of $B$, then $Y=VU^T$. To verify: $$\mathop{\textrm{Tr}}(BY)=\mathop{\textrm{Tr}}(U\Sigma V^TVU^T) =\mathop{\textrm{Tr}}(U^TU\Sigma V^TV)=\mathop{\textrm{Tr}}(\Sigma)=\sum_i^n \sigma_i(B)$$ Given $Y$, then, $X=M_1^{1/2} UV^T M_2^{1/2}.$