Lower bounds for randomized direct search with isotropic sampling

Randomized direct-search methods for the optimization of a function f:Rn→Rf:Rn→R that is given by a black box for ff-evaluations are investigated. These iterative methods generate new candidate solutions by adding isotropically distributed vectors to the current candidate solution. Lower bounds on the number of ff-evaluations necessary for reducing the approximation error in the search space are proved.