semidefinite programming relaxation

Separable QCQPs and Their Exact SDP Relaxations

  • Masakazu Kojima
  • Sunyoung Kim
  • Naohiko Arima
    • Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming Tags , , , , ,

    This paper studies exact semidefinite programming relaxations (SDPRs) for separable quadratically constrained quadratic programs (QCQPs). We consider the construction of a larger separable QCQP from multiple QCQPs with exact SDPRs. We show that exactness is preserved when such QCQPs are combined through a separable horizontal connection, where the coupling is induced through the right-hand-side parameters … Read more

    Tight semidefinite programming relaxations for sparse box-constrained quadratic programs

  • Aida Khajavirad
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , , , , ,

    We introduce a new class of semidefinite programming (SDP) relaxations for sparse box-constrained quadratic programs, obtained by a novel integration of the Reformulation Linearization Technique into standard SDP relaxations while explicitly exploiting the sparsity of the problem. The resulting relaxations are not implied by the existing LP and SDP relaxations for this class of optimization … Read more