Second-order optimality and beyond: Characterization and Evaluation Complexity in Convexly Constrained Nonlinear Optimization

Coralia Cartis, Nicholas I M Gould, Philippe Toint

Research output: Contribution to journalArticle

Abstract

High-order optimality conditions for convexly constrained nonlinear optimization problems are analysed. A corresponding (expensive) measure of criticality for arbitrary order is proposed and extended to define high-order ϵ-approximate critical points. This new measure is then used within a conceptual trust-region algorithm to show that if derivatives of the objective function up to order q≥ 1 can be evaluated and are Lipschitz continuous, then this algorithm applied to the convexly constrained problem needs at most O(ϵ - ( q + 1 )) evaluations of f and its derivatives to compute an ϵ-approximate qth-order critical point. This provides the first evaluation complexity result for critical points of arbitrary order in nonlinear optimization. An example is discussed, showing that the obtained evaluation complexity bounds are essentially sharp.

Original languageEnglish
Pages (from-to)1073-1107
Number of pages35
JournalFoundations of Computational Mathematics
Volume18
Issue number5
DOIs
Publication statusPublished - 1 Oct 2018

Keywords

  • Complexity theory
  • optimality conditions
  • nonlinear optimization

Fingerprint Dive into the research topics of 'Second-order optimality and beyond: Characterization and Evaluation Complexity in Convexly Constrained Nonlinear 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

    • 8 Invited talk
    • 2 Participation in conference
    • 2 Visiting an external academic institution

    Oxford University

    Philippe Toint (Visiting researcher)

    20 Nov 20196 Dec 2019

    Activity: Visiting an external institution typesVisiting an external academic institution

    Departement of Applied Mathematics, Polytechnic University of Hong Kong

    Philippe Toint (Visiting researcher)

    15 Nov 201815 Dec 2018

    Activity: Visiting an external institution typesVisiting an external academic institution

    Recent Advances in Evaluation Complexity for Nonconvex Optimization

    Philippe Toint (Speaker)

    28 Nov 2018

    Activity: Talk or presentation typesInvited talk

    Cite this