Journal article
Optimizing a polyhedral-semidefinite relaxation of completely positive programs
Mathematical programming computation, Vol.2(1), pp.1-19
03/01/2010
DOI: 10.1007/s12532-010-0010-8
Abstract
It has recently been shown (Burer, Math Program 120: 479-495, 2009) that a large class of NP-hard nonconvex quadratic programs (NQPs) can be modeled as so-called completely positive programs, i.e., the minimization of a linear function over the convex cone of completely positive matrices subject to linear constraints. Such convex programs are NP-hard in general. A basic tractable relaxation is gotten by approximating the completely positive matrices with doubly nonnegative matrices, i.e., matrices which are both nonnegative and positive semidefinite, resulting in a doubly nonnegative program (DNP). Optimizing a DNP, while polynomial, is expensive in practice for interior-point methods. In this paper, we propose a practically efficient decomposition technique, which approximately solves the DNPs while simultaneously producing lower bounds on the original NQP. We illustrate the effectiveness of our approach for solving the basic relaxation of box-constrained NQPs (BoxQPs) and the quadratic assignment problem. For one quadratic assignment instance, a best-known lower bound is obtained. We also incorporate the lower bounds within a branch-and-bound scheme for solving BoxQPs and the quadratic multiple knapsack problem. In particular, to the best of our knowledge, the resulting algorithm for globally solving BoxQPs is the most efficient to date.
Details
- Title: Subtitle
- Optimizing a polyhedral-semidefinite relaxation of completely positive programs
- Creators
- Samuel Burer - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Mathematical programming computation, Vol.2(1), pp.1-19
- Publisher
- Springer Nature
- DOI
- 10.1007/s12532-010-0010-8
- ISSN
- 1867-2949
- eISSN
- 1867-2957
- Number of pages
- 19
- Grant note
- CCF-0545514 / NSF; National Science Foundation (NSF)
- Language
- English
- Date published
- 03/01/2010
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380479102771
Metrics
1 Record Views