Proving tightness of a semidefinite relaxation of a nonconvex quadratic program

144 Views Asked by At

The Lagrangian of my semidefinite relaxation of a nonconvex QCQP (quadratically-constrained quadratic program) is \begin{align} L&=\sum_{n=1}^{N}\operatorname{tr}\left(\textbf{Q}_n\textbf{X}\right)-\sum_{n=1}^{N-1}\lambda_n\operatorname{tr}\left(\textbf{Q}_n\textbf{X}\right)-\mu\operatorname{tr}\left(\textbf{Q}_N\textbf{X}\right)-\sigma(\operatorname{tr}(\textbf{MX})-1)\\[0.35em] &=\operatorname{tr}\left(\textbf{Q}\textbf{X}\right)-\sigma(\operatorname{tr}(\textbf{MX})-1)\\[0.35em] &=\operatorname{tr}\left(\textbf{P}\textbf{X}\right)+\sigma \end{align} where $\textbf{Q}_n\nsucceq0$ (indefinite) but $\sum_{n=1}^{N}\textbf{Q}_n\succ0$ (positive definite), $\textbf{M}\succeq0$ (zero everywhere but for one positive diagonal entry, $\operatorname{rank}(\textbf{M})=1$), the primary variable is $\textbf{X}\succeq0$, the dual variables are $\lambda_n\geq0$ and $\mu,\sigma\in\mathbb{R}$.

I would like to prove that the optimal solution is rank-1, i.e. $\operatorname{rank}\textbf{X}^\star=1$.

Karush-Kuhn-Tucker (KKT) conditions of optimality:

Primal

$\bullet\;$ $\operatorname{tr}\left(\textbf{Q}_n\textbf{X}^\star\right)\geq0\;$ for $\;n=1,...,N-1$

$\bullet\;$ $\operatorname{tr}\left(\textbf{Q}_N\textbf{X}^\star\right)=0\;$

$\bullet\;$ $\operatorname{tr}\left(\textbf{M}\textbf{X}^\star\right)=1\;$

$\bullet\;$ $\textbf{X}^\star\succeq0\;$

Dual

$\bullet\;$ $\textbf{P}^\star\succeq0$

$\bullet\;$ $\lambda_n^\star\geq0\;$ for $\;n=1,...,N-1$

Complementary Slackness:

$\bullet\;$ $\operatorname{tr}(\textbf{P}^\star\textbf{X}^\star)=0$

$\bullet\;$ $\lambda_n^\star\operatorname{tr}(\textbf{Q}_n\textbf{X}^\star)=0\;$ for $\;n=1,...,N-1$

Since $\textbf{P}^\star,\textbf{X}^\star\succeq0$ follows that if $\operatorname{tr}(\textbf{P}^\star\textbf{X}^\star)=0$ $\Rightarrow$ $\textbf{P}^\star\textbf{X}^\star=0$, meaning that $$(\textbf{Q}^\star-\sigma\textbf{M})\textbf{X}^\star=\textbf{0}.$$ Further, since $\sigma(\operatorname{tr}(\textbf{MX})-1)$ ensures not running into the trivial solution $\textbf{X}=\textbf{0}$, there cannot be slack in that constraint and $\sigma\neq0$. Therefore, we can say that $$\operatorname{rank}(\textbf{Q}^\star\textbf{X}^\star)=\operatorname{rank}(\textbf{M}\textbf{X}^\star)\leq\operatorname{rank}(\textbf{M})=1.$$

At this point, I think, I would need to show that $\textbf{Q}^\star$ is full-rank. Some references considering similar problems just say it is (e.g. https://arxiv.org/pdf/1509.06602.pdf ) but I am not sure, why that would have to be the case. What am I missing? I'm grateful for any hints, comments or ideas.