Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
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?
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.
