Skip to main content
1 of 2
dineshdileep
  • 1.4k
  • 10
  • 17

Semi Definite Relaxation for a Quadratic Feasibility Problem using CVX

Consider the following Semi-Definite Feasibility problem \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}_i$ are hermitian matrices of appropriate dimensions. $\rho$,$\alpha$ are known positive quantities. This comes from a quadratic feasibility problem as its semi definite relaxation, so that $\mathbf{Z}=\mathbf{z}\mathbf{z}^H$ in the orginal problem. CVX never returned a rank-one solution for this. Does it mean, semi-definite relaxation is not optimal in this case, is there a theoretical way of arguing this?

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

dineshdileep
  • 1.4k
  • 10
  • 17