ORC Seminar: On Complexity of Derivative-Free Optimization

About this event

Katya Scheinberg Professor Georgia Tech Abstract: In many applications of mathematical optimization, one may wish to optimize an objective function without access to its derivatives (gradients). These situations call for derivative-free optimization (DFO) methods. Among the most successful approaches in practice are model-based trust-region methods, such as those pioneered by M.J.D Powell. These methods rely on function approximations via low degree polynomials and carefully adapt the local geometry of interpolation points to balance exploration and exploitation. While relatively complex to implement, these methods are now available in standard scientific computing platforms, including MATLAB and SciPy. However, theoretical analysis of their computational complexity lagged behind practice. In particular, it is important to bound the number of function evaluations required to achieve a desired level of accuracy. Using a mix of handy concepts from approximation, sample set geometry, Lagrangian interpolation and linear algebra we systematically derive complexity bounds for classical model-based trust-region methods and their modern variations. We establish, for the first time, that these methods can have the same worst case complexity than any other known DFO method. Bio: Katya Scheinberg is a Coca-Cola Foundation Chair and Professor at the H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology. Prior to joining Georgia Tech she held positions at Cornell and Lehigh Universities and at IBM T.J. Watson Research Center. She attended Moscow University for her undergraduate studies and received her PhD degree from Columbia University.