Exact SDP relaxations for quadratic programs with bipartite graph structures

Godai Azuma (), Mituhiro Fukuda (), Sunyoung Kim () and Makoto Yamashita ()
Additional contact information
Godai Azuma: Tokyo Institute of Technology
Mituhiro Fukuda: Tokyo Institute of Technology
Sunyoung Kim: Ewha W. University
Makoto Yamashita: Tokyo Institute of Technology

Journal of Global Optimization, 2023, vol. 86, issue 3, No 6, 691 pages

Abstract: Abstract 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.

Keywords: Quadratically constrained quadratic programs; Exact semidefinite relaxations; Bipartite graph; Sign-indefinite QCQPs; Rank of aggregated sparsity matrix; 90C20; 90C22; 90C25; 90C26 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-022-01268-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:86:y:2023:i:3:d:10.1007_s10898-022-01268-3

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-022-01268-3

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().