Journal article
A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations
Mathematical programming, Vol.113(2), pp.259-282
06/01/2008
DOI: 10.1007/s10107-006-0080-6
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.
Details
- Title: Subtitle
- A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations
- Creators
- Samuel Burer - University of IowaDieter Vandenbussche - Axioma
- Resource Type
- Journal article
- Publication Details
- Mathematical programming, Vol.113(2), pp.259-282
- Publisher
- Springer Nature
- DOI
- 10.1007/s10107-006-0080-6
- ISSN
- 0025-5610
- eISSN
- 1436-4646
- Number of pages
- 24
- Language
- English
- Date published
- 06/01/2008
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380555402771
Metrics
8 Record Views