Evaluation Complexity of Algorithms for Nonconvex Optimization: Theory, Computation, and Perspectives

A popular way to assess the “effort” needed to solve a problem is to count how many evaluations of the problem functions (and their derivatives) are required. In many cases, this is often the dominating computational cost. Given an optimization problem satisfying reasonable assumptions―and given access to problem-function values and derivatives of various degrees―how many evaluations might be required to approximately solve the problem? Evaluation Complexity of Algorithms for Nonconvex Optimization: Theory, Computation, and Perspectives addresses this question for nonconvex optimization problems, those that may have local minimizers and appear most often in practice. This is the first book on complexity to cover topics such as composite and constrained optimization, derivative-free optimization, subproblem solution, and optimal (lower and sharpness) bounds for nonconvex problems. It is also the first to address the disadvantages of traditional optimality measures and propose useful surrogates leading to algorithms that compute approximate high-order critical points, and to compare traditional and new methods, highlighting the advantages of the latter from a complexity point of view. This is the go-to book for those interested in solving nonconvex optimization problems. It is suitable for advanced undergraduate and graduate students in courses on advanced numerical analysis, data science, numerical optimization, and approximation theory.

Coralia Cartis is Professor of Numerical Optimization at the Mathematical Institute, University of Oxford, and a Fellow of Balliol College and The Alan Turing Institute. Her research interests include the development and analysis of nonlinear optimization algorithms and diverse applications of optimization from climate modeling to signal processing and machine learning. Nicholas I. M. Gould is a Senior Fellow at the STFC-Rutherford Appleton Laboratory in Oxfordshire and a visiting professor at the Universities of Edinburgh and Oxford. His research interests include the theory and practice of optimization methods, numerical linear algebra, large-scale scientific computation, and the links between these fields. Philippe L. Toint is Professor Emeritus at the University of Namur and has been the co-director of the Numerical Analysis Unit and director of the Transportation Research Group there. He is also past chairman of the Mathematical Optimization Society (MOS). His research interests include numerical optimization, numerical analysis, and transportation.