### Coralia Cartis (University of Edinburgh)

#### Optimal Newton-type methods for nonconvex smooth optimization

*Joint work with Nick Gould and Philippe Toint.*

*Wednesday 25 January 2012 at 15.30, JCMB 6206*

##### Abstract

We show that the steepest-descent and Newton's methods for unconstrained
nonconvex optimization under standard assumptions may both require a number of
iterations and function evaluations arbitrarily close to the steepest-descent's
global worst-case complexity bound. This implies that the latter upper bound is
essentially tight for steepest descent and that Newton's method may be as slow
as the steepest-descent method in the worst case. Then the cubic regularization
of Newton's method (Griewank (1981), Nesterov & Polyak (2006)) is considered
and extended to large-scale problems, while preserving the same order of its
improved worst-case complexity (by comparison to that of steepest-descent);
this improved worst-case bound is also shown to be tight. We further show that
the cubic regularization approach is, in fact, optimal from a worst-case
complexity point of view amongst a wide class of second-order methods. The
worst-case problem-evaluation complexity of constrained optimization will also
be discussed.

### 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*