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

Ernesto Birgin, John Gardenghi, José-Mario Martinez, Sandra Augusta Santos, Philippe Toint

Research output: Working paper

## 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\geq 1$) and to assume Lipschitz continuity of the $p$-th derivative, then an $\epsilon$-approximate first-order critical point can be computed in at most $O(\epsilon^{-(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 language English 2015 Namur center for complex systems 8 naXys-05-2015 Published - Jun 2015

### Publication series

Name naXys Technical Reports naXys 05-2015

## Keywords

• Nonlinear optimization
• Complexity theory
• High-order models

## 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.
• ### Adaptive regularization algorithms with inexact evaluations for nonconvex optimization

Bellavia, S., Gurioli, G., Morini, B. & Toint, P., 2 Jan 2020, 29, 4, p. 2881-2915 35 p.

Research output: Contribution to journalArticlepeer-review

Open Access
File
• ### Complexity of partially separable convexly constrained optimization with non-Lipschitzian singularities

Chen, X., Toint, P. & Wang, H., 15 Apr 2019, 29, 1, p. 874-903 30 p.

Research output: Contribution to journalArticlepeer-review

Open Access
File
• ### Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models

Cartis, C., Gould, N. I. M. & Toint, P., Jun 2019, Springer Optimization and Its Applications: Algorithms, Complexity and Applications. Demetriou, I. & Pardalos, P. (eds.). Springer Heidelberg, p. 5-26 22 p. (Springer Optimization and Its Applications; vol. 145).

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

• ### Complexity in nonlinear optimization

TOINT, P., Gould, N. I. M. & Cartis, C.

1/11/08 → …

Project: Research

• ### ADALGOPT: ADALGOPT - Advanced algorithms in nonlinear optimization

1/01/87 → …

Project: Research Axis

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

• ### High-order optimality conditions in nonlinear optimization: necessary conditions and a conceptual approach of evaluation complexity

Philippe Toint (Speaker)

10 Aug 2016

Activity: Talk or presentation typesInvited talk