TY - JOUR
T1 - Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
AU - Azuma, Godai
AU - Fukuda, Mituhiro
AU - Kim, Sunyoung
AU - Yamashita, Makoto
N1 - Funding Information:
S. Kim: The research was supported by NRF 2021-R1A2C1003810. M. Yamashita: This research was partially supported by JSPS KAKENHI (Grant No. 20H04145).
Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2022/2
Y1 - 2022/2
N2 - 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 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.
AB - 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 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.
KW - Exact semidefinite relaxations
KW - Forest graph
KW - Quadratically constrained quadratic programs
KW - The rank of aggregated sparsity matrix
UR - http://www.scopus.com/inward/record.url?scp=85114298886&partnerID=8YFLogxK
U2 - 10.1007/s10898-021-01071-6
DO - 10.1007/s10898-021-01071-6
M3 - Article
AN - SCOPUS:85114298886
SN - 0925-5001
VL - 82
SP - 243
EP - 262
JO - Journal of Global Optimization
JF - Journal of Global Optimization
IS - 2
ER -