- Luís Nunes Vicente, Universidade de Coimbra, Portugal
"Zero-Order Methods: Global Rates and Randomness"
In some derivative-free methods, it is possible to
develop worst case complexity bounds in terms of the number of
iterations or function evaluations to reach some level of stationarity.
Such global rates complement existing analyses of global convergence by
providing additional insight and comparisons.\newline
We show that
the broad class of direct-search methods of directional type, based on
imposing sufficient decrease to accept new iterates, exhibits the same
global rates or worst case complexity bounds of the gradient method for
the unconstrained minimization of a smooth function, both in the
nonconvex and convex cases. A smoothing direct search approach is also
discussed capable of deliver a global rate in the nonsmooth nonconvex
We will also present some recent interesting
discoveries in probabilistic direct-search methods where polling does
not rely necessarily on positive spanning sets and global rates are
developed for certain positive probability. At this point we will
connect to the other broad class of derivative-free methods based on
modeling and trust regions.\newline
This is joint work with M. Dodangeh, R. Garmanjani, S. Gratton, C. Royer, and Z. Zhang.