Optimization Online


Optimizing a Polyhedral-Semidefinite Relaxation of Completely Positive Programs

Samuel Burer (samuel-burer***at***uiowa.edu)

Abstract: It has recently been shown (Burer, 2006) that a large class of NP-hard nonconvex quadratic programs (NQPs) can be modeled as so-called completely positive programs (CPPs), i.e., the minimization of a linear function over the convex cone of completely positive matrices subject to linear constraints. Such convex programs are necessarily NP-hard. 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 (IPMs). In this paper, we propose a decomposition technique, which approximately solves the DNPs in a practically efficient manner, while simultaneously producing lower bounds on the original NQP. Our method is inspired by, but different from, a related decomposition technique of Burer and Vandenbussche (2006). Compared to IPMs and Burer-Vandenbussche, we illustrate the effectiveness of our approach for solving the basic relaxation of box-constrained NQPs (BoxQPs) and the quadratic assignment problem. For a few quadratic assignment instances, best-known lower bounds are 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.

Keywords: nonconvex quadratic program, relaxation, linear programming, semidefinite programming, decomposition

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Global Optimization

Citation: Technical report, Department of Management Sciences, University of Iowa, December 2008.

Download: [PDF]

Entry Submitted: 12/25/2008
Entry Accepted: 01/08/2009
Entry Last Modified: 11/03/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society