This paper presents a branch-and-bound algorithm for nonconvex quadratic programming, which is based on solving semidefinite relaxations at each node of the enumeration tree. The method is motivated by a recent branch-and-cut approach for the box-constrained case that employs linear relaxations of the first-order KKT conditions. We discuss certain limitations of linear relaxations when handling general constraints and instead propose semidefinite relaxations of the KKT conditions, which do not suffer from the same drawbacks. Computational results demonstrate the effectiveness of the method, with a particular highlight being that only a small number of branch-and-bound nodes are required. Furthermore, specialization to the box-constrained case yields a state-of-the-art method for globally solving this class of problems.
Citation
Manuscript, Department of Mechanical and Industrial Engineering, University of Illinois at Urbana-Champaign, June 2005.