Semidefinite-Based Branch-and-Bound for Nonconvex Quadratic Programming
Samuel Burer (samuel-bureruiowa.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.
Entry Submitted: 06/27/2005
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|