Fall 2008 Seminar Series

DATE: December 4, 2008
LOCATION: E51-063
TIME: 4:15pm
Reception immediately following in the ORC ConferenceRoom, E40-106

SPEAKER:
Levent Tuncel

TITLE
Fundamentals of Convergence Theories for Convex Relaxation

ABSTRACT
Lift-and-project operators 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 these operators which can be used to generate convex relaxations of essentially arbitrary nonconvex sets.

 

I will quickly review the above-mentioned methods and then focus on the main techniques used in providing convergence theories for various convex relaxation hierarchies. I will discuss the relationships among the various techniques when the hierarchies are applied to polynomial optimization problems.