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.

Cite this