Journal article
Relaxing the optimality conditions of box QP
Computational optimization and applications, Vol.48(3), pp.653-673
04/01/2011
DOI: 10.1007/s10589-009-9273-2
Abstract
We present semidefinite relaxations of nonconvex, box-constrained quadratic programming, which incorporate the first- and second-order necessary optimality conditions, and establish theoretical relationships between the new relaxations and a basic semidefinite relaxation due to Shor. We compare these relaxations in the context of branch-and-bound to determine a global optimal solution, where it is shown empirically that the new relaxations are significantly stronger than Shor's. An effective branching strategy is also developed.
Details
- Title: Subtitle
- Relaxing the optimality conditions of box QP
- Creators
- Samuel Burer - University of IowaJieqiu Chen - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Computational optimization and applications, Vol.48(3), pp.653-673
- Publisher
- Springer Nature
- DOI
- 10.1007/s10589-009-9273-2
- ISSN
- 0926-6003
- eISSN
- 1573-2894
- Number of pages
- 21
- Grant note
- CCF-0545514 / NSF; National Science Foundation (NSF)
- Language
- English
- Date published
- 04/01/2011
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380459302771
Metrics
1 Record Views