Complexity of Non-Adaptive Optimization Algorithms for a Class of Diffusions

J. M. Calvin and P. W. Glynn

Stochastic Models, Vol. 12, No. 3, 343-365 (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.