Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
From MaRDI portal
Publication:2114577
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 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 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.
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
- scientific article; zbMATH DE number 7152114
- A new convex relaxation for quadratically constrained quadratic programming
- Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons
Cites work
- scientific article; zbMATH DE number 1534299 (Why is no real title available?)
- A Survey of the S-Lemma
- A new graph parameter related to bounded rank positive semidefinite matrix completions
- A note on a three-term recurrence for a tridiagonal matrix.
- Algorithm 996
- Assignment Problems and the Location of Economic Activities
- Conic relaxation approaches for equal deployment problems
- Converse to the Parter--Wiener theorem: the case of non-trees
- Copositive and semidefinite relaxations of the quadratic assignment problem
- Eigenvalue-based algorithm and analysis for nonconvex QCQP with one constraint
- Elementary linear algebra with supplemental applications, international student version
- Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs
- Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxa\-tions
- Exactness of semidefinite relaxations for nonlinear optimization problems with underlying graph structure
- Exploiting aggregate sparsity in second-order cone relaxations for quadratic constrained quadratic programming problems
- Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion
- Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
- Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
- Finding low-rank solutions of sparse linear matrix inequalities using convex optimization
- Handbook of semidefinite programming. Theory, algorithms, and applications
- Handbook on semidefinite, conic and polynomial optimization
- On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues
- On the relative position of multiple eigenvalues in the spectrum of an Hermitian matrix with a given graph
- On the simultaneous tridiagonalization of two symmetric matrices
- Polyhedral-based methods for mixed-integer SOCP in tree breeding
- Quadratically Constrained Quadratic Programs on Acyclic Graphs With Application to Power Flow
- SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
- Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons
- Simultaneous tridiagonalization of two symmetric matrices
- The generalized trust region subproblem: solution complexity and convex hull results
- The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree
Cited in
(9)- A graphic structure based branch-and-bound algorithm for complex quadratic optimization and applications to magnitude least-square problem
- Invariants of SDP exactness in quadratic programming
- Exploiting aggregate sparsity in second-order cone relaxations for quadratic constrained quadratic programming problems
- Exact SDP relaxations for quadratic programs with bipartite graph structures
- Simultaneous diagonalization of matrices and its applications in quadratically constrained quadratic programming
- On the tightness of SDP relaxations of QCQPs
- 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
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)
