Caltech Logo

H.B. Keller Colloquium

Monday, May 24, 2021
4:00pm to 5:00pm
Add to Cal
Online Event
The Role of Complexity Bounds in Optimization
Stephen Wright, Professor, Computer Sciences Department, University of Wisconsin-Madison,

Complexity analysis in optimization seeks upper bounds on the amount of work required to find approximate solutions of problems in a given class with a given algorithm, and also lower bounds, usually in the form of a worst-case example from a given problem class as regards the work required by a particular class of algorithms. The relationship between theoretical complexity bounds and practical performance of algorithms on "typical" problems varies widely across problem and algorithm classes, and relative interest among researchers between these two aspects of algorithm design and analysis has waxed and waned over the years. This talk surveys complexity analysis and its relationship to practice in optimization, with an emphasis on linear programming and convex and nonconvex nonlinear optimization, providing historical (and cultural) perspectives on research in these areas.

For more information, please contact Diana Bohler by phone at 6262326138 or by email at [email protected].