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

doi:10.1007/s10107-016-1065-8

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 journal › Article

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 ⁺ ¹ ⁾ ^/ ^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
Pages (from-to)	359-368
Number of pages	10
Journal	Mathematical Programming
Volume	163
Issue number	1-2
DOIs	https://doi.org/10.1007/s10107-016-1065-8
Publication status	Published - 15 Apr 2017

Fingerprint

Unconstrained Optimization

Nonlinear Optimization

Higher Order

Derivatives

Derivative

Evaluation

Objective function

Lipschitz Continuity

Nonconvex Optimization

Critical point

Model

First-order

Generalise

Keywords

Evaluation complexity
High-order models
Nonlinear optimization
Regularization
Unconstrained optimization

Cite this

Birgin, E. G., Gardenghi, J. L., Martínez, J. M., Santos, S. A., & Toint, P. L. (2017). Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models. Mathematical Programming, 163(1-2), 359-368. https://doi.org/10.1007/s10107-016-1065-8

Birgin, E. G. ; Gardenghi, J. L. ; Martínez, J. M. ; Santos, S. A. ; Toint, P. L. / Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models. In: Mathematical Programming. 2017 ; Vol. 163, No. 1-2. pp. 359-368.

@article{6330c972b85247dcbfc3b422043dafa3,

title = "Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models",

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.",

keywords = "Evaluation complexity, High-order models, Nonlinear optimization, Regularization, Unconstrained optimization",

author = "Birgin, {E. G.} and Gardenghi, {J. L.} and Mart{\'i}nez, {J. M.} and Santos, {S. A.} and Toint, {P. L.}",

year = "2017",

month = "4",

day = "15",

doi = "10.1007/s10107-016-1065-8",

language = "English",

volume = "163",

pages = "359--368",

journal = "Mathematical Programming",

issn = "0025-5610",

publisher = "Springer-Verlag GmbH and Co. KG",

number = "1-2",

}

Birgin, EG, Gardenghi, JL, Martínez, JM, Santos, SA & Toint, PL 2017, 'Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models', Mathematical Programming, vol. 163, no. 1-2, pp. 359-368. https://doi.org/10.1007/s10107-016-1065-8

Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models. / Birgin, E. G.; Gardenghi, J. L.; Martínez, J. M.; Santos, S. A.; Toint, P. L.

In: Mathematical Programming, Vol. 163, No. 1-2, 15.04.2017, p. 359-368.

Research output: Contribution to journal › Article

TY - JOUR

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

AU - Birgin, E. G.

AU - Gardenghi, J. L.

AU - Martínez, J. M.

AU - Santos, S. A.

AU - Toint, P. L.

PY - 2017/4/15

Y1 - 2017/4/15

N2 - 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.

AB - 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.

KW - Evaluation complexity

KW - High-order models

KW - Nonlinear optimization

KW - Regularization

KW - Unconstrained optimization

UR - http://www.scopus.com/inward/record.url?scp=84984820379&partnerID=8YFLogxK

U2 - 10.1007/s10107-016-1065-8

DO - 10.1007/s10107-016-1065-8

M3 - Article

AN - SCOPUS:84984820379

VL - 163

SP - 359