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

Namur Institute for Complex Systems

Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

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
Etat de la publication	Publié - 15 avr. 2017

Accès au document

10.1007/s10107-016-1065-8

Empreinte digitale Examiner les sujets de recherche de « Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models ». Ensemble, ils forment une empreinte digitale unique.

6 Discours invité

Worst-case evaluation complexity for nonconvex optimization: adventures in the jungle of high-order nonlinear optimization
Philippe Toint (Orateur)
8 sept. 2018
Activité: Types de discours ou de présentation › Discours invité
A path and some adventures in the jungle of high-order nonlinear optimization
Philippe Toint (Orateur)
24 oct. 2017
Activité: Types de discours ou de présentation › Discours invité
A path and some adventures in the jungle of high-order nonlinear optimization
Philippe Toint (Orateur)
23 oct. 2017
Activité: Types de discours ou de présentation › Discours invité

Contient cette citation

@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{\textquoteright}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.}",

note = "Funding Information: This work has been partially supported by the Brazilian agencies FAPESP (Grants 2010/10133-0, 2013/03447-6, 2013/05475-7, 2013/07375-0, and 2013/23494-9) and CNPq (Grants 304032/2010-7, 309517/2014-1, 303750/2014-6, and 490326/2013-7) and by the Belgian Fund for Scientific Research (FNRS). Publisher Copyright: {\textcopyright} 2016, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society. Copyright: Copyright 2017 Elsevier B.V., All rights reserved.",

year = "2017",

month = apr,

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

}

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.

N1 - Funding Information: This work has been partially supported by the Brazilian agencies FAPESP (Grants 2010/10133-0, 2013/03447-6, 2013/05475-7, 2013/07375-0, and 2013/23494-9) and CNPq (Grants 304032/2010-7, 309517/2014-1, 303750/2014-6, and 490326/2013-7) and by the Belgian Fund for Scientific Research (FNRS). Publisher Copyright: © 2016, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society. Copyright: Copyright 2017 Elsevier B.V., All rights reserved.

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

EP - 368

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1-2

ER -

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

Résumé

Accès au document

Worst-case evaluation complexity for nonconvex optimization: adventures in the jungle of high-order nonlinear optimization

A path and some adventures in the jungle of high-order nonlinear optimization

A path and some adventures in the jungle of high-order nonlinear optimization

Contient cette citation