A concise second-order complexity analysis for unconstrained optimization using high-order regularized models

C. Cartis, N. I.M. Gould, Ph L. Toint

Research output: Contribution to journalArticle

Abstract

An adaptive regularization algorithm is proposed that uses Taylor models of the objective of order p, (Formula presented.), of the unconstrained objective function, and that is guaranteed to find a first- and second-order critical point in at most (Formula presented.) function and derivatives evaluations, where (Formula presented.) and (Formula presented.) are prescribed first- and second-order optimality tolerances. This is a simple algorithm and associated analysis compared to the much more general approach in Cartis et al. [Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints, arXiv:1811.01220, 2018] that addresses the complexity of criticality higher-than two; here, we use standard optimality conditions and practical subproblem solves to show a same-order sharp complexity bound for second-order criticality. Our approach also extends the method in Birgin et al. [Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models, Math. Prog. A 163(1) (2017), pp. 359–368] to finding second-order critical points, under the same problem smoothness assumptions as were needed for first-order complexity.

Original languageEnglish
Pages (from-to)243-256
JournalOptimization Methods and Software
Volume35
Issue number2
DOIs
Publication statusPublished - 1 Dec 2019

Fingerprint

Complexity Analysis
Unconstrained Optimization
Higher Order
Adaptive algorithms
Criticality
First-order
Critical point
Derivatives
Evaluation
Model
Nonconvex Optimization
Optimality Conditions
Nonlinear Optimization
Tolerance
Smoothness
Optimality
Regularization
Objective function
Derivative
Arbitrary

Keywords

  • complexity analysis
  • Nonconvex optimization
  • regularization methods

Cite this

@article{7cbcdd004739442ba8030f3389fe8fef,
title = "A concise second-order complexity analysis for unconstrained optimization using high-order regularized models",
abstract = "An adaptive regularization algorithm is proposed that uses Taylor models of the objective of order p, (Formula presented.), of the unconstrained objective function, and that is guaranteed to find a first- and second-order critical point in at most (Formula presented.) function and derivatives evaluations, where (Formula presented.) and (Formula presented.) are prescribed first- and second-order optimality tolerances. This is a simple algorithm and associated analysis compared to the much more general approach in Cartis et al. [Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints, arXiv:1811.01220, 2018] that addresses the complexity of criticality higher-than two; here, we use standard optimality conditions and practical subproblem solves to show a same-order sharp complexity bound for second-order criticality. Our approach also extends the method in Birgin et al. [Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models, Math. Prog. A 163(1) (2017), pp. 359–368] to finding second-order critical points, under the same problem smoothness assumptions as were needed for first-order complexity.",
keywords = "complexity analysis, Nonconvex optimization, regularization methods",
author = "C. Cartis and Gould, {N. I.M.} and Toint, {Ph L.}",
year = "2019",
month = "12",
day = "1",
doi = "10.1080/10556788.2019.1678033",
language = "English",
volume = "35",
pages = "243--256",
journal = "Optimization Methods and Software",
issn = "1055-6788",
publisher = "Taylor & Francis",
number = "2",

}

A concise second-order complexity analysis for unconstrained optimization using high-order regularized models. / Cartis, C.; Gould, N. I.M.; Toint, Ph L.

In: Optimization Methods and Software, Vol. 35, No. 2, 01.12.2019, p. 243-256.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A concise second-order complexity analysis for unconstrained optimization using high-order regularized models

AU - Cartis, C.

AU - Gould, N. I.M.

AU - Toint, Ph L.

PY - 2019/12/1

Y1 - 2019/12/1

N2 - An adaptive regularization algorithm is proposed that uses Taylor models of the objective of order p, (Formula presented.), of the unconstrained objective function, and that is guaranteed to find a first- and second-order critical point in at most (Formula presented.) function and derivatives evaluations, where (Formula presented.) and (Formula presented.) are prescribed first- and second-order optimality tolerances. This is a simple algorithm and associated analysis compared to the much more general approach in Cartis et al. [Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints, arXiv:1811.01220, 2018] that addresses the complexity of criticality higher-than two; here, we use standard optimality conditions and practical subproblem solves to show a same-order sharp complexity bound for second-order criticality. Our approach also extends the method in Birgin et al. [Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models, Math. Prog. A 163(1) (2017), pp. 359–368] to finding second-order critical points, under the same problem smoothness assumptions as were needed for first-order complexity.

AB - An adaptive regularization algorithm is proposed that uses Taylor models of the objective of order p, (Formula presented.), of the unconstrained objective function, and that is guaranteed to find a first- and second-order critical point in at most (Formula presented.) function and derivatives evaluations, where (Formula presented.) and (Formula presented.) are prescribed first- and second-order optimality tolerances. This is a simple algorithm and associated analysis compared to the much more general approach in Cartis et al. [Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints, arXiv:1811.01220, 2018] that addresses the complexity of criticality higher-than two; here, we use standard optimality conditions and practical subproblem solves to show a same-order sharp complexity bound for second-order criticality. Our approach also extends the method in Birgin et al. [Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models, Math. Prog. A 163(1) (2017), pp. 359–368] to finding second-order critical points, under the same problem smoothness assumptions as were needed for first-order complexity.

KW - complexity analysis

KW - Nonconvex optimization

KW - regularization methods

UR - http://www.scopus.com/inward/record.url?scp=85075616567&partnerID=8YFLogxK

U2 - 10.1080/10556788.2019.1678033

DO - 10.1080/10556788.2019.1678033

M3 - Article

AN - SCOPUS:85075616567

VL - 35

SP - 243

EP - 256

JO - Optimization Methods and Software

JF - Optimization Methods and Software

SN - 1055-6788

IS - 2

ER -