Methods and Applications of Analysis

Volume 20 (2013)

Number 4

Special issue dedicated to the 70th birthday of Stanley Osher: Part I

Guest Editor: Chi-Wang Shu, Brown University

Finding the minimum of a function

Pages: 365 – 382

DOI: https://dx.doi.org/10.4310/MAA.2013.v20.n4.a4

Authors

Albert Cohen (Laboratoire Jacques-Louis Lions, UMR 7598, University of Paris, France)

Ronald Devore (Department of Mathematics, Texas A&M University, College Station, Tx., U.S.A.)

Guergana Petrova (Department of Mathematics, Texas A&M University, College Station, Tx., U.S.A.)

Przemysław Wojtaszczyk (Interdisciplinary Center for Mathematical and Computational Modelling, University of Warsaw, Poland)

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 \in C^r$, 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 ${\vert f \vert }_{C^r}$. 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.

Keywords

computing minima, adaptive methods, tree based algorithms, high dimension

2010 Mathematics Subject Classification

Primary 65K99, 68Q25. Secondary 41A25, 90C60.

Full Text (PDF format)

Published 16 April 2014