Exact SDP relaxations of quadratically constrained quadratic programs with forest structures

DOI10.1007/S10898-021-01071-6zbMATH Open1486.90138arXiv2009.02638OpenAlexW3196749966MaRDI QIDQ2114577FDOQ2114577

Sunyoung Kim, Mituhiro Fukuda, Godai Azuma, Makoto Yamashita

Publication date: 15 March 2022

Published in: Journal of Global Optimization (Search for Journal in Brave)

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$ 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.

Full work available at URL: https://arxiv.org/abs/2009.02638

zbMATH Keywords

quadratically constrained quadratic programsexact semidefinite relaxationsforest graphrank of aggregated sparsity matrix

Mathematics Subject Classification ID

Quadratic programming (90C20) Semidefinite programming (90C22)

Cites Work

• SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
• Algorithm 996
• A Survey of the S-Lemma
• Assignment Problems and the Location of Economic Activities
• Handbook of semidefinite programming. Theory, algorithms, and applications
• Copositive and semidefinite relaxations of the quadratic assignment problem
• Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons
• Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
• On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues
• Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion
• A note on a three-term recurrence for a tridiagonal matrix.
• Handbook on semidefinite, conic and polynomial optimization
• A new graph parameter related to bounded rank positive semidefinite matrix completions
• The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree
• Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxa\-tions
• On the relative position of multiple eigenvalues in the spectrum of an Hermitian matrix with a given graph
• Title not available (Why is that?)
• Exactness of Semidefinite Relaxations for Nonlinear Optimization Problems with Underlying Graph Structure
• Simultaneous tridiagonalization of two symmetric matrices
• Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
• On the simultaneous tridiagonalization of two symmetric matrices
• Converse to the Parter--Wiener theorem: the case of non-trees
• Title not available (Why is that?)
• Finding Low-rank Solutions of Sparse Linear Matrix Inequalities using Convex Optimization
• Quadratically Constrained Quadratic Programs on Acyclic Graphs With Application to Power Flow
• The generalized trust region subproblem: solution complexity and convex hull results
• Eigenvalue-based algorithm and analysis for nonconvex QCQP with one constraint
• Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs
• Conic relaxation approaches for equal deployment problems
• Exploiting aggregate sparsity in second-order cone relaxations for quadratic constrained quadratic programming problems
• Polyhedral-based Methods for Mixed-Integer SOCP in Tree Breeding

Cited In (5)

• A graphic structure based branch-and-bound algorithm for complex quadratic optimization and applications to magnitude least-square problem
• On exact and inexact RLT and SDP-RLT relaxations of quadratic programs with box constraints
• Outcome-space branch-and-bound outer approximation algorithm for a class of non-convex quadratic programming problems
• KKT-based primal-dual exactness conditions for the Shor relaxation
• Exact SDP relaxations for quadratic programs with bipartite graph structures

Uses Software

• SDPNAL+
• BBCPOP

   Recommendations

• Exact SDP relaxations for quadratic programs with bipartite graph structures 👍 👎
• Exactness criteria for SDP-relaxations of quadratic extremum problems 👍 👎
• SDP relaxations for quadratic optimization problems derived from polynomial optimization problems 👍 👎
• Exact SDP relaxations for classes of nonlinear semidefinite programming problems 👍 👎
• On convex relaxations for quadratically constrained quadratic programming 👍 👎
• Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxa\-tions 👍 👎
• SDP relaxation of homogeneous quadratic optimization: approximation bounds and applications 👍 👎
• Title not available (Why is that?) 👍 👎
• A new convex relaxation for quadratically constrained quadratic programming 👍 👎
• Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons 👍 👎

This page was built for publication: Exact SDP relaxations of quadratically constrained quadratic programs with forest structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2114577)