Optimization and Systems Theory Minicourse
Wednesday, June 2, 1999, 15.15-17.00, Room 3733, Lindstedtsv. 25
Thursday, June 3, 13.15-15.00, Room 3733, Lindstedtsv. 25
Friday, June 4, 9.15-11.00, Room 3733, Lindstedtsv. 25
Claude Lemaréchal
INRIA
Grenoble, France
Lagrangian duality and SDP relaxation in combinatorial
optimization
The aim of the tutorial is to overview the SDP relaxation technique for
some combinatorial problems, and to embed it in a more general
framework:
Lagrangian duality.
We will start from two well-known instances: the max-cut and
max-stable problems. We will show how their SDP relaxations can be
recovered as Lagrangian (bi-)duals. This allows us to generalize the
approach to large classes of combinatorial problems. We construct
tight SDP relaxations of them, which for which we compare with the
classical - or linear - Lagrangian relaxation.
Calendar of seminars
Last update: June 2, 1999 by
Anders Forsgren,
anders.forsgren@math.kth.se.