Abstract
An Adaptive Regularisation framework using Cubics (ARC) was proposed for unconstrained optimization and analysed in Cartis, Gould and Toint (Part I, Math Program, doi:10.1007/s10107-009-0286-5, 2009), generalizing at the same time an unpublished method due to Griewank (Technical Report NA/12, 1981, DAMTP, University of Cambridge), an algorithm by Nesterov and Polyak (Math Program 108(1):177–205, 2006) and a proposal by Weiser, Deuflhard and Erdmann (Optim Methods Softw 22(3):413–431, 2007). In this companion paper, we further the analysis by providing worst-case global iteration complexity bounds for ARC and a second-order variant to achieve approximate first-order, and for the latter second-order, criticality of the iterates. In particular, the second-order ARC algorithm requires at most \({\mathcal{O}(\epsilon^{-3/2})}\) iterations, or equivalently, function- and gradient-evaluations, to drive the norm of the gradient of the objective below the desired accuracy \({\epsilon}\), and \({\mathcal{O}(\epsilon^{-3})}\) iterations, to reach approximate nonnegative curvature in a subspace. The orders of these bounds match those proved for Algorithm 3.3 of Nesterov and Polyak which minimizes the cubic model globally on each iteration. Our approach is more general in that it allows the cubic model to be solved only approximately and may employ approximate Hessians.
Similar content being viewed by others
References
Cartis, C., Gould, N.I.M., Toint, Ph.L.: Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results. Math. Program. doi:10.1007/s10107-009-0286-5 (online) (2009)
Conn A.R., Gould N.I.M., Toint Ph.L.: Trust-Region Methods. SIAM, Philadelphia (2000)
Dennis J.E., Moré J.J.: A characterization of superlinear convergence and its application to quasi-Newton methods. Math. Comput. 28(126), 549–560 (1974)
Dennis, J.E., Schnabel, R.B.: Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice-Hall, Englewood Cliffs, New Jersey, USA (1983). Reprinted as Classics in Applied Mathematics 16, SIAM, Philadelphia, USA (1996)
Golub G.H., Van Loan C.F.: Matrix Computations. The John Hopkins University Press, Baltimore (1996)
Gratton S., Mouffe M., Toint Ph.L., Weber-Mendonça M.: A recursive trust-region method in infinity norm for bound-constrained nonlinear optimization. IMA J. Numer. Anal. 28(4), 827–861 (2008)
Gratton S., Sartenaer A., Toint Ph.L.: Recursive trust-region methods for multiscale nonlinear optimization. SIAM J. Optim. 19(1), 414–444 (2008)
Griewank, A.: The modification of Newton’s method for unconstrained optimization by bounding cubic terms. Technical Report NA/12 (1981), Department of Applied Mathematics and Theoretical Physics, University of Cambridge, United Kingdom (1981)
Nesterov Yu.: Introductory Lectures on Convex Optimization. Kluwer, Dordrecht, The Netherlands (2004)
Nesterov Yu.: Accelerating the cubic regularization of Newton’s method on convex problems. Math. Program. 112(1), 159–181 (2008)
Nesterov Yu., Polyak B.T.: Cubic regularization of Newton’s method and its global performance. Math. Program. 108(1), 177–205 (2006)
Nocedal J., Wright S.J.: Numerical Optimization. Springer, New York (1999)
Weiser M., Deuflhard P., Erdmann B.: Affine conjugate adaptive Newton methods for nonlinear elastomechanics. Optim. Methods Softw. 22(3), 413–431 (2007)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported by the EPSRC grant GR/S42170.
Rights and permissions
About this article
Cite this article
Cartis, C., Gould, N.I.M. & Toint, P.L. Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function- and derivative-evaluation complexity. Math. Program. 130, 295–319 (2011). https://doi.org/10.1007/s10107-009-0337-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-009-0337-y
Keywords
- Nonlinear optimization
- Unconstrained optimization
- Cubic regularization
- Newton’s method
- Trust-region methods
- Global complexity bounds
- Global rate of convergence