Computational complexity of low rank SDP

Question

Suppose we are given a general semidefinite program (SDP) of the form with an additinal rank requirement

\begin{array}{rl} {\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle_{\mathbb{S}^n} \\ \text{subject to} & \langle A_i, X \rangle_{\mathbb{S}^n} = b_i, \quad i = 1,\ldots,m \\ & X \succeq 0 \\ & \operatorname{rank} (X)\leq r \end{array}

What is the computational complexity of such problem? What is the optimal algorithm right now?

In particular, I am interested in the cases that $r\leq \log n$, and $r\leq \exp(\sqrt{\log n})$.

Answer 1

Various NP-hard problems, such as MAX-CUT, can be formulated exactly as SDPs with rank constraints (just google e.g. "max cut sdp"). If you want to enforce such rank constraints anyway, a popular approach is to parametrize $X=ZZ^T$ for $Z\in\mathbb{R}^{n\times r}$ and rewrite the optimization problem in terms of $Z$.

Then the positive semidefiniteness and rank constraints hold automatically. Of course, the resulting problem is nonconvex. But people do have success applying generic nonconvex optimization methods to such problems, especially in cases where $n$ is large enough that working with $X$ explicitly is impractical and $r$ is small enough to make it practical.

It is worth noting that everything in sight is invariant under the right action of the orthogonal group which maps $Z\in\mathbb{R}^{n\times r}$ and $O\in \mathcal{O}(r)$ to $ZO$. This invariance means that the problem is rife with saddle points, which may cause problems depending on the choice of optimization method.