• Speaker: Prof Levent Tunçel, University of Waterloo
  • Title: Lift-and-Project Methods: A meeting place for Combinatorial Optimization, Semidefinite Programming and Convex Algebraic Geometry
  • Location: Room V205, Mathematics Building (Callaghan Campus) The University of Newcastle
  • Access Grid Venue: RMIT
  • Time and Date: 4:00 pm, Fri, 11th Sep 2015
  • Abstract:

    Lift-and-Project operators (which map compact convex sets to compact convex sets in a certain contractive way, via higher dimensional convex representations of these sets) provide an automatic way for constructing all facets of the convex hull of 0,1 vectors in a polytope given by linear or polynomial inequalities. They also yield tractable approximations provided that the input polytope is tractable and that we only apply the operators O(1) times. There are many generalizations of the theory of these operators which can be used, in theory, to generate (eventually, in the limit) arbitrarily tight, convex relaxations of essentially arbitrary nonconvex sets. Moreover, Lift-and-Project methods provide universal ways of applying Semidefinite Programming techniques to Combinatorial Optimization problems, and in general, to nonconvex optimization problems.

    I will survey some of the developments (some recent, some not so recent) that I have been involved in, especially those utilizing Lift-and-Project methods and Semidefinite Optimization. I will touch upon the connections to Convex Algebraic Geometry and present various open problems.

  • [Permanent link]