# 12 mars 2018

Heure et lieu:
10h, salle de réunion, bâtiment 210
Nom intervenant:
El Houcine Bergou
Titre:
Random Direct Search Method for Unconstrained Smooth Minimization
Résumé:

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$.

Année:
2018
Organisme intervenant:
INRA MaIAGE et KAUST-VCC
Date du jour:
Lundi, Mars 12, 2018