University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Tutte seminar - Levent TunçelExport this event to calendar

Friday, February 27, 2009 — 3:30 PM to 4:30 PM EST

Fundamentals of Convergence Theories for Convex Relaxation Hierarchies

Speaker: Levent Tunçel
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

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 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.

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
  1. 2020 (43)
    1. June (4)
    2. May (6)
    3. March (11)
    4. February (11)
    5. January (11)
  2. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  3. 2018 (138)
  4. 2017 (103)
  5. 2016 (137)
  6. 2015 (136)
  7. 2014 (88)
  8. 2013 (48)
  9. 2012 (39)
  10. 2011 (36)
  11. 2010 (40)
  12. 2009 (40)
  13. 2008 (39)
  14. 2007 (15)