Complexity of Non-Adaptive Optimization Algorithms for a Class of DiffusionsJ. 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.
|