Black-box complexity of local minimization

Abstract

We study the complexity of local minimization in the black-box model, that is, the model in which the objective function and possibly its gradient are available as external subroutines. This is the model used, for example, in all the optimization algorithms in the 1983 book by Dennis and Schnabel. Our first main result is that the complexity grows polynomially with the number of variables n, in contrast to other related black-box problems (global minimization, Brouwer fixed points) for which the worst case complexity is exponential in n. Our second contribution is the construction of a family of functions that are bad cases for all possible black-box local optimization algorithms.