A concise second-order complexity analysis for unconstrained optimization using high-order regularized models
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{ϵ−p+1p1,ϵ−p+1p−12}) function and derivatives evaluations, where...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Taylor and Francis
2019
|
| _version_ | 1826258263302209536 |
|---|---|
| author | Cartis, C Gould, N Toint, P |
| author_facet | Cartis, C Gould, N Toint, P |
| author_sort | Cartis, C |
| collection | OXFORD |
| description | 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{ϵ−p+1p1,ϵ−p+1p−12}) function and derivatives evaluations, where ϵ1 and ϵ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. |
| first_indexed | 2024-03-06T18:31:12Z |
| format | Journal article |
| id | oxford-uuid:09b543f4-83e2-4e03-9846-84cab74dad6c |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T18:31:12Z |
| publishDate | 2019 |
| publisher | Taylor and Francis |
| record_format | dspace |
| spelling | oxford-uuid:09b543f4-83e2-4e03-9846-84cab74dad6c2022-03-26T09:19:48ZA concise second-order complexity analysis for unconstrained optimization using high-order regularized modelsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:09b543f4-83e2-4e03-9846-84cab74dad6cEnglishSymplectic Elements at OxfordTaylor and Francis2019Cartis, CGould, NToint, PAn 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{ϵ−p+1p1,ϵ−p+1p−12}) function and derivatives evaluations, where ϵ1 and ϵ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. |
| spellingShingle | Cartis, C Gould, N Toint, P A concise second-order complexity analysis for unconstrained optimization using high-order regularized models |
| title | A concise second-order complexity analysis for unconstrained optimization using high-order regularized models |
| title_full | A concise second-order complexity analysis for unconstrained optimization using high-order regularized models |
| title_fullStr | A concise second-order complexity analysis for unconstrained optimization using high-order regularized models |
| title_full_unstemmed | A concise second-order complexity analysis for unconstrained optimization using high-order regularized models |
| title_short | A concise second-order complexity analysis for unconstrained optimization using high-order regularized models |
| title_sort | concise second order complexity analysis for unconstrained optimization using high order regularized models |
| work_keys_str_mv | AT cartisc aconcisesecondordercomplexityanalysisforunconstrainedoptimizationusinghighorderregularizedmodels AT gouldn aconcisesecondordercomplexityanalysisforunconstrainedoptimizationusinghighorderregularizedmodels AT tointp aconcisesecondordercomplexityanalysisforunconstrainedoptimizationusinghighorderregularizedmodels AT cartisc concisesecondordercomplexityanalysisforunconstrainedoptimizationusinghighorderregularizedmodels AT gouldn concisesecondordercomplexityanalysisforunconstrainedoptimizationusinghighorderregularizedmodels AT tointp concisesecondordercomplexityanalysisforunconstrainedoptimizationusinghighorderregularizedmodels |