A grid algorithm for bound constrained optimization of noisy functions

The optimization of noisy functions is a common problem occurring in various applications. In this paper, a new approach is presented for low-dimensional bound constrained problems, based on the use of quadratic models and a restriction of the evaluation points to successively refined grids. In the noiseless case, global convergence of tie algorithm to a stationary point is proved; in the noisy case a bound for the limit accuracy is derived. An extensive numerical comparison with two widely used methods—a quasi-Newton method and the simplex method of Nelder and Mead—performed on a standard collection of test problems, shows that the new algorithm is comparable with quasi-Newton in the noiseless case, and is much more robust than Nelder-Mead in the noisy case. If performance is measured solely by the number of function evaluations needed to achieve a prescribed reduction of the difference to the minimal function value (as for instance in the optimization of experiments), the new algorithm is also significantly faster than Nelder-Mead.