TY - JOUR
T1 - Exact SDP relaxations for quadratic programs with bipartite graph structures
AU - Azuma, Godai
AU - Fukuda, Mituhiro
AU - Kim, Sunyoung
AU - Yamashita, Makoto
N1 - Funding Information:
The research of Godai Azuma was supported by JSPS KAKENHI Grant Number JP22J13893.
Funding Information:
G. Azuma, M. Fukuda, M. Yamashita: The research of Makoto Yamashita was partially supported by JSPS KAKENHI Grant Number JP20H04145. M. Fukuda: The research of Mituhiro Fukuda was supported by grants 2020/04585-7 and 2018/24293-0 from the São Paulo Research Foundation (FAPESP). S. Kim: This work was supported by NRF 2021-R1A2C1003810.
Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2023/7
Y1 - 2023/7
N2 - For nonconvex quadratically constrained quadratic programs (QCQPs), we first show that, under certain feasibility conditions, the standard semidefinite programming (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 generalize the previous results on QCQPs 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.
AB - For nonconvex quadratically constrained quadratic programs (QCQPs), we first show that, under certain feasibility conditions, the standard semidefinite programming (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 generalize the previous results on QCQPs 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.
KW - Bipartite graph
KW - Exact semidefinite relaxations
KW - Quadratically constrained quadratic programs
KW - Rank of aggregated sparsity matrix
KW - Sign-indefinite QCQPs
UR - http://www.scopus.com/inward/record.url?scp=85141397823&partnerID=8YFLogxK
U2 - 10.1007/s10898-022-01268-3
DO - 10.1007/s10898-022-01268-3
M3 - Article
AN - SCOPUS:85141397823
SN - 0925-5001
VL - 86
SP - 671
EP - 691
JO - Journal of Global Optimization
JF - Journal of Global Optimization
IS - 3
ER -