Abstract
Original language | English |
---|---|
Pages (from-to) | 93-108 |
Number of pages | 16 |
Journal | Journal of Complexity |
Volume | 28 |
DOIs | |
Publication status | Published - 1 Feb 2012 |
Fingerprint
Keywords
- evaluation complexity
- second-order optimality conditions
- nonconvex optimization
- worst-case analysis
Cite this
}
Complexity bounds for second-order optimality in unconstrained optimization. / Cartis, Coralia; Gould, N.I.M.; Toint, Philippe.
In: Journal of Complexity, Vol. 28, 01.02.2012, p. 93-108.Research output: Contribution to journal › Article
TY - JOUR
T1 - Complexity bounds for second-order optimality in unconstrained optimization
AU - Cartis, Coralia
AU - Gould, N.I.M.
AU - Toint, Philippe
N1 - Copyright 2011 Elsevier B.V., All rights reserved.
PY - 2012/2/1
Y1 - 2012/2/1
N2 - This paper examines worst-case evaluation bounds for finding weak minimizers in unconstrained optimization. For the cubic regularization algorithm, Nesterov and Polyak (2006) [15] and Cartis et al. (2010) [3] show that at most O(ε ) iterations may have to be performed for finding an iterate which is within of satisfying second-order optimality conditions. We first show that this bound can be derived for a version of the algorithm, which only uses one-dimensional global optimization of the cubic model and that it is sharp. We next consider the standard trust-region method and show that a bound of the same type may also be derived for this method, and that it is also sharp in some cases. We conclude by showing that a comparison of the bounds on the worst-case behaviour of the cubic regularization and trust-region algorithms favours the first of these methods. © 2011 Elsevier Inc. All rights reserved.
AB - This paper examines worst-case evaluation bounds for finding weak minimizers in unconstrained optimization. For the cubic regularization algorithm, Nesterov and Polyak (2006) [15] and Cartis et al. (2010) [3] show that at most O(ε ) iterations may have to be performed for finding an iterate which is within of satisfying second-order optimality conditions. We first show that this bound can be derived for a version of the algorithm, which only uses one-dimensional global optimization of the cubic model and that it is sharp. We next consider the standard trust-region method and show that a bound of the same type may also be derived for this method, and that it is also sharp in some cases. We conclude by showing that a comparison of the bounds on the worst-case behaviour of the cubic regularization and trust-region algorithms favours the first of these methods. © 2011 Elsevier Inc. All rights reserved.
KW - evaluation complexity
KW - second-order optimality conditions
KW - nonconvex optimization
KW - worst-case analysis
UR - http://www.scopus.com/inward/record.url?scp=82555189756&partnerID=8YFLogxK
U2 - 10.1016/j.jco.2011.06.001
DO - 10.1016/j.jco.2011.06.001
M3 - Article
VL - 28
SP - 93
EP - 108
JO - Journal of Complexity
JF - Journal of Complexity
SN - 0885-064X
ER -