Mirjam Dür
Copositive programming: a framework for quadratic and combinatorial optimization
Prof. Dr. Mirjam Dür
Department of Mathematics
University of Trier
Time & Place
The presentation on December 13, 2016 will be given in the Carnot-Gebäude G25 in Room 201 and starts at 5.00 p.m..
Abstract
A copositive optimization problem is a problem in matrix variables with a constraint which requires that the matrix be in the copositive cone. This means that its quadratic form takes nonnegative values over the nonnegative orthant. Many combinatorial problems like for example the maximum clique problem can be equivalently formulated as a copositive problem. Burer (2009) showed that also any nonconvex quadratic problem with linear constraints and binary variables can be reformulated as such a copositive problem. This is remarkable, since by this approach, a nonconvex problem is reformulated equivalently as a convex problem. The complexity of the original problem is entirely shifted into the cone constraint. We review recent progress in this area, concerning both theoretical results and numerical issues. In particular, we show how this approach can be used to deal with the stable set problem for infinite graphs, an application of which is the famous kissing number problem.
The lecture is part of the 10th CDS anniversary.