# Exact SDP relaxations for quadratic programs with bipartite graph structures

arXiv: https://arxiv.org/abs/2204.09509 · HTML: https://mlsanity.com/paper/2204.09509/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Apr 2022.

## Built on by (most cited first, 1 of 1)

- [On the Exactness of Dantzig-Wolfe Relaxation for Rank Constrained Optimization Problems](https://mlsanity.com/paper/2210.16191/) (2022)

## Abstract (arXiv)

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. Our results on the QCQPs generalize the results on QCQP with sign-definite bipartite graph structures, QCQPs with forest structures, and QCQPs with nonpositive off-diagonal data elements. Second, we propose a conversion method from QCQPs with no particular structure to the ones with bipartite graph structures. As a result, we demonstrate that a wider class of QCQPs can be exactly solved by the SDP relaxation. Numerical instances are presented for illustration.