[The University of Newcastle, Australia]
[CARMA logo]

Priority Research Centre for Computer-Assisted
Research Mathematics and its Applications



Subscribe to our seminar mailing list

Subscribe to our events calendar (iCal format)

CARMA-Sponsored Seminar Series: Colloquia, Seminars and More.

Last updated Wednesday, 23 Sep, 2015


[Note: events are listed by descending date.]
  • SMGS MATHS COLLOQUIA
  • 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 event link]

Copyright 2017. All rights reserved.
Copyright and Disclaimer
To report errors please contact the webmaster. Last modified:
Wed, 23 Sep, 2015 at 09:38