Transforming rank constraints over positive semidefinite matrices

47 Views Asked by At

For $A, B \in S_{n\times n}$, $i$.$e$. symmetric matrices. Consider the following program

$$ \begin{align} \underset{ Y \in S_{n \times n} }{ \text{Find} } \quad & Y \succeq 0 \\ s.t. \quad & \langle A,Y \rangle = a_{1} \\ & Y \succeq 0 \\ & \langle B,Y \rangle \leq b_{1} \\ &\operatorname{Rank} (Y) = s \end{align} $$ $s$ is just some number less than $n$, for simplicity, assume it is $n-1$ or $n - 2$.

Is there a way to transform the rank constraint to something that is easier to deal with? For $rank(Y) \leq s$, we can just factor $Y$ into $UU^{\top}$, where $U \in M_{n \times s}$. However, I'm not sure how should I bound the inequality in the other way.

Utimaltely, this is an application to a first-order algorithm I know that would solve $\underset{ Q \succeq 0 }{ min }\|\mathscr{A}Q-b\|$ very fast (under some conditions). Factoring $Q = UU^{\top}$ is in fact used in the algorithm, but for the other way, I'm not exactly sure how to transform the constraints.

I posted a question about finding the dual of the above program, which might not related.