Global optimization with unknown Lipschitz constant

We study the global optimization problem, i.e., for a real-valued and bounded function f we are interested in a point x of the domain whose function value f(x) is close to the infimum inf f. We consider the case that f is d-variate, Lipschitz, and, in a certain sense, does not increase too slowly in a neighborhood of the global minimizer(s). We give two contributions: We show that for an optimal method adaptiveness is necessary and that randomization (Monte Carlo) yields no further advantage. We present a method that is universal in the following sense: This algorithm has the optimal rate of convergence even if neither the Lipschitz constant nor any other function parameter is known. Wir betrachten das globale Optimierungsproblem, d.h. für eine reellwertige und beschränkte Funktion f suchen wir eine Stelle x des Definitionsbereichs, deren Funktionswert f(x) nahe dem Infimum inf f liegt. Wir untersuchen den Fall, daß f eine d-variate, Lipschitz-stetige Funktion ist, die in einem gewissen Sinne in der Nähe der globalen Minimalstelle(n) nicht zu langsam wächst. Wir leisten zwei Beiträge: Wir zeigen, daß für eine optimale Methode Adaptivität notwendig ist und daß Randomisierung (Monte-Carlo) keine weiteren Vorteile bringt. Wir stellen eine Methode vor, die universell ist im folgenden Sinne: Diese Methode hat die optimale Konvergenzrate auch in dem Fall, daß weder die Lipschitzkonstante noch die übrigen Klassenparameter bekannt sind.