Stefan Bundfuss

(TU Darmstadt, Germany)

Copositive Programming - Applications and Algorithms

Thursay 15 October 2009, 15.00-16.00

5161.0105 (Bernoulliborg)

Abstract:

Many difficult optimization problems like the quadratic assignment problem, which arises in location theory, graph partitioning problems, the max clique problem, nonconvex quadratic programming, and quadratic mixed-binary programming can be reformulated as linear programs over the cone of copositive matrices. The difficulty in this formulation lies in the description of the copositive cone. We propose new polyhedral approximations of the copositive cone which we show to be exact in the limit. We derive necessary and sufficient criteria for copositivity which leads to an adaptive linear approximation algorithm. A generalization of our approach yields semidefinite approximations. We conclude by presenting numerical results of our algorithms.

This is joint work with Mirjam Dür.