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

Research output: Contribution to journal › Article › peer-review

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

Keywords

Evaluation complexity
High-order models
Nonlinear optimization
Regularization
Unconstrained optimization

Access to Document

10.1007/s10107-016-1065-8

Fingerprint Dive into the research topics of 'Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models'. Together they form a unique fingerprint.

6 Invited talk

Worst-case evaluation complexity for nonconvex optimization: adventures in the jungle of high-order nonlinear optimization
Philippe Toint (Speaker)
8 Sep 2018
Activity: Talk or presentation types › Invited talk
A path and some adventures in the jungle of high-order nonlinear optimization
Philippe Toint (Speaker)
24 Oct 2017
Activity: Talk or presentation types › Invited talk
A path and some adventures in the jungle of high-order nonlinear optimization
Philippe Toint (Speaker)
23 Oct 2017
Activity: Talk or presentation types › Invited talk

Cite this

@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

Abstract

Keywords

Access to Document

Other files and links

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

Cite this