# Semidefinite relaxation for a quadratic feasibility problem using CVX

The following decides the feasibility of a semidefinite program (SDP)

\begin{align} \max_{\mathbf{Z}}~0 \\\ \mathrm{trace}(\mathbf{Z})\leq \rho \\\ \mathrm{trace}(\mathbf{S}_1\mathbf{Z}) \geq \alpha \\\ \mathrm{trace}(\mathbf{S}_2\mathbf{Z}) \geq \alpha \\\ \mathbf{Z} \geq 0 \end{align}

where $\mathbf{S}_2$ and $\mathbf{S}_2$ are Hermitian matrices and $\rho, \alpha > 0$. This is the semidefinite relaxation of a quadratic feasibility problem, i.e., $\mathbf{Z} = \mathbf{z}\mathbf{z}^H$. CVX never returned a rank-$1$ solution for this SDP. Does it mean that the semidefinite relaxation is not optimal in this case? Is there a theoretical way of arguing this?

Note: I decide the matrix to be rank-$1$ if it has only one singular value above a particular threshold which is set very low as $10^{-6}$.

• Read this. The rank-$1$ solution should be found on the boundary of the spectrahedron. Try a nonzero objective function. – Rodrigo de Azevedo Dec 12 '17 at 15:26