In this work we consider the problem of unconstrained minimization of a smooth function in $R^n$ in a setting where only function evaluations are possible. We design a novel random direct search (RDS) method and analyze its complexity. At each iteration, RDS generates a random search direction according to a certain fixed probability law. Our assumptions on this law are very mild. For instance, we allow for the uniform distribution on the sphere and also distributions that concentrate all measure on a positive spanning set. Given a current iterate $x$, the objective function is compared at three points: $x$, $x+\alpha s$ and $x-\alpha s$, where $\alpha>0$ is a stepsize parameter and $s$ is the random search direction. The best of these three points is the next iterate. The complexity of RDS depends on the probability law via a simple characteristic closely related to the cosine measure which is used in the analysis of deterministic direct search (DDS) methods. Unlike in DDS, where $O(n)$ function evaluations must be performed in each iteration in the worst case, our random search method only requires two new function evaluations per iteration. Consequently, while DDS depends quadratically on $n$, our method depends linearly on $n$.

# Mathématiques et Informatique Appliquées

du Génome à l'Environnement