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.