Building a completely positive factorization

Immanuel Bomze (immanuel.bomzeunivie.ac.at)

Abstract: Using a bordering approach, and building upon an already known factorization of a principal block, we establish sufficient conditions under which we can extend this factorization to the full matrix. Simulations show that the approach is promising also in higher dimensions, provided there is no gap in the cp-rank. We expect that this property is shared by good quality approximation solutions obtained by the usual conic (semidefinite) relaxation procedures in copositive programming for combinatorial optimization applications.

Keywords: Copositive programming, semidefinite relaxation, mixed-binary quadratic optimization

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

Citation: Technical Report TR-ISDS {\bf 2009-06}, Department of Statistics and Decision Support Systems, University of Vienna, Austria (August 2009).

Download: [PDF]

Entry Submitted: 08/21/2009
Entry Accepted: 08/21/2009
Entry Last Modified: 03/14/2010

Modify/Update this entry