Complexity bounds for second-order optimality in unconstrained optimization

Coralia Cartis, N.I.M. Gould, Philippe Toint

Research output: Contribution to journalArticle

53 Downloads (Pure)

Abstract

This paper examines worst-case evaluation bounds for finding weak minimizers in unconstrained optimization. For the cubic regularization algorithm, Nesterov and Polyak (2006) [15] and Cartis et al. (2010) [3] show that at most O(ε ) iterations may have to be performed for finding an iterate which is within 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 bounds on the worst-case behaviour of the cubic regularization and trust-region algorithms favours the first of these methods. © 2011 Elsevier Inc. All rights reserved.
Original languageEnglish
Pages (from-to)93-108
Number of pages16
JournalJournal of Complexity
Volume28
DOIs
Publication statusPublished - 1 Feb 2012

Keywords

  • evaluation complexity
  • second-order optimality conditions
  • nonconvex optimization
  • worst-case analysis

Fingerprint Dive into the research topics of 'Complexity bounds for second-order optimality in unconstrained optimization'. Together they form a unique fingerprint.

  • Projects

    Complexity in nonlinear optimization

    TOINT, P., Gould, N. I. M. & Cartis, C.

    1/11/08 → …

    Project: Research

    Activities

    • 4 Oral presentation
    • 1 Research/Teaching in a external institution
    • 1 Visiting an external academic institution

    How much patience do you have? Issues in complexity for nonlinear optimization

    Philippe Toint (Invited speaker)

    5 Feb 2016

    Activity: Talk or presentation typesOral presentation

    Polytechnic University of Hong Kong

    Philippe Toint (Visiting researcher)

    31 Jan 201614 Feb 2016

    Activity: Visiting an external institution typesResearch/Teaching in a external institution

    How much patience do you have? Issues in complexity for nonlinear optimization

    Philippe Toint (Speaker)

    31 Jan 2016

    Activity: Talk or presentation typesOral presentation

    Cite this