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

Autres fichiers et liens

Link to publication in Scopus

61 Citations
4 Article

Adaptive regularization algorithms with inexact evaluations for nonconvex optimization
Bellavia, S., Gurioli, G., Morini, B. & Toint, P., 2 janv. 2020, Dans: SIAM Journal on Optimization. 29, 4, p. 2881-2915 35 p.
Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

Accès ouvert
File
11 Téléchargements (Pure)
Complexity of partially separable convexly constrained optimization with non-Lipschitzian singularities
Chen, X., Toint, P. & Wang, H., 15 avr. 2019, Dans: SIAM Journal on Optimization. 29, 1, p. 874-903 30 p.
Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

Accès ouvert
File
16 Téléchargements (Pure)
Optimality of orders one to three and beyond: Characterization and evaluation complexity in constrained nonconvex optimization
Cartis, C., Gould, N. I. M. & Toint, P., 10 août 2019, Dans: Journal of Complexity. 53, p. 68-94 32 p.
Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

Accès ouvert
File
11 Téléchargements (Pure)

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)
23 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)
24 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

Autres fichiers et liens

Empreinte digitale

Résultat de recherche

Adaptive regularization algorithms with inexact evaluations for nonconvex optimization

Complexity of partially separable convexly constrained optimization with non-Lipschitzian singularities

Optimality of orders one to three and beyond: Characterization and evaluation complexity in constrained nonconvex optimization

Activités

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