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

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

Fingerprint

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

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

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Research output

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

Activities

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