Globally solving nonconvex quadratic programming problems via completely positive programming |
| |
Authors: | Jieqiu Chen Samuel Burer |
| |
Institution: | 1.Mathematics and Computer Science Division,Argonne National Laboratory,Argonne,USA;2.Department of Management Sciences,University of Iowa,Iowa City,USA |
| |
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 polyhedral-semidefinite 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|