Quadratic factorization heuristics for copositive programming

Immanuel M. Bomze(immanuel.bomzeunivie.ac.at)
Florian Jarre(jarreopt.uni-duesseldorf.de)
Franz Rendl(rendluni-klu.ac.at)

Abstract: Copositive optimization problems are particular conic programs: extremize linear forms over the copositive cone subject to linear constraints. Every quadratic program with linear constraints can be formulated as a copositive program, even if some of the variables are binary. So this is an NP-hard problem class. While most methods try to approximate the copositive cone from within, we propose a method which approximates this cone from outside. This is achieved by passing to the dual problem, where the feasible set is an affine subspace intersected with the cone of completely positive matrices, and this cone is approximated from within. We consider feasible descent directions in the completely positive cone, and regularized strictly convex subproblems. In essence, we replace the intractable completely positive cone with a nonnegative cone, at the cost of a series of nonconvex quadratic subproblems. Proper adjustment of the regularization parameter results in short steps for the nonconvex quadratic programs. This suggests to approximate their solution by standard linearization techniques. Preliminary numerical results on three different classes of test problems are quite promising.

Keywords: Combinatorial optimization, copositive programs, clique number

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

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Global Optimization (Other )

Citation: Technical Report TR 2009-08, Oct. 2009. Institut fuer Statistik und Decision Support Systems, Universitaet Wien, Austria

Download: [Postscript][PDF]

Entry Submitted: 10/14/2009
Entry Accepted: 10/14/2009
Entry Last Modified: 10/14/2009

Modify/Update this entry