Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models

Coralia Cartis, Nicholas I M Gould, Philippe Toint

Research output: Contribution in Book/Catalog/Report/Conference proceedingChapter

Abstract

Evaluation complexity for convexly constrained optimization is considered and it is shown first that the complexity bound of O(ε- −3∕2 ) proved by Cartis et al. (IMA J Numer Anal 32:1662–1695, 2012) for computing an ε-approximate first-order critical point can be obtained under significantly weaker assumptions. Moreover, the result is generalized to the case where high-order derivatives are used, resulting in a bound of (Formula presented) evaluations whenever derivatives of order p are available. It is also shown that the bound of (Formula presented) evaluations (ε- P and ε- D being primal and dual accuracy thresholds) suggested by Cartis et al. (SIAM J. Numer. Anal. 53:836–851, 2015) for the general nonconvex case involving both equality and inequality constraints can be generalized to yield a bound of (Formula presented) evaluations under similarly weakened assumptions.

Original languageEnglish
Title of host publicationSpringer Optimization and Its Applications
Subtitle of host publicationAlgorithms, Complexity and Applications
EditorsIannis Demetriou, Panos Pardalos
PublisherSpringer Heidelberg
Chapter1
Pages5-26
Number of pages22
ISBN (Electronic)978-3-030-12766-4
DOIs
Publication statusPublished - Jun 2019

Publication series

NameSpringer Optimization and Its Applications
Volume145
ISSN (Print)1931-6828
ISSN (Electronic)1931-6836

Keywords

  • Complexity theory
  • Nonlinear optimization
  • scaled optimality conditions

Fingerprint Dive into the research topics of 'Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models'. 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 Invited talk
    • 4 Oral presentation
    • 2 Visiting an external academic institution
    • 1 Research/Teaching in a external institution

    Oxford University

    Philippe Toint (Visiting researcher)

    20 Nov 20196 Dec 2019

    Activity: Visiting an external institution typesVisiting an external academic institution

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

    Philippe Toint (Speaker)

    23 Oct 2017

    Activity: Talk or presentation typesInvited talk

    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

    Prizes

    Leverhulme Fellow

    TOINT, Philippe (Recipient), Sep 2015

    Prize: Fellowship awarded competitively

    Oliver Smithies Fellow

    TOINT, Philippe (Recipient), Sep 2015

    Prize: Fellowship awarded competitively

    Cite this

    Cartis, C., Gould, N. I. M., & Toint, P. (2019). Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models. In I. Demetriou, & P. Pardalos (Eds.), Springer Optimization and Its Applications: Algorithms, Complexity and Applications (pp. 5-26). (Springer Optimization and Its Applications; Vol. 145). Springer Heidelberg. https://doi.org/10.1007/978-3-030-12767-1_2