2
$\begingroup$

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

$\endgroup$

closed as off-topic by dantopa, Saad, Thomas Shelby, José Carlos Santos, Eevee Trainer Apr 19 at 0:31

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Saad, Thomas Shelby, José Carlos Santos, Eevee Trainer
If this question can be reworded to fit the rules in the help center, please edit the question.

4
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.