Journal article
Globally solving nonconvex quadratic programming problems via completely positive programming
Mathematical programming computation, Vol.4(1), pp.33-52
03/01/2012
DOI: 10.1007/s12532-011-0033-9
Abstract
Nonconvex quadratic programming (QP) is an NP-hard problem that optimizes a general quadratic function over linear constraints. This paper introduces a new global optimization algorithm for this problem, which combines two ideas from the literature-finite branching based on the first-order KKT conditions and polyhedralsemidefinite relaxations of completely positive (or copositive) programs. Through a series of computational experiments comparing the new algorithm with existing codes on a diverse set of test instances, we demonstrate that the new algorithm is an attractive method for globally solving nonconvex QP.
Details
- Title: Subtitle
- Globally solving nonconvex quadratic programming problems via completely positive programming
- Creators
- Jieqiu Chen - Argonne National LaboratorySamuel Burer - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Mathematical programming computation, Vol.4(1), pp.33-52
- Publisher
- Springer Nature
- DOI
- 10.1007/s12532-011-0033-9
- ISSN
- 1867-2949
- eISSN
- 1867-2957
- Number of pages
- 20
- Grant note
- U.S. Government DE-AC02-06CH11357 / U.S. Department of Energy; United States Department of Energy (DOE) CCF-0545514 / NSF; National Science Foundation (NSF) DE-AC02-06CH11357 / Office of Advanced Scientific Computing Research, Office of Science, U.S. Department of Energy; United States Department of Energy (DOE)
- Language
- English
- Date published
- 03/01/2012
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380552602771
Metrics
9 Record Views