Worst-case evaluation complexity of non-monotone gradient-related algorithms for unconstrained optimization

C. Cartis, Phillipe Rodrigues Sampaio, Ph L. Toint

Research output: Contribution to journalArticle

85 Downloads (Pure)

Abstract

The worst-case evaluation complexity of finding an approximate first-order critical point using gradient-related non-monotone methods for smooth non-convex and unconstrained problems is investigated. The analysis covers a practical linesearch implementation of these popular methods, allowing for an unknown number of evaluations of the objective function (and its gradient) per iteration. It is shown that this class of methods shares the known complexity properties of a simple steepest-descent scheme and that an approximate first-order critical point can be computed in at most (Formula presented.) function and gradient evaluations, where (Formula presented.) is the user-defined accuracy threshold on the gradient norm.

Original languageEnglish
Pages (from-to)1349-1361
Number of pages13
JournalOptimization
Volume64
Issue number5
DOIs
Publication statusPublished - 4 May 2015

Keywords

  • evaluation complexity
  • linesearch algorithms
  • non-linear optimization
  • non-monotone methods
  • worst-case analysis

Fingerprint Dive into the research topics of 'Worst-case evaluation complexity of non-monotone gradient-related algorithms for 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
    • 2 Research/Teaching in a external institution
    • 1 Invited talk
    • 1 Visiting an external academic institution

    A path and some adventures in the jungle of high-order nonlinear optimization

    Philippe Toint (Speaker)

    24 Oct 2017

    Activity: Talk or presentation typesInvited talk

    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

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

    Philippe Toint (Speaker)

    31 Jan 2016

    Activity: Talk or presentation typesOral presentation

    Prizes

    Leverhulme Fellow

    TOINT, Philippe (Recipient), Sep 2015

    Prize: Fellowship awarded competitively

    Cite this