A lower bound on convergence rates of nonadaptive algorithms for univariate optimization with noise

作者：Calvin James M^*

来源：Journal of Global Optimization, 2010, 48(1): 17-27.

DOI：10.1007/s10898-010-9530-z

• Global optimization
• Wiener process
• Noisy information

This paper considers complexity bounds for the problem of approximating the global minimum of a univariate function when the function evaluations are corrupted by random noise. We take an average-case point of view, where the objective function is taken to be a sample function of a Wiener process and the noise is independent Gaussian. Previous papers have bounded the convergence rates of some nonadaptive algorithms. We establish a lower bound on the convergence rate of any nonadaptive algorithm.

• 出版日期2010-9