Globally solving nonconvex quadratic programming problems via completely positive programming
- 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.
Metadaten| Author: | Jieqiu Chen, Samuel Burer |
|---|
| DOI: | https://doi.org/10.1007/s12532-011-0033-9 |
|---|
| ISSN: | 1867-2949 |
|---|
| Parent Title (English): | Mathematical Programming Computation |
|---|
| Publisher: | Springer Science and Business Media LLC |
|---|
| Document Type: | Article |
|---|
| Language: | English |
|---|
| Year of Completion: | 2011 |
|---|
| Tag: | Software; Theoretical Computer Science |
|---|
| Volume: | 4 |
|---|
| Issue: | 1 |
|---|
| Page Number: | 20 |
|---|
| First Page: | 33 |
|---|
| Last Page: | 52 |
|---|
| Mathematical Programming Computation : | MPC 2012 - Issue 1 |
|---|