Adaptive cubic regularisation methods for unconstrained optimization. Part II: Worst-case function- and derivative-evaluation complexity

Coralia Cartis, Nick Gould, Philippe Toint

Research output: Contribution to journalArticle

97 Downloads (Pure)

Abstract

An Adaptive Regularisation framework using Cubics (ARC) was proposed for unconstrained optimization and analysed in Cartis, Gould and Toint (Part I, Math Program, doi: 10.1007/s10107-009-0286-5, 2009), generalizing at the same time an unpublished method due to Griewank (Technical Report NA/12, 1981, DAMTP, University of Cambridge), an algorithm by Nesterov and Polyak (Math Program 108(1):177-205, 2006) and a proposal by Weiser, Deuflhard and Erdmann (Optim Methods Softw 22(3):413-431, 2007). In this companion paper, we further the analysis by providing worst-case global iteration complexity bounds for ARC and a second-order variant to achieve approximate first-order, and for the latter second-order, criticality of the iterates. In particular, the second-order ARC algorithm requires at most O(ε ^(-3/2)) iterations, or equivalently, function- and gradient-evaluations, to drive the norm of the gradient of the objective below the desired accuracy εand Omathcal (ε ) iterations, to reach approximate nonnegative curvature in a subspace. The orders of these bounds match those proved for Algorithm 3.3 of Nesterov and Polyak which minimizes the cubic model globally on each iteration. Our approach is more general in that it allows the cubic model to be solved only approximately and may employ approximate Hessians.
Original languageEnglish
Pages (from-to)295-319
Number of pages25
JournalMathematical Programming
Volume130
Issue number2
DOIs
Publication statusPublished - 1 Dec 2011

Fingerprint Dive into the research topics of 'Adaptive cubic regularisation methods for unconstrained optimization. Part II: Worst-case function- and derivative-evaluation complexity'. 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

    • 3 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

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

    Philippe Toint (Speaker)

    31 Jan 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

    Cite this