Journal article
ON NONCONVEX QUADRATIC PROGRAMMING WITH BOX CONSTRAINTS
SIAM journal on optimization, Vol.20(2), pp.1073-1089
01/01/2009
DOI: 10.1137/080729529
Abstract
Nonconvex quadratic programming with box constraints is a fundamental NP-hard global optimization problem. Recently, some authors have studied a certain family of convex sets associated with this problem. We prove several fundamental results concerned with these convex sets: we determine their dimension, characterize their extreme points and vertices, show their invariance under certain a. ne transformations, and show that various linear inequalities induce facets. We also show that the sets are closely related to the Boolean quadric polytope, a fundamental polytope in the field of polyhedral combinatorics. Finally, we give a classification of valid inequalities and show that this yields a finite recursive procedure to check the validity of any proposed inequality.
Details
- Title: Subtitle
- ON NONCONVEX QUADRATIC PROGRAMMING WITH BOX CONSTRAINTS
- Creators
- Samuel Burer - samuel-burer@uiowa.eduAdam N. Letchford - Lancaster University Ghana
- Resource Type
- Journal article
- Publication Details
- SIAM journal on optimization, Vol.20(2), pp.1073-1089
- Publisher
- Siam Publications
- DOI
- 10.1137/080729529
- ISSN
- 1052-6234
- eISSN
- 1095-7189
- Number of pages
- 17
- Grant note
- EP/F033613/1 / Engineering and Physical Sciences Research Council; UK Research & Innovation (UKRI); Engineering & Physical Sciences Research Council (EPSRC) CCF-0545514 / National Science Foundation; National Science Foundation (NSF) EP/D072662/1 / Engineering and Physical Sciences Research Council; UK Research & Innovation (UKRI); Engineering & Physical Sciences Research Council (EPSRC) EP/D072662/1 / EPSRC; UK Research & Innovation (UKRI); Engineering & Physical Sciences Research Council (EPSRC)
- Language
- English
- Date published
- 01/01/2009
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380425502771
Metrics
3 Record Views