Exact SDP relaxations for quadratic programs with bipartite graph structures
From MaRDI portal
Abstract: For nonconvex quadratically constrained quadratic programs (QCQPs), we first show that, under certain feasibility conditions, the standard semidefinite (SDP) relaxation is exact for QCQPs with bipartite graph structures. The exact optimal solutions are obtained by examining the dual SDP relaxation and the rank of the optimal solution of this dual SDP relaxation under strong duality. Our results on the QCQPs generalize the results on QCQP with sign-definite bipartite graph structures, QCQPs with forest structures, and QCQPs with nonpositive off-diagonal data elements. Second, we propose a conversion method from QCQPs with no particular structure to the ones with bipartite graph structures. As a result, we demonstrate that a wider class of QCQPs can be exactly solved by the SDP relaxation. Numerical instances are presented for illustration.
Recommendations
- Exactness criteria for SDP-relaxations of quadratic extremum problems
- Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
- Exact SDP relaxations for classes of nonlinear semidefinite programming problems
- Exactness of semidefinite relaxations for nonlinear optimization problems with underlying graph structure
- A successive quadratic programming algorithm for SDP relaxation of Max-Bisection
- On solving biquadratic optimization via semidefinite relaxation
- Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxa\-tions
- Semidefinite programming relaxations for the quadratic assignment problem
- Semidefinite relaxation for two mixed binary quadratically constrained quadratic programs: algorithms and approximation bounds
- SDP relaxation of homogeneous quadratic optimization: approximation bounds and applications
Cites work
- A Survey of the S-Lemma
- Copositive and semidefinite relaxations of the quadratic assignment problem
- Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
- 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 conditions for an SDP relaxation of the extended trust region problem
- Exactness of semidefinite relaxations for nonlinear optimization problems with underlying graph structure
- Exploiting Sparsity in SDP Relaxation for Sensor Network Localization
- scientific article; zbMATH DE number 3368525 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- JuMP: a modeling language for mathematical optimization
- Nonchordal positive semidefinite stochastic matrices∗
- Semidefinite programming relaxations for the quadratic assignment problem
- Solving pooling problems with time discretization by LP and SOCP relaxations and rescheduling methods
- Strong duality for generalized trust region subproblem: S-lemma with interval bounds
- Theory of semidefinite programming for sensor network localization
- Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization
Cited in
(13)- Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
- On the tightness of SDP relaxations of QCQPs
- On standard quadratic programs with exact and inexact doubly nonnegative relaxations
- New SOCP relaxation and branching rule for bipartite bilinear programs
- Exactness criteria for SDP-relaxations of quadratic extremum problems
- Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
- Exactness of semidefinite relaxations for nonlinear optimization problems with underlying graph structure
- Further development in convex conic reformulation of geometric nonconvex conic optimization problems
- A vectorized positive semidefinite penalty method for unconstrained binary quadratic programming
- Rank-one matrix completion via high-rank matrices in sum-of-squares relaxations
- A slightly lifted convex relaxation for nonconvex quadratic programming with ball constraints
- Equivalent sufficient conditions for global optimality of quadratically constrained quadratic programs
- Verifying robustness of neural networks with tight semidefinite relaxations
This page was built for publication: Exact SDP relaxations for quadratic programs with bipartite graph structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6173960)
