# 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

## 1 Answer

The semidefinite relaxation technique of an homogeneus QCQP is tight when the number of linear constraints is lower or equal to 3. This is shown in

Huang, Yongwei; Palomar, D.P., "Rank-Constrained Separable Semidefinite Programming With Applications to Optimal Beamforming," Signal Processing, IEEE Transactions on , vol.58, no.2, pp.664,678, Feb. 2010 doi: 10.1109/TSP.2009.2031732

Thus, your problem might lead to a high-rank solution.