Exact SDP relaxations of quadratically constrained quadratic programs with forest 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, 2022, vol. 82, issue 2, No 2, 243-262

Abstract: Abstract 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 than $$n-1$$ n - 1 and the matrix remains positive semidefinite after replacing some off-diagonal nonzero elements with zeros, then the standard SDP relaxation provides an exact optimal solution for the QCQP under feasibility assumptions. In particular, we demonstrate that QCQPs with forest-structured aggregate sparsity matrix, such as the tridiagonal or arrow-type matrix, satisfy the exactness condition on the rank. The exactness is attained by considering the feasibility of the dual SDP relaxation, the strong duality of SDPs, and a sequence of QCQPs with perturbed objective functions, under the assumption that the feasible region is compact. We generalize our result for a wider class of QCQPs by applying simultaneous tridiagonalization on the data matrices. Moreover, simultaneous tridiagonalization is applied to a matrix pencil so that QCQPs with two constraints can be solved exactly by the SDP relaxation.

Keywords: Quadratically constrained quadratic programs; Exact semidefinite relaxations; Forest graph; The rank of aggregated sparsity matrix (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-021-01071-6 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:82:y:2022:i:2:d:10.1007_s10898-021-01071-6

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

DOI: 10.1007/s10898-021-01071-6

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 ().