Rank constrained SDP

I would like to optimize a function of the following form: $$\sum_{i,j=1}^N c_{i,j} \mathbf{x}_i \cdot \mathbf{x}_j,$$ where $\mathbf{x}_i \in \mathbf{R}^d$. Is it possible to state this as SDP?

I guess that an SDP variable would be somehow related to the Gramian $G$ of the vectors $\{\mathbf{x}_i\}$, with the constraint $rank(G) \leq d$. Is it possible to impose such a constraint?

1 Answer

The constraint $\mbox{rank}(X) <= d$ is in general a non-convex constraint. Sorry.

A commonly used approach is to minimize the Schatten 1-norm of X (the sum of singular values of X) as a surrogate for minimizing the rank. This works similarly to minimizing the 1-norm of a vector x as a way of minimizing the number of nonzero entries in x.