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 language | English |
|---|---|
| Pages (from-to) | 243-256 |
| Journal | Optimization Methods and Software |
| Volume | 35 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - 1 Dec 2019 |
Fingerprint
Keywords
- complexity analysis
- Nonconvex optimization
- regularization methods
Cite this
}
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 journal › Article
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 -