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

Résultats de recherche: Contribution à un journal/une revue › Article

Résumé

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.

langue originale	Anglais
Pages (de - à)	359-368
Nombre de pages	10
journal	Mathematical Programming
Volume	163
Numéro de publication	1-2
Les DOIs	https://doi.org/10.1007/s10107-016-1065-8
état	Publié - 15 avr. 2017

Empreinte digitale

Unconstrained Optimization

Nonlinear Optimization

Higher Order

Derivatives

Derivative

Evaluation

Objective function

Lipschitz Continuity

Nonconvex Optimization

Critical point

Model

First-order

Generalise

Citer ceci

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. Dans: Mathematical Programming. 2017 ; Vol 163, Numéro 1-2. p. 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, Numéro 1-2, p. 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.

Dans: Mathematical Programming, Vol 163, Numéro 1-2, 15.04.2017, p. 359-368.

Résultats de recherche: Contribution à un journal/une revue › 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

VL - 163

SP - 359

EP - 368