A concise second-order complexity analysis for unconstrained optimization using high-order regularized models
| Autor: | Philippe L. Toint, Coralia Cartis, Nicholas I. M. Gould |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Mathematical optimization
021103 operations research Control and Optimization Applied Mathematics 0211 other engineering and technologies 010103 numerical & computational mathematics 02 engineering and technology Unconstrained optimization Taylor models complexity analysis 01 natural sciences Nonconvex optimization regularization methods Order (business) Adaptive regularization 0101 mathematics High order Software Mathematics |
| Zdroj: | Optimization Methods and Software. 35:243-256 |
| ISSN: | 1029-4937 1055-6788 |
| DOI: | 10.1080/10556788.2019.1678033 |
| Popis: | 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 ε 1 and ε 1 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|