Journal article
Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs
Mathematical programming, Vol.181(1), pp.1-17
05/2020
DOI: 10.1007/s10107-019-01367-2
Abstract
We study a class of quadratically constrained quadratic programs (QCQPs), called diagonal QCQPs, which contain no off-diagonal terms xjxk for j≠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, 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.
Details
- Title: Subtitle
- Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs
- Creators
- Samuel Burer - University of IowaYinyu Ye - Stanford University
- Resource Type
- Journal article
- Publication Details
- Mathematical programming, Vol.181(1), pp.1-17
- DOI
- 10.1007/s10107-019-01367-2
- ISSN
- 0025-5610
- eISSN
- 1436-4646
- Language
- English
- Date published
- 05/2020
- Academic Unit
- Business Analytics
- Record Identifier
- 9984083813102771
Metrics
34 Record Views