Optimization Online


Exact Semidefinite Formulations for a Class of (Random and Non-Random) Nonconvex Quadratic Programs

Samuel Burer (samuel-burer***at***uiowa.edu)
Yinyu Ye (yinyu-ye***at***stanford.edu)

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 $j \ne k$, 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 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 variables is significantly larger than the number of constraints. To the best of our knowledge, this is the first result establishing the exactness of the semidefinite relaxation for random general QCQPs.

Keywords: quadratically constrained quadratic programming, semidefinite relaxation, low-rank solutions

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Global Optimization (Theory )

Citation: Manuscript, Department of Management Sciences, University of Iowa, Feb 2018.

Download: [PDF]

Entry Submitted: 02/07/2018
Entry Accepted: 02/07/2018
Entry Last Modified: 11/07/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society