I would like to optimize a function of the following form: \begin{equation} \sum_{i,j=1}^N c_{i,j} \mathbf{x}_i \cdot \mathbf{x}_j, \end{equation} 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 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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