Skip to main content

Semi Definite Relaxation Semidefinite relaxation for a Quadratic Feasibility Problemquadratic feasibility problem using CVX

Consider theThe following Semi-Definite Feasibility problem 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

where $\mathbf{S}_i$$\mathbf{S}_2$ and $\mathbf{S}_2$ are hermitianHermitian matrices of appropriate dimensions.and $\rho$,$\alpha$ are known positive quantities$\rho, \alpha > 0$. This comes fromis the semidefinite relaxation of a quadratic feasibility problem as its semi definite relaxation, so thati.e., $\mathbf{Z}=\mathbf{z}\mathbf{z}^H$ in the orginal problem$\mathbf{Z} = \mathbf{z}\mathbf{z}^H$. CVX never returned a rank-one$1$ solution for this SDP. Does it mean, semi-definite that the semidefinite relaxation is not optimal in this case, is? Is there a theoretical way of arguing this?

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

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

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

Source Link
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}$).