exact semidefinite relaxations

Exact SDP relaxations for quadratic programs with bipartite graph structures

  • Godai Azuma
  • Mituhiro Fukuda
  • Sunyoung Kim
  • Makoto Yamashita
    • Categories Semi-definite Programming Tags , , , ,

    For nonconvex quadratically constrained quadratic programs (QCQPs), we first show that, under certain feasibility conditions, the standard semidefinite (SDP) relaxation is exact for QCQPs with bipartite graph structures. The exact optimal solutions are obtained by examining the dual SDP relaxation and the rank of the optimal solution of this dual SDP relaxation under strong duality. … Read more

    Exact SDP relaxations of quadratically constrained quadratic programs with forest structures

  • Godai Azuma
  • Mituhiro Fukuda
  • Sunyoung Kim
  • Makoto Yamashita
    • Categories Global Optimization, Semi-definite Programming Tags , , ,

    We study the exactness of the semidefinite programming (SDP) relaxation of quadratically constrained quadratic programs (QCQPs). With the aggregate sparsity matrix from the data matrices of a QCQP with $n$ variables, the rank and positive semidefiniteness of the matrix are examined. We prove that if the rank of the aggregate sparsity matrix is not less … Read more