Friday, February 27, 2009
3:30 pm, MC 5158

Levent Tunçel
University of Waterloo

Fundamentals of Convergence Theories for Convex Relaxation Hierarchies

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 arbitrarily tight, 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. Finally, I will show how to use these techniques to prove sum-of-squares type representation theorems for polynomials that are nonnegative over some compact set.