On Equivalence of Semidefinite Relaxations for Quadratic Matrix Programming

  • Yichuan Ding
  • Dongdong Ge
  • Henry Wolkowicz
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , , Short URL: https://optimization-online.org/?p=11126

    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.

    Article

    Download

    View On Equivalence of Semidefinite Relaxations for Quadratic Matrix Programming