On the Copositive Representation of Binary and Continuous Nonconvex Quadratic Programs

Samuel Burer (samuel-bureruiowa.edu)

Abstract: We establish that any nonconvex quadratic program having a mix of binary and continuous variables over a bounded feasible set can be represented as a linear program over the dual of the cone of copositive matrices. This result can be viewed as an extension of earlier separate results, which have established the copositive representation of a small collection of NP-hard problems.

Keywords:

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Global Optimization

Category 3: Integer Programming

Citation: Manuscript, Department of Management Sciences, University of Iowa, October 2006.

Download: [PDF]

Entry Submitted: 10/23/2006
Entry Accepted: 10/23/2006
Entry Last Modified: 07/25/2007

Modify/Update this entry