Paper Info
Title
A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations
Abstract
Existing global optimization techniques for nonconvex quadratic programming (QP) branch by recursively partitioning the convex feasible set and thus generate an infinite number of branch-and-bound nodes. An open question of theoretical interest is how to develop a finite branch-and-bound algorithm for nonconvex QP. One idea, which guarantees a finite number of branching decisions, is to enforce the first-order Karush-Kuhn-Tucker (KKT) conditions through branching. In addition, such an approach naturally yields linear programming (LP) relaxations at each node. However, the LP relaxations are unbounded, a fact that precludes their use. In this paper, we propose and study semidefinite programming relaxations, which are bounded and hence suitable for use with finite KKT-branching. Computational results demonstrate the practical effectiveness of the method, with a particular highlight being that only a small number of nodes are required.
Year
DOI
Venue
2008
10.1007/s10107-006-0080-6
Math. Program.
Keywords
Field
DocType
finite number,nonconvex quadratic programming,linear programming,nonconcave quadratic maximization · nonconvex quadratic programming · branch-and-bound · lift-and-project relaxations · semidefinite programming,study semidefinite programming relaxation,finite kkt-branching,finite branch-and-bound algorithm,semidefinite relaxation,lp relaxation,small number,infinite number,branch-and-bound node,non linear programming,recursive partitioning,branch and bound,subdivision,quadratic programming,ramification,semidefinite programming,karush kuhn tucker,branching,first order,convex set,global optimization,quadratic program,global optimum,linear program,mathematical programming,branch and bound algorithm,semi definite programming
Mathematical optimization,Branch and bound,Global optimization,Nonlinear programming,Feasible region,Linear programming,Quadratic programming,Karush–Kuhn–Tucker conditions,Semidefinite programming,Mathematics
Journal
Volume
Issue
ISSN
113
2
1436-4646
Citations 
PageRank 
References 
54
2.43
16
Authors
2
Name
Order
Citations
PageRank
Samuel Burer1114873.09
Dieter Vandenbussche232417.00