Publications

J. Chen and S. Burer, "Globally Solving Nonconvex QPs via Completely Positive Programming," Mathematical Programming Computation, vol. 4, Mathematical Prog. Comp., 2011, pp. 33-52. Also Preprint ANL/MCS-P1837-0211, February 2011. [pdf]

Nonconvex quadratic programming 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|nite branching based on the first-order KKT conditions and polyhedral-semidefinite 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.