Semidefinite-Based Branch-and-Bound for Nonconvex Quadratic Programming

Samuel Burer (samuel-bureruiowa.edu)
Dieter Vandenbussche (dietervuiuc.edu)

Abstract: 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.

Keywords: Nonconcave quadratic maximization, nonconvex quadratic programming, branch-and-bound, lift-and-project relaxations, semidefinite programming

Category 1: Global Optimization

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Nonlinear Optimization (Quadratic Programming )

Citation: Manuscript, Department of Mechanical and Industrial Engineering, University of Illinois at Urbana-Champaign, June 2005.

Download: [PDF]

Entry Submitted: 06/27/2005
Entry Accepted: 07/01/2005
Entry Last Modified: 06/27/2005

Modify/Update this entry