Optimal algorithms for global optimization in case of unknown Lipschitz constant (Q2489149)

The author presents two algorithms in order to find a point such that the value of a continuous multivariate Lipschitz function on the unit cube in that point be close to the infimum of the function. The first algorithm applies when the Lipschitz constant is known and the second when it is unknown and both are adaptive deterministic and use only function values. It is shown that both algorithms have the optimal rate of convergence and that adaptiveness is necessary and randomization yields no further advantages. A numerical test problem is presented to illustrate the behavior of the algorithm applying in the case when the Lipschitz constant is unknown.