A concise second-order complexity analysis for unconstrained optimization using high-order regularized models. (3rd March 2020)

• Record Type: Journal Article
• Authors: Cartis, C.; Gould, N. I. M.; Toint, Ph. L.
• Is Part Of: Optimization methods and software. Volume 35:Number 2(2020)
• Page Start: 243
• Page End: 256
• Publication Date: 2020-03-03
• Subjects: Nonconvex optimization -- regularization methods -- complexity analysis; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2019.1678033
• Languages: English
• ISSNs: 1055-6788

Abstract

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 { ϵ 1 − p + 1 p, ϵ 2 − p + 1 p − 1 } ) 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.