ABSTRACT
An adaptive regularization algorithm is proposed that uses Taylor models of the objective of order p, , of the unconstrained objective function, and that is guaranteed to find a first- and second-order critical point in at most function and derivatives evaluations, where and 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.
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 , the usual Euclidean vector norm.
2 When p is even, 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 can be stored explicitly.
Additional information
Funding
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.