Argonne National Laboratory

Globally Solving Nonconvex Quadratic Programming Problems via Completely Positive Programming

TitleGlobally Solving Nonconvex Quadratic Programming Problems via Completely Positive Programming
Publication TypeJournal Article
Year of Publication2012
AuthorsChen, J, Burer, S
JournalMathematical Programming Computation
Volume4
Issue1
Date Published03/2012
Other NumbersANL/MCS-P1967-1011
AbstractNonconvex 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.  
URLhttp://mpc.zib.de/index.php/MPC/article/view/79
PDFhttp://www.mcs.anl.gov/papers/P1967-1011.pdf