A concise second-order complexity analysis for unconstrained optimization using high-order regularized models

Journal article

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.

Authors: Cartis, C; Gould, N; Toint, P

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Taylor and Francis
• Journal: Optimization Methods and Software
• Volume: 35
• Issue: 2
• Pages: 243-256
• Publication date: 2019-10-24
• Acceptance date: 2019-10-01
• DOI: 10.1080/10556788.2019.1678033
• EISSN: 1029-4937
• ISSN: 1055-6788
• Language: English
• Keywords: nonconvex optimization; FFR; complexity analysis; regularization methods