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

Financement

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

Bailleurs de fonds	Numéro du bailleur de fonds
Belgian Fund for Scientific Research
Fundação de Amparo à Pesquisa do Estado de São Paulo	2010/10133-0, 2013/05475-7, 2013/07375-0, 2013/23494-9, 2013/03447-6
Fonds De La Recherche Scientifique - FNRS
Conselho Nacional de Desenvolvimento Científico e Tecnológico	490326/2013-7, 309517/2014-1, 303750/2014-6, 304032/2010-7

Accès au document

10.1007/s10107-016-1065-8

Autres fichiers et liens

Link to publication in Scopus

108 Citations
4 Article
1 Livre
1 Papier de travail

Examples of slow convergence for adaptive regularization optimization methods are not isolated
Toint, P., 25 sept. 2024, Arxiv.
Résultats de recherche: Papier de travail

File
Evaluation complexity of algorithms for nonconvex optimization
Cartis, C., Gould, N. I. M. & TOINT, P., juil. 2022, SIAM. 600 p. (SIAM-MOS Series on Optimization)
Résultats de recherche: Livre/Rapport/Revue › Livre
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
54 Téléchargements (Pure)

6 Discours invité

Worst-case evaluation complexity for nonconvex optimization: adventures in the jungle of high-order nonlinear optimization
Toint, P. (Orateur)
8 sept. 2018
Activité: Discours ou présentation › Discours invité
A path and some adventures in the jungle of high-order nonlinear optimization
Toint, P. (Orateur)
23 oct. 2017
Activité: Discours ou présentation › Discours invité
A path and some adventures in the jungle of high-order nonlinear optimization
Toint, P. (Orateur)
24 oct. 2017
Activité: Discours ou 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

SN - 0025-5610

VL - 163

SP - 359

EP - 368

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1-2

ER -

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

Résumé

Financement

Accès au document

Autres fichiers et liens

Empreinte digitale

Résultat de recherche

Examples of slow convergence for adaptive regularization optimization methods are not isolated

Evaluation complexity of algorithms for nonconvex optimization

Adaptive regularization algorithms with inexact evaluations for 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