Speed of convergence as a function of given accuracy for random search methods

The essence of this article lies in a demonstration of the fact that for some random search methods (r.s.m.) of global optimization, the number of the objective function evaluations required to reach a given accuracy may have very slow (logarithmic) growth to infinity as the accuracy tends to zero. Several inequalities of this kind are derived for some typical Markovian monotone r.s.m. in metric spaces including thed-dimensional Euclidean space ^d and its compact subsets. In the compact case, one of the main results may be briefly outlined as a constructive theorem of existence: if is a first moment of approaching a good subset of-neighbourhood ofx ₀=arg maxf by some random search sequence (r.s.s.), then we may choose parameters of this r.s.s. in such a way that E c(f) In² . Certainly, some restrictions on metric space and functionf are required.