BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Optimal Newton-type methods for nonconvex smooth optimization - Co
 ralia Cartis (School of Mathematics\, University of Edinburgh\, UK)
DTSTART:20120913T140000Z
DTEND:20120913T150000Z
UID:TALK38794@talks.cam.ac.uk
CONTACT:Carola-Bibiane Schoenlieb
DESCRIPTION:This talk addresses global rates of convergence and the worst-
 case evaluation complexity of methods for nonconvex optimization problems.
  We show that the classical steepest-descent and Newton's methods for unco
 nstrained nonconvex optimization under standard assumptions may both requi
 re a number of iterations and function evaluations arbitrarily close to th
 e 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 wors
 t case. Then the cubic regularization of Newton's method (Griewank (1981)\
 , Nesterov & Polyak (2006)) is considered and extended to large-scale prob
 lems\, while preserving the same order of its improved worst-case complexi
 ty (by comparison to that of steepest-descent)\; this improved worst-case 
 bound is also shown to be tight. We further show that the cubic regulariza
 tion approach is\, in fact\, optimal from a worst-case complexity point of
  view amongst a wide class of second-order methods for nonconvex optimizat
 ion. The worst-case problem-evaluation complexity of constrained optimizat
 ion will also be discussed. This is joint work with Nick Gould (Rutherford
  Appleton Laboratory\, UK) and Philippe Toint (University of Namur\, Belgi
 um).
LOCATION:MR 14\, Centre for Mathematical Sciences
END:VEVENT
END:VCALENDAR