Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs
From MaRDI portal
Publication:2188238
Abstract: We study a class of quadratically constrained quadratic programs (QCQPs), called {em diagonal QCQPs/}, which contain no off-diagonal terms for , and we provide a sufficient condition on the problem data guaranteeing that the basic Shor semidefinite relaxation is exact. Our condition complements and refines those already present in the literature and can be checked in polynomial time. We then extend our analysis from diagonal QCQPs to general QCQPs, i.e., ones with no particular structure. By reformulating a general QCQP into diagonal form, we establish new, polynomial-time-checkable sufficient conditions for the semidefinite relaxations of general QCQPs to be exact. Finally, these ideas are extended to show that a class of random general QCQPs has exact semidefinite relaxations with high probability as long as the number of constraints grows no faster than a fixed polynomial in the number of variables. To the best of our knowledge, this is the first result establishing the exactness of the semidefinite relaxation for random general QCQPs.
Recommendations
- Correction to: ``Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs
- Nonconvex quadratic programming, semidefinite relaxations and randomization algorithms in information and decision systems
- Approximating non-convex quadratic programs by semidefinite and copositive programming
- scientific article; zbMATH DE number 1380758
- Semidefinite programming relaxation for nonconvex quadratic programs
- Further Results on Approximating Nonconvex Quadratic Optimization by Semidefinite Programming Relaxation
- Semidefinite approximation bound for a class of nonhomogeneous nonconvex quadratically constrained quadratic programming problem
- Semidefinite relaxation and nonconvex quadratic optimization
- Complexity and nonlinear semidefinite programming reformulation of \(\ell_1\)-constrained nonconvex quadratic optimization
Cites work
- scientific article; zbMATH DE number 4070633 (Why is no real title available?)
- A branch and bound algorithm for nonconvex quadratic optimization with ball and linear constraints
- A gentle, geometric introduction to copositive optimization
- A new graph parameter related to bounded rank positive semidefinite matrix completions
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
- Approximating quadratic programming with bound and quadratic constraints
- Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems
- Conditions for correct sensor network localization using SDP relaxation
- Exactness of semidefinite relaxations for nonlinear optimization problems with underlying graph structure
- Finding low-rank solutions of sparse linear matrix inequalities using convex optimization
- Geometry of cuts and metrics
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- Handbook on semidefinite, conic and polynomial optimization
- New Results on Quadratic Minimization
- On Cones of Nonnegative Quadratic Functions
- On the average number of steps of the simplex method of linear programming
- On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues
- Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
- Polynomial Solvability of Variants of the Trust-Region Subproblem
- Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
- Probabilistic analysis of an infeasible-interior-point algorithm for linear programming
- Probabilistic analysis of the semidefinite relaxation detector in digital communications
- Problems of distance geometry and convex properties of quadratic maps
- Quadratic programs with hollows
- Second-order-cone constraints for extended trust-region subproblems
- Semidefinite optimization
- Semidefinite programming relaxation for nonconvex quadratic programs
- Smoothed analysis of algorithms
- Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
- Toward Probabilistic Analysis of Interior-Point Algorithms for Linear Programming
Cited in
(26)- The equivalence of optimal perspective formulation and Shor's SDP for quadratic programs with indicator variables
- On indefinite quadratic optimization over the intersection of balls and linear constraints
- An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization
- Invariants of SDP exactness in quadratic programming
- Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
- On Convex Hulls of Epigraphs of QCQPs
- On the exactness of a simple relaxation for the extended Celis–Dennis–Tapia subproblem
- (Global) optimization: historical notes and recent developments
- On obtaining the convex hull of quadratic inequalities via aggregations
- Exact SDP relaxations for quadratic programs with bipartite graph structures
- On the local stability of semidefinite relaxations
- Quadratic maximization of reachable values of affine systems with diagonalizable matrix
- On sparsity of the solution to a random quadratic optimization problem
- On the tightness of SDP relaxations of QCQPs
- On exact and inexact RLT and SDP-RLT relaxations of quadratic programs with box constraints
- Correction to: ``Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs
- Finite convergence of sum-of-squares hierarchies for the stability number of a graph
- Penalized semidefinite programming for quadratically-constrained quadratic optimization
- Outcome-space branch-and-bound outer approximation algorithm for a class of non-convex quadratic programming problems
- Projectively and Weakly Simultaneously Diagonalizable Matrices and their Applications
- KKT-based primal-dual exactness conditions for the Shor relaxation
- Aggregations of Quadratic Inequalities and Hidden Hyperplane Convexity
- Convex hull results on quadratic programs with non-intersecting constraints
- Polynomial optimization: tightening RLT-based branch-and-bound schemes with conic constraints
- Accelerated first-order methods for a class of semidefinite programs
- Cutting plane generation through sparse principal component analysis
This page was built for publication: Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2188238)
