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 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.

Citation

Argonne National Laboratory Mathematics and Computer Science Division Preprint ANL/MCS-P1837-0211

Article

Download

View Globally Solving Nonconvex Quadratic Programming Problems via Completely Positive Programming