Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models

E. G. Birgin, J. L. Gardenghi, J. M. Martínez, S. A. Santos, P. L. Toint

Research output: Contribution to journalArticlepeer-review

Abstract

The worst-case evaluation complexity for smooth (possibly nonconvex) unconstrained optimization is considered. It is shown that, if one is willing to use derivatives of the objective function up to order p (for p≥ 1 ) and to assume Lipschitz continuity of the p-th derivative, then an ϵ-approximate first-order critical point can be computed in at most O(ϵ - ( p + 1 ) / p) evaluations of the problem’s objective function and its derivatives. This generalizes and subsumes results known for p= 1 and p= 2.

Original languageEnglish
Pages (from-to)359-368
Number of pages10
JournalMathematical Programming
Volume163
Issue number1-2
DOIs
Publication statusPublished - 15 Apr 2017

Keywords

  • Evaluation complexity
  • High-order models
  • Nonlinear optimization
  • Regularization
  • Unconstrained optimization

Fingerprint

Dive into the research topics of 'Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models'. Together they form a unique fingerprint.

Cite this