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

$\endgroup$
  • $\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 Dec 12 '17 at 15:26
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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.