### Yurii Nesterov (Center for Operations Research and Econometrics, Catholic University of Louvain, Belgium)

#### Random gradient-free minimization of convex functions

~~Wednesday 23 March 2011 at 15.30~~, Cancelled

##### Abstract

In this talk, we present the complexity bounds for methods of Convex
Optimization based only on computation of the function value. The search
directions of our schemes are normally distributed random Gaussian vectors.
It appears that such methods usually need at most n times more iterations than
the standard gradient methods, where n is the dimension of the space of
variables. This conclusion is true both for nonsmooth and smooth problems.
For the latter class, we develop also an accelerated scheme with the expected
rate of convergence O(n^{2} / k^{2}), where k is the iteration
counter. For Stochastic Optimization, we propose a zero-order scheme and
justify its expected rate of convergence O(n / k^{1/2}). We give also
some bounds for the rate of convergence of the random gradient-free methods to
stationary points of nonconvex functions, both for smooth and nonsmooth cases.
Our theoretical results are supported by preliminary computational experiments.

### Seminars by year

*Current*
*2016*
*2015*
*2014*
*2013*
*2012*
*2011*
*2010*
*2009*
*2008*
*2007*
*2006*
*2005*
*2004*
*2003*
*2002*
*2001*
*2000*
*1999*
*1998*
*1997*
*1996*