Optimization Online


A note on Burer's copositive representation of mixed-binary QPs

Immanuel Bomze (immanuel.bomze***at***univie.ac.at)
Florian Jarre (jarre***at***opt.uni-duesseldorf.de)

Abstract: In an important paper, Burer recently showed how to reformulate general mixed-binary quadratic optimization problems (QPs) into copositive programs where a linear functional is minimized over a linearly constrained subset of the cone of completely positive matrices. In this note we interpret the implication from a topological point of view, showing that the Minkowski sum of the lifted feasible set and the lifted recession cone gives exactly the closure of the former. We also discuss why feasibility of the copositive program implies feasibility of the original mixed-binary QP, which can be derived from the arguments in Burer's article without any further condition.

Keywords: copositive programming

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Linear, Cone and Semidefinite Programming (Other )

Citation: Technical Report TR-ISDS 2009-04, Department of Statistics and Decision Support Systems, University of Vienna, Austria (August 2009)

Download: [PDF]

Entry Submitted: 08/10/2009
Entry Accepted: 08/10/2009
Entry Last Modified: 09/27/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