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

Bio: Stephen J. Wright holds the George B. Dantzig Professorship, the Sheldon Lubar Chair, and the Amar and Balinder Sohi Professorship of Computer Sciences at the University of Wisconsin-Madison. His research is in computational optimization and its applications to many areas of science and engineering. Prior to joining UW-Madison in 2001, Wright held positions at North Carolina State University (1986-90), Argonne National Laboratory (1990-2001), and the University of Chicago (2000-01). He has served as Chair of the Mathematical Optimization Society, and Trustee of SIAM. He is also a Fellow of SIAM. In 2014, he won the W.R.G. Baker award from IEEE. Wright is the author and coauthor of widely used text/reference books in optimization, including Primal Dual Interior-Point Methods, and Numerical Optimization. He has published widely on optimization theory, algorithms, software, and applications. Wright is current editor-in-chief of the SIAM Journal on Optimization, and previously served variously as editor-in-chief or associate editor of Mathematical Programming (Series A), Mathematical Programming (Series B), SIAM Review, SIAM Journal on Scientific Computing, and several other journals and book series.