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.

%B Mathematical Programming Computation %V 4 %8 03/2012 %G eng %U http://mpc.zib.de/index.php/MPC/article/view/79 %N 1 %1 http://www.mcs.anl.gov/papers/P1967-1011.pdf