Name
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,p >= 2, of the unconstrained objective function, and that is guaranteed to find a first- and second-order critical point in at most O(max{epsilon(-p+1/p)(1), epsilon(-p+1/p-1)(2)}) function and derivatives evaluations, where epsilon(1) and epsilon(2) 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. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1080/10556788.2019.1678033 | OPTIMIZATION METHODS & SOFTWARE |
Keywords | DocType | Volume |
Nonconvex optimization,regularization methods,complexity analysis | Journal | 35 |
Issue | ISSN | Citations |
SP2 | 1055-6788 | 1 |
PageRank | References | Authors |
0.35 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Coralia Cartis | 1 | 451 | 28.74 |
| Nicholas I. M. Gould | 2 | 1445 | 123.86 |
| Ph. L. Toint | 3 | 927 | 197.61 |