|
Friday, May 28, 2010 |
|
|
|
|
Optimization algorithms: worst-case behaviour and related conjectures |
|
|
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. |