Title: Non-intrusive Termination of Noisy Optimization
Authors: Jeffrey Larson, Stefan Wild
Abstract: Significant 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 satisfied. Early termination is especially desirable for noisy functions, where a solver could potentially proceed indefinitely while seeing changes insignificant 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 and a set of derivative-free solvers, 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.
Keywords: Noisy Optimization, Termination Criteria, Deterministic Noise, Stochastic Noise, Derivative-free Optimization
Thanks: This work was supported by the Office of Advanced Scientific Computing Research, Office of Science, U.S. Department of Energy, under Contract DE-AC02-06CH11357. The majority of this work was performed while the first author was visiting the Mathematics and Computer Science Division at Argonne National Laboratory. We are grateful to two anonymous referees for their comments that led to an improved version of the paper.
Status: Appears in Optimization Methods and Software, Vol. 28 (5), 2013.
Previously available as Preprint ANL/MCS-P1887-0511, May 2011.
Link: [DOI:10.1080/10556788.2012.656116]
[PDF older version available from Optimization Online]
    author      = "Jeffrey Larson and Stefan M. Wild",
    title       = "Non-intrusive Termination of Noisy Optimization",
    journal     = "Optimization Methods and Software",
    volume      = "28",
    number      = "5",
    pages       = "To appear",    
    year        = "2013",
    doi         = "10.1080/10556788.2012.656116",
Back to Stefan Wild's homepage