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\ge 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^{-\frac{p+1}{p}},{ϵ}_2^{-\frac{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.

KEYWORDS:

• Nonconvex optimization
• regularization methods
• complexity analysis

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

C. Cartis http://orcid.org/0000-0002-0963-5550

N. I. M. Gould http://orcid.org/0000-0002-1031-1588

Notes

1 Note that $\Vert \cdot {\Vert }_{[1]}=\Vert \cdot \Vert$, the usual Euclidean vector norm.

2 When p is even, $m(x,s,\sigma )$ is smooth everywhere but at the origin, but a step from s = 0 in the steepest-descent/eigen direction will move to a region for which the model is always smooth.

3 We implicitly assume here that derivatives at $x_k$ can be stored explicitly.

Additional information

Funding

The work of the first author was supported by the Alan Turing Institute, UK. The work of the second author was supported by EPSRC [grant number EP/M025179/1].

Notes on contributors

C. Cartis

C. Cartis holds a PhD in mathematics from the University of Cambridge, and is currently Associate Professor in numerical optimization at the University of Oxford. She was awarded a Leslie Fox Prize in numerical analysis (second place). Her research interests cover numerical optimization with emphasis on methods and analysis for nonconvex problems, and applications in compressed sensing and climate modelling.

N. I. M. Gould

N. I. M. Gould, an STFC Senior Fellow and Professor of Numerical Optimization, has interests in theoretical and practical optimization, and links to linear algebra. He is a SIAM Fellow, a winner of theLeslie Fox and Beale-Orchard Hays prizes, and his most recent book is/Trust-region Methods/(SIAM, 2000), written jointly with Andy Conn and Philippe Toint.

Ph. L. Toint

Ph. L. Toint received his PhD from mathematics from the University of Namur (Belgium) and Cambridge (UK), after which he was appointed as assistant professor and then full professor in mathematics at the University of Namur (Belgium), where he is now emeritus. He was awarded the Beale-Orchard-Hays prize and the Lagrange prize for continuous optimization. He is an inaugural SIAM Fellow, and former chair of the Mathematical Optimisation Society (2010--2013). His research interests are smooth nonlinear optimization, with an emphasis on the algorithmic viewpoint, ranging from convergence theory to numerical considerations and software development, as well as practical and multidisciplinary applications of optimization techniques such as in transportation systems and planning.