Tutte seminar - Antoine DezaExport this event to calendar

Friday, May 28, 2010 — 3:30 PM to 4:30 PM EDT

Optimization algorithms: worst-case behaviour and related conjectures

Speaker: Antoine Deza
Affiliation: McMaster University
Room: Mathematics & Computer Building (MC) 5158

Abstract:

The simplex and primal-dual interior point methods are currently the most computationally successful algorithms for linear optimization. While the simplex methods follow an edge path, the interior point methods follow the central path. Within this framework, the curvature of a polytope, defined as the largest possible total curvature of the associated central path, can be regarded as the continuous analogue of its diameter. In this talk we highlight links between the edge and central paths, and between the diameter and the curvature of a polytope. We recall continuous results of Dedieu-Malajovich-Shub, and discrete results of Holt-Klee and Klee-Walkup, as well as related conjectures such as the Hirsch conjecture which was disproved this month by Santos. We also present analogous results dealing with average and worst-case behaviour of the curvature and diameter of polytopes. 

This talk is partially based on joint work with David Bremner (New Brunswick), William Hua (McMaster), Lars Schewe (Darmstadt), Tamas Terlaky (Lehigh), Feng Xie (McMaster) and Yuriy Zinchenko (Calgary).

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

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
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
31
1
2
  1. 2019 (143)
    1. October (14)
    2. September (15)
    3. August (9)
    4. July (17)
    5. June (18)
    6. May (16)
    7. April (9)
    8. March (24)
    9. February (13)
    10. January (8)
  2. 2018 (138)
    1. December (2)
    2. November (18)
    3. October (14)
    4. September (9)
    5. August (2)
    6. July (10)
    7. June (13)
    8. May (17)
    9. April (9)
    10. March (19)
    11. February (14)
    12. January (11)
  3. 2017 (103)
  4. 2016 (137)
  5. 2015 (136)
  6. 2014 (88)
  7. 2013 (48)
  8. 2012 (39)
  9. 2011 (36)
  10. 2010 (40)
  11. 2009 (40)
  12. 2008 (39)
  13. 2007 (15)