Adaptive cubic regularisation methods for unconstrained optimization. Part II: Worst-case function- and derivative-evaluation complexity

Coralia Cartis, Nick Gould, Philippe Toint

Research output: Contribution to journalArticle

32 Downloads (Pure)

Abstract

An Adaptive Regularisation framework using Cubics (ARC) was proposed for unconstrained optimization and analysed in Cartis, Gould and Toint (Part I, Math Program, doi: 10.1007/s10107-009-0286-5, 2009), generalizing at the same time an unpublished method due to Griewank (Technical Report NA/12, 1981, DAMTP, University of Cambridge), an algorithm by Nesterov and Polyak (Math Program 108(1):177-205, 2006) and a proposal by Weiser, Deuflhard and Erdmann (Optim Methods Softw 22(3):413-431, 2007). In this companion paper, we further the analysis by providing worst-case global iteration complexity bounds for ARC and a second-order variant to achieve approximate first-order, and for the latter second-order, criticality of the iterates. In particular, the second-order ARC algorithm requires at most O(ε ^(-3/2)) iterations, or equivalently, function- and gradient-evaluations, to drive the norm of the gradient of the objective below the desired accuracy εand Omathcal (ε ) iterations, to reach approximate nonnegative curvature in a subspace. The orders of these bounds match those proved for Algorithm 3.3 of Nesterov and Polyak which minimizes the cubic model globally on each iteration. Our approach is more general in that it allows the cubic model to be solved only approximately and may employ approximate Hessians.
Original languageEnglish
Pages (from-to)295-319
Number of pages25
JournalMathematical Programming
Volume130
Issue number2
DOIs
Publication statusPublished - 1 Dec 2011

Fingerprint

Unconstrained Optimization
Regularization Method
Derivatives
Iteration
Derivative
Evaluation
Gradient
Nonnegative Curvature
Criticality
Iterate
Regularization
Subspace
First-order
Minimise
Norm
Model

Cite this

@article{dbb93aa2a4904d16a8cf52063f45cc9b,
title = "Adaptive cubic regularisation methods for unconstrained optimization. Part II: Worst-case function- and derivative-evaluation complexity",
abstract = "An Adaptive Regularisation framework using Cubics (ARC) was proposed for unconstrained optimization and analysed in Cartis, Gould and Toint (Part I, Math Program, doi: 10.1007/s10107-009-0286-5, 2009), generalizing at the same time an unpublished method due to Griewank (Technical Report NA/12, 1981, DAMTP, University of Cambridge), an algorithm by Nesterov and Polyak (Math Program 108(1):177-205, 2006) and a proposal by Weiser, Deuflhard and Erdmann (Optim Methods Softw 22(3):413-431, 2007). In this companion paper, we further the analysis by providing worst-case global iteration complexity bounds for ARC and a second-order variant to achieve approximate first-order, and for the latter second-order, criticality of the iterates. In particular, the second-order ARC algorithm requires at most O(ε ^(-3/2)) iterations, or equivalently, function- and gradient-evaluations, to drive the norm of the gradient of the objective below the desired accuracy εand Omathcal (ε ) iterations, to reach approximate nonnegative curvature in a subspace. The orders of these bounds match those proved for Algorithm 3.3 of Nesterov and Polyak which minimizes the cubic model globally on each iteration. Our approach is more general in that it allows the cubic model to be solved only approximately and may employ approximate Hessians.",
author = "Coralia Cartis and Nick Gould and Philippe Toint",
note = "Copyright 2011 Elsevier B.V., All rights reserved.",
year = "2011",
month = "12",
day = "1",
doi = "10.1007/s10107-009-0337-y",
language = "English",
volume = "130",
pages = "295--319",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer-Verlag GmbH and Co. KG",
number = "2",

}

Adaptive cubic regularisation methods for unconstrained optimization. Part II : Worst-case function- and derivative-evaluation complexity. / Cartis, Coralia; Gould, Nick; Toint, Philippe.

In: Mathematical Programming, Vol. 130, No. 2, 01.12.2011, p. 295-319.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Adaptive cubic regularisation methods for unconstrained optimization. Part II

T2 - Worst-case function- and derivative-evaluation complexity

AU - Cartis, Coralia

AU - Gould, Nick

AU - Toint, Philippe

N1 - Copyright 2011 Elsevier B.V., All rights reserved.

PY - 2011/12/1

Y1 - 2011/12/1

N2 - An Adaptive Regularisation framework using Cubics (ARC) was proposed for unconstrained optimization and analysed in Cartis, Gould and Toint (Part I, Math Program, doi: 10.1007/s10107-009-0286-5, 2009), generalizing at the same time an unpublished method due to Griewank (Technical Report NA/12, 1981, DAMTP, University of Cambridge), an algorithm by Nesterov and Polyak (Math Program 108(1):177-205, 2006) and a proposal by Weiser, Deuflhard and Erdmann (Optim Methods Softw 22(3):413-431, 2007). In this companion paper, we further the analysis by providing worst-case global iteration complexity bounds for ARC and a second-order variant to achieve approximate first-order, and for the latter second-order, criticality of the iterates. In particular, the second-order ARC algorithm requires at most O(ε ^(-3/2)) iterations, or equivalently, function- and gradient-evaluations, to drive the norm of the gradient of the objective below the desired accuracy εand Omathcal (ε ) iterations, to reach approximate nonnegative curvature in a subspace. The orders of these bounds match those proved for Algorithm 3.3 of Nesterov and Polyak which minimizes the cubic model globally on each iteration. Our approach is more general in that it allows the cubic model to be solved only approximately and may employ approximate Hessians.

AB - An Adaptive Regularisation framework using Cubics (ARC) was proposed for unconstrained optimization and analysed in Cartis, Gould and Toint (Part I, Math Program, doi: 10.1007/s10107-009-0286-5, 2009), generalizing at the same time an unpublished method due to Griewank (Technical Report NA/12, 1981, DAMTP, University of Cambridge), an algorithm by Nesterov and Polyak (Math Program 108(1):177-205, 2006) and a proposal by Weiser, Deuflhard and Erdmann (Optim Methods Softw 22(3):413-431, 2007). In this companion paper, we further the analysis by providing worst-case global iteration complexity bounds for ARC and a second-order variant to achieve approximate first-order, and for the latter second-order, criticality of the iterates. In particular, the second-order ARC algorithm requires at most O(ε ^(-3/2)) iterations, or equivalently, function- and gradient-evaluations, to drive the norm of the gradient of the objective below the desired accuracy εand Omathcal (ε ) iterations, to reach approximate nonnegative curvature in a subspace. The orders of these bounds match those proved for Algorithm 3.3 of Nesterov and Polyak which minimizes the cubic model globally on each iteration. Our approach is more general in that it allows the cubic model to be solved only approximately and may employ approximate Hessians.

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

U2 - 10.1007/s10107-009-0337-y

DO - 10.1007/s10107-009-0337-y

M3 - Article

AN - SCOPUS:81255179401

VL - 130

SP - 295

EP - 319

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 2

ER -