Complexity of non–adaptive optimization algorithms for a class of diffusions
James M. Calvin, Glynn Peter W. · Stochastic Models · 1996
This paper is concerned with the analysis of the average error in approximating the global minimum of a 1-dimensional, time-homogeneous diffusion by non-adaptive methods. We derive the limiting distribution of the suitably normalized approximation error for both random and deterministic non-adaptive approximation methods. We identify the form of the asymptotically optimal random non-adaptive approximation methods.