We describe a class of adaptive algorithms for approximating the global minimum of a continuous function on the unit interval. The limiting distribution of the error is derived under the assumption of Wiener measure on the objective functions. For any δ > 0, we construct an algorithm which has error converging to zero at rate n-(1 - δ) in the number of function evaluations n. This convergence rate contrasts with the n11/2 rate of previously studied nonadaptive methods.
All Science Journal Classification (ASJC) codes
- Statistics and Probability
- Statistics, Probability and Uncertainty
- Average complexity
- Brownian motion
- Global optimization