Abstract
| Original language | English |
|---|---|
| Pages (from-to) | 295-319 |
| Number of pages | 25 |
| Journal | Mathematical Programming |
| Volume | 130 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - 1 Dec 2011 |
Fingerprint
Cite this
}
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 journal › Article
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 -