  


Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
Godai Azuma (azuma.a.ggm.is.titech.ac.jp) 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 $n1$ and the matrix remains positive semidefinite after replacing some offdiagonal 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 foreststructured aggregate sparsity matrix, such as the tridiagonal or arrowtype 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, rank of aggregated sparsity matrix Category 1: Global Optimization Category 2: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Citation: Download: [PDF] Entry Submitted: 09/08/2020 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  