Lower bounds for randomized direct search with isotropic sampling

Randomized direct-search methods for the optimization of a function f:Rⁿ→R that is given by a black box for f-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 f-evaluations necessary for reducing the approximation error in the search space are proved.