FINDING THE MINIMUM OF A FUNCTION∗

Dedicated to Stanley Osher on the occasion of his 70-th birthday with much admiration Abstract. Adaptive query algorithms for finding the minimum of a function f are studied. The algorithms build on the earlier adaptive algorithms given in [5, 8]. The rate of convergence of these algorithms is estimated under various model assumptions on the function f. The first class of algorithms is analyzed when f satisfies a smoothness condition, e.g. f ∈ Cr, and an assumption on its level sets as given in [8]. There is a distinction drawn as to whether or not the algorithm has knowledge of the semi-norm |f |Cr. If this information is known, it is rather straightforward to design algorithms with optimal performance and to show that this performance is better than non-adaptive algorithms. A bit more subtle is to build algorithms which are universal in that they do not need to know the semi-norm of f. Universal algorithms are built that have the same asymptotic performance as when the semi-norm is known, save for a logarithm. The second part of this paper studies adaptive algorithms for finding the minimum of a function in high dimension. In this case, additional assumptions are placed on f, of the form given in [3], that have the effect of variable reduction and thereby avoiding the curse of dimensionality. These algorithms are again shown to be asymptotically optimal up to a logarithm factor. Key words. Computing minima, adaptive methods, tree based algorithms, high dimension. AMS subject classifications. Primary: 65K99, 68Q25; Secondary 41A25, 90C60