[Colloquium] Michael Shub Talk - 9/18 at TTI-C

[Meridel Trimble]

TOYOTA TECHNOLOGICAL INSTITUTE TALK
 
Speaker: Michael Shub                                              
TJ Watson Research Center 
IBM                                                                    
http://www.research.ibm.com/people/s/shub/
Title: Linear Programming, Dynamical Systems and Integral Geometry

Date: September 18th, 2003
Time: 12:45pm
Place: TTI-C’s Conference Room (The Press Building - 1427 E. 60th St.)

*FREE LUNCH PROVIDED*

Abstract: Interior point methods in linear programming theory 
frequently "follow" the "central path" which is a solution curve of the Newton 
vector field associated to the logarithmic barrier function. Motivated by the 
question of whether or not there is a strongly polynomial algorithm for linear 
programming, we study the dynamics of these vector fields and the curvature of 
the solutions. With tools from integral geometry, we prove that on 
the "average" the curvature of these solution curves is "small". We study the 
behavior of these vector fields near the boundary. The dynamics suggests that 
the curvature is even smaller. Small curvature may help explain why straight 
line approximations to the solution curves 
work well in practice. 

This is joint work with Jean-Pierre Dedieu.

Please contact Meridel Trimble for further information
(mtrimble at tti-c.org/773.834.9873)