1
$\begingroup$

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}$.

Improve this question
$\endgroup$
1
  • $\begingroup$ Read this. The rank-$1$ solution should be found on the boundary of the spectrahedron. Try a nonzero objective function. $\endgroup$
    – Rodrigo de Azevedo
    Commented Dec 12, 2017 at 15:26

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .