 SMGS MATHS COLLOQUIA
 Speaker: Prof Levent TunĂ§el, University of Waterloo
 Title: LiftandProject 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, 11^{th} Sep 2015
 Abstract:
LiftandProject 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, LiftandProject 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 LiftandProject methods and Semidefinite Optimization. I will touch upon the connections to Convex Algebraic Geometry and present various open problems.
 [Permanent link]
