Magdeburg Lectures on Optimization and Control: Copositive programming: a framework for quadratic and combinatorial optimization

Magdeburg Lectures on Optimization and Control: Copositive programming: a framework for quadratic and combinatorial optimization

  • Datum: 13.12.2016
  • Uhrzeit: 17:00 - 19:00
  • Vortragende(r): Prof. Dr. Mirjam Dür, Department of Mathematics University of Trier
  • Ort: Carnot-Gebäude G25 in Room 201
  • Gastgeber: The lecture is part of the 10th CDS anniversary.

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.

Zur Redakteursansicht