04 May 2012, 10h30 - 04 May 2012, 11h30 Salle/Bat : 435/PCRI-N
Contact :

Activités de recherche :

Résumé :

Copositive programming can be seen as a generalization of semidefinite programming, since it means optimizing over the cone of so called copositive matrices. A matrix is called copositive if its quadratic form takes nonnegative values on the nonnegative orthant. Obviously, every positive semidefinite matrix is copositive, and so is every entrywise nonnegative matrix, but the copositive cone is significantly larger than both the semidefinite and the nonnegative matrix cones.

Similar to SDP, copositive programs play a role in combinatorial and quadratic optimization. In contrast to SDP, however, in many cases copositive programs provide exact reformulations rather than relaxations. This fact has led to new approaches to combinatorial problems like max clique, QAP, graph partitioning, and graph coloring problems, as well as to certain nonconvex quadratic problems.

The talk will give an introduction to this rather young field of research. We will discuss properties of the copositive cone and its dual, the so-called completely positive cone. We will give an overview on problem classes that can be treated as copositive problems, and discuss various solution approaches to solve copositive programs.