Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs

DOI10.1007/S10107-019-01367-2zbMATH Open1445.90073arXiv1802.02688OpenAlexW2963227682WikidataQ128448972 ScholiaQ128448972MaRDI QIDQ2188238FDOQ2188238

Authors: Samuel Burer, Yinyu Ye 

Publication date: 10 June 2020

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: We study a class of quadratically constrained quadratic programs (QCQPs), called {em diagonal QCQPs/}, which contain no off-diagonal terms $x_j{x}_k$ for $jek$, 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.

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

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

zbMATH Keywords

semidefinite relaxationquadratically constrained quadratic programminglow-rank solutions

Mathematics Subject Classification ID

Quadratic programming (90C20) Nonconvex programming, global optimization (90C26) Semidefinite programming (90C22)

Cites Work

• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Semidefinite optimization
• Title not available (Why is that?)
• New Results on Quadratic Minimization
• On Cones of Nonnegative Quadratic Functions
• Geometry of cuts and metrics
• Second-Order-Cone Constraints for Extended Trust-Region Subproblems
• Problems of distance geometry and convex properties of quadratic maps
• On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues
• Smoothed analysis of algorithms
• Handbook on semidefinite, conic and polynomial optimization
• A gentle, geometric introduction to copositive optimization
• A new graph parameter related to bounded rank positive semidefinite matrix completions
• Semidefinite programming relaxation for nonconvex quadratic programs
• Conditions for Correct Sensor Network Localization Using SDP Relaxation
• Approximating quadratic programming with bound and quadratic constraints
• Exactness of Semidefinite Relaxations for Nonlinear Optimization Problems with Underlying Graph Structure
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• Title not available (Why is that?)
• Probabilistic analysis of an infeasible-interior-point algorithm for linear programming
• On the average number of steps of the simplex method of linear programming
• Toward Probabilistic Analysis of Interior-Point Algorithms for Linear Programming
• Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems
• A branch and bound algorithm for nonconvex quadratic optimization with ball and linear constraints
• Polynomial Solvability of Variants of the Trust-Region Subproblem
• Finding Low-rank Solutions of Sparse Linear Matrix Inequalities using Convex Optimization
• A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
• Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
• Quadratic programs with hollows

Cited In (25)

• Cutting Plane Generation through Sparse Principal Component Analysis
• Aggregations of Quadratic Inequalities and Hidden Hyperplane Convexity
• Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
• On sparsity of the solution to a random quadratic optimization problem
• 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
• An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization
• On the tightness of SDP relaxations of QCQPs
• Penalized semidefinite programming for quadratically-constrained quadratic optimization
• Quadratic maximization of reachable values of affine systems with diagonalizable matrix
• Projectively and Weakly Simultaneously Diagonalizable Matrices and their Applications
• Invariants of SDP exactness in quadratic programming
• On exact and inexact RLT and SDP-RLT relaxations of quadratic programs with box constraints
• 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
• On the exactness of a simple relaxation for the extended Celis–Dennis–Tapia subproblem
• On Convex Hulls of Epigraphs of QCQPs
• 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
• Polynomial optimization: tightening RLT-based branch-and-bound schemes with conic constraints
• Accelerated first-order methods for a class of semidefinite programs
• (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
• Convex hull results on quadratic programs with non-intersecting constraints

Uses Software

• SDPLR
• PhaseLift

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)