In this paper, we analyze two popular semidefinite programming \SDPb relaxations for quadratically constrained quadratic programs \QCQPb with matrix variables. These are based on \emph{vector-lifting} and on \emph{matrix lifting} and are of different size and expense. We prove, under mild assumptions, that these two relaxations provide equivalent bounds. Thus, our results provide a theoretical guideline for how to choose an inexpensive \SDP relaxation and still obtain a strong bound. Our results also shed important insights on how to simplify large-scale \SDP constraints by exploiting the particular sparsity pattern.
Citation
CORR 2010-02, University of Waterloo, Canada, april/2010.