zbMATH — the first resource for mathematics

Adaptive cubic regularisation methods for unconstrained optimization. II: Worst-case function- and derivative-evaluation complexity. (English) Zbl 1229.90193
Summary: An adaptive regularisation framework using cubics (ARC) was proposed for unconstrained optimization and analysed in Part I [Math. Program. 127, No. 2 (A), 245–295 (2011; Zbl 1229.90192)], generalizing at the same time an unpublished method due to A. Griewank [“The modification of Newton’s method for unconstrained optimization by bounding cubic terms”, Technical Report NA/12, 1981, DAMTP, University of Cambridge (1981)], an algorithm by Y. Nesterov and B. T. Polyak [Math. Program. 108, No. 1 (A), 177–205 (2006; Zbl 1142.90500)] and a proposal by M. Weiser, P. Deuflhard and B. Erdmann [Optim. Methods Softw. 22, No. 3, 413–431 (2007; Zbl 1128.74007)]. 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 \(O(\varepsilon^{-3/2})\) iterations, or equivalently, function- and gradient-evaluations, to drive the norm of the gradient of the objective below the desired accuracy \({\varepsilon}\), and \(O(\varepsilon^{-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 [loc. cit.] 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.

90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
49M37 Numerical methods based on nonlinear programming
49M15 Newton-type methods
58C15 Implicit function theorems; global Newton methods on manifolds
90C60 Abstract computational complexity for mathematical programming problems
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] 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) · Zbl 1229.90192
[2] Conn A.R., Gould N.I.M., Toint Ph.L.: Trust-Region Methods. SIAM, Philadelphia (2000) · Zbl 0958.65071
[3] 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) · Zbl 0282.65042
[4] 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) · Zbl 0579.65058
[5] Golub G.H., Van Loan C.F.: Matrix Computations. The John Hopkins University Press, Baltimore (1996) · Zbl 0865.65009
[6] 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) · Zbl 1156.65060
[7] Gratton S., Sartenaer A., Toint Ph.L.: Recursive trust-region methods for multiscale nonlinear optimization. SIAM J. Optim. 19(1), 414–444 (2008) · Zbl 1163.90024
[8] 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)
[9] Nesterov Yu.: Introductory Lectures on Convex Optimization. Kluwer, Dordrecht, The Netherlands (2004) · Zbl 1086.90045
[10] Nesterov Yu.: Accelerating the cubic regularization of Newton’s method on convex problems. Math. Program. 112(1), 159–181 (2008) · Zbl 1167.90013
[11] Nesterov Yu., Polyak B.T.: Cubic regularization of Newton’s method and its global performance. Math. Program. 108(1), 177–205 (2006) · Zbl 1142.90500
[12] Nocedal J., Wright S.J.: Numerical Optimization. Springer, New York (1999) · Zbl 0930.65067
[13] Weiser M., Deuflhard P., Erdmann B.: Affine conjugate adaptive Newton methods for nonlinear elastomechanics. Optim. Methods Softw. 22(3), 413–431 (2007) · Zbl 1128.74007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.