ORIE Colloquium: Stephen Wright (Wisconsin-Madison) - Methods for finding second-order points in nonconvex optimization with complexity guarantees

Description

Widely used algorithms for smooth nonconvex optimization problems—unconstrained, bound-constrained, and general equality-constrained—can be modified slightly to ensure that approximate first- and second-order optimal points are found, with complexity guarantees that depend on the desired accuracy. We discuss methods constructed from Newton's method, conjugate gradients, randomized Lanczos, trust-region frameworks, log-barrier, and augmented Lagrangians. We derive upper bounds on various measures of complexity in terms of the tolerances required. Our methods use Hessian information only in the form of Hessian-vector products—an operation that does not require the Hessian itself to be evaluated or stored explicitly.

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 data science and many other 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-2001). He has served as Chair of the Mathematical Optimization Society (2007-2010) and as a Trustee of SIAM for the maximum three terms (2005-2014). He is a Fellow of SIAM. In 2014, he won the W.R.G. Baker Award from IEEE for best paper in an IEEE archival publication during the three years 2009-2011. He was awarded the Khachiyan Prize by the INFORMS Optimization Society in 2020 for lifetime achievements in optimization. Prof. Wright is the author/coauthor of widely used text and reference books in optimization including "Primal Dual Interior-Point Methods" and "Numerical Optimization". He has published widely on optimization theory, algorithms, software, and applications. Prof. Wright served from 2014-2019 as Editor-in-Chief of the SIAM Journal on Optimization and previously served as Editor-in-Chief of Mathematical Programming Series B. He has also served as Associate Editor of Mathematical Programming Series A, SIAM Review, SIAM Journal on Scientific Computing, and several other journals and book series.