quadratic matrix programming

On Integrality in Semidefinite Programming for Discrete Optimization

  • Frank de Meijer
  • Renata Sotirov
    • Categories Combinatorial Optimization, Quadratic Programming, Semi-definite Programming Tags , , , ,

    It is well-known that by adding integrality constraints to the semidefinite programming (SDP) relaxation of the max-cut problem, the resulting integer semidefinite program is an exact formulation of the problem. In this paper we show similar results for a wide variety of discrete optimization problems for which SDP relaxations have been derived. Based on a … Read more

    On Equivalence of Semidefinite Relaxations for Quadratic Matrix Programming

  • Yichuan Ding
  • Dongdong Ge
  • Henry Wolkowicz
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , ,

    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 … Read more