Suppose we wish to solve the quadratically constrained quadratic program (QCQP) in $x \in \mathbb R^n$
$$\begin{array}{rl} \text{minimize} & \frac{1}{2}x^\top Lx\\ \text{subject to} & Ax=b\\ & x^\top P_i x=0\ \forall x\in\{1,\ldots,m\}. \end{array}$$
where $L \in \mathbb R^{n\times n}$ is positive definite, whereas matrices $P_i$ are not.
We can write a semidefinite relaxation of this problem as follows
$$\begin{array}{rl} \min_{x\in\mathbb R^n, X\in\mathbb R^{n\times n}}& \frac{1}{2}\mathrm{tr}(LX)\\ \mathrm{s.t.} & \begin{pmatrix} -b & A \end{pmatrix}\begin{pmatrix} 1 &x^\top\\x & X\end{pmatrix}=\begin{pmatrix} 0&0\end{pmatrix} \\ & \mathrm{tr}(P_iX)=0\ \forall x\in\{1,\ldots,m\}\\ & \begin{pmatrix} 1 &x^\top\\x & X\end{pmatrix}\succeq0 \end{array}$$
Adding a constraint $X=xx^\top$ would make the above equivalent to the original QCQP. The first constraint is obtained by writing $Ax=b$ as $$\begin{pmatrix}-b&A\end{pmatrix}\begin{pmatrix}1\\x\end{pmatrix}=0$$ and post-multiplying both sides by $\begin{pmatrix}1&x^\top\end{pmatrix}$. I have several related questions:
Are there conditions under which the solution of the original QCQP is also optimal for the relaxed problem? (i.e. relaxing may make the solution nonunique but not have a lower objective value)
Are there constraints I should add to the convex relaxation to make it tighter?
Are there conditions under which the optimal $X$ in the relaxed problem is rank-$1$?
Additional details in case they help:
- My $L$ has similar structure to a graph Laplacian
- Everything is convex in this problem except the (pesky) $P_i$ constraints, but these are "homogeneous" in the sense that they are purely degree-$2$ with zero on the right-hand side.
- The problem to which I'm applying this relaxation is a little complicated to explain in this post, but my experience experimentally is that, well, sometimes $X$ is rank-$1$ and sometimes it's low-rank but not rank-$1$. I haven't figured out the pattern.