Mathematical Programming Computation, Volume 4, Number 1, March 2012

Font Size:  Small  Medium  Large

Globally solving nonconvex quadratic programming problems via completely positive programming

Jieqiu Chen, Samuel Burer

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

Full Text: PDF

mpc footer
© MPS 2008-2012