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.

Maximum Independent Set in H-free graphs
Théorie des graphes
Friday 05 October 2018 - 14h30
Salle : 445 - PCRI-N
Edouard BONNET
.............................................

A Family of Tractable Graph Distances
Gestion de données du Web
Wednesday 04 July 2018 - 10h30
Salle : 465 - PCRI-N
Stratis Ioannidis
.............................................