Equivalent methods for global optimization

Abstract

The envelope used by the algorithm of Breiman and Cutler [4] can be smoothed to create a better algorithm. This is equivalent to an accelerated algorithm developed by the third author and Cutler in [3] using envelopes which seemed poor ones at first sight. Explaining this anomaly lead to a general result concerning the equivalence of methods which use information from more than one point at each stage and those that only use the most recent evaluated point. Smoothing is appropriate for many algorithms, and we show it is an optimal strategy.