LANS Publications

"Non-intrusive Termination of Noisy Optimization"

J. Larson and S. M. Wild

Optimization Methods and Software, . Also Preprint ANL/MCS-P1887-0511

Preprint Version: [pdf]

Signi ficant savings can be gained from terminating the optimization of a computationally expensive function well before traditional criteria, such as a maximum budget of evaluations, are satisfi ed. Early termination is especially desirable for noisy functions, where a solver could potentially proceed indefinitely while seeing changes insigni ficant relative to the noise. In this paper we consider general termination tests that can be used in conjunction with any solver's built-in termination criteria. We propose parameterized families of termination tests, analyze their properties, and illustrate how they can employ an estimate of the function's noise level. Using a set of benchmark problems with both stochastic and deterministic noise, we compare the tests and their sensitivities to parameters in terms of both accuracy and efficiency. Recommendations are made for using the proposed tests in practice.