Optimization Online


Complexity bounds for second-order optimality in unconstrained optimization

Coralia Cartis(coralia.cartis***at***ed.ac.uk)
Nick Gould(nick.gould***at***sftc.ac.uk)
Philippe Toint(philippe.toint***at***fundp.ac.be)

Abstract: This paper examines worst-case evaluation bounds for finding weak minimizers in unconstrained optimization. For the cubic regularization algorithm, Nesterov and Polyak (2006) and Cartis, Gould and Toint (2010) show that at most O(epsilon^{-3}) iterations may have to be performed for finding an iterate which is within epsilon of satisfying second-order optimality conditions. We first show that this bound can be derived for a version of the algorithm which only uses one-dimensional global optimization of the cubic model and that it is sharp. We next consider the standard trust-region method and show that a bound of the same type may also be derived for this method, and that it is also sharp in some cases. We conclude by showing that a comparison of the worst-case behaviour of the ARC and trust-region algorithms favours the first of these methods.

Keywords: evaluation complexity, worst-case analysis, nonconvex optimization, second-order optimality conditions

Category 1: Nonlinear Optimization (Unconstrained Optimization )

Category 2: Nonlinear Optimization (Nonlinear Systems and Least-Squares )

Category 3: Nonlinear Optimization (Other )

Citation: C. Cartis, N. I. M. Gould and Ph. L. Toint, "Complexity bounds for second-order optimality in unconstrained optimization", Report NAXYS-11-2010, FUNDP-University of Namur, 2010.

Download: [PDF]

Entry Submitted: 12/18/2010
Entry Accepted: 12/18/2010
Entry Last Modified: 12/18/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society