Seminar : Optimal Newton-type Methods for Nonconvex Smooth Optimization

INDUSTRIAL AND SYSTEMS ENGINEERING (ISE) SEMINAR

Speaker:

Coralia Cartis

Assistant Professor

School of Mathematics

University of Edinburgh

Date, Time, Location:

Thursday, October 27, 2011

2:30pm - 3:30pm

Mohler Laboratory, Room 453

Title:

Optimal Newton-type Methods for Nonconvex Smooth Optimization

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 shows 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 essentially tight. We further show that the cubic regularization approach is, in fact, optimal from a worst-case complexity point of view amongst a class of second-order methods. The worst-case problem-evaluation complexity of constrained optimization will also be discussed, time permitting. This is joint work with Nick Gould (Rutherford Appleton Laboratory, UK) and Philippe Toint (Namur University, Belgium).

Biography:

Coralia Cartis has been a tenured assistant professor at Edinburgh University in Scotland, United Kingdom since 2007. Previously, she held postdoctoral appointments within the numerical analysis groups at Rutherford Appleton Laboratory and Oxford University. She pursued her PhD research in optimization under the supervision of Prof Mike Powell at Cambridge University (2005).

Coralia's research addresses the development, convergence and complexity analyses and implementation of algorithms for linear and nonlinear nonconvex smooth optimization problems, suitable for large-scale problems. She is also interested in the interconnections between dynamical systems and continuous optimization; and optimization aspects of compressed sensing and sparse approximation.