×
Cartis, Coralia; Gould, Nicholas I. M.; Toint, Philippe L.

Adaptive cubic regularisation methods for unconstrained optimization. I: Motivation, convergence and numerical results. (English) Zbl 1229.90192

Math. Program. 127, No. 2 (A), 245-295 (2011).
The paper is concerned with a general cubic regularization framework for unconstrained optimization which has roots in earlier algorithms. It contains a thorough introduction to relevant contributions and presents an appropriate list of references on this subject. The authors consider the convergence properties. The framework allows for the approximate solution of the key step calculation. Preliminary numerical experiments with small-scale problems are reported.
For Part II see [Math. Program. 130, No. 2 (A), 295–319 (2011; Zbl 1229.90193)].
Reviewer: Francisco Guerra Vazquez (Puebla)

Cited in 7 Reviews
Cited in 140 Documents

MSC:

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
65F10 Iterative numerical methods for linear systems
65H05 Numerical computation of solutions to single equations

Keywords:

nonlinear optimization; unconstrained optimization; cubic regularization; Newton’s method; trust-region methods; global convergence; local convergence

Citations:

Zbl 1229.90193

Software:

SifDec; NewtonLib; CUTEr; HSL-VF05
Cite Review PDF
Full Text: DOI

References:

[1] Byrd R.H., Khalfan H.F., Schnabel R.B.: Analysis of a symmetric rank-one trust region method. SIAM J. Optim. 6(4), 1025–1039 (1996) · Zbl 0923.65035 · doi:10.1137/S1052623493252985
[2] Cartis, C., Gould, N.I.M., Toint, Ph.L.: Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function- and derivative-evaluation complexity, 2007 · Zbl 1229.90193
[3] Conn A.R., Gould N.I.M., Toint Ph.L.: Convergence of quasi-Newton matrices generated by the symmetric rank one update. Math. Program. 50(2), 177–196 (1991) · Zbl 0737.90062 · doi:10.1007/BF01594934
[4] Conn A.R., Gould N.I.M., Toint Ph.L.: Trust-Region Methods. SIAM, Philadelphia (2000) · Zbl 0958.65071
[5] Dembo R.S., Eisenstat S.C., Steihaug T.: Inexact-Newton methods. SIAM J. Numer. Anal. 19(2), 400–408 (1982) · Zbl 0478.65030 · doi:10.1137/0719025
[6] Dembo R.S., Steihaug T.: Truncated-Newton algorithms for large-scale unconstrained optimization. Math. Program. 26(2), 190–212 (1983) · Zbl 0523.90078 · doi:10.1007/BF02592055
[7] 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 · doi:10.1090/S0025-5718-1974-0343581-1
[8] 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, vol. 16. SIAM, Philadelphia, USA (1996) · Zbl 0579.65058
[9] Deuflhard, P.: Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms. Springer Series in Computational Mathematics, vol. 35. Springer, Berlin (2004) · Zbl 1056.65051
[10] Dolan E.D., Moré J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201–213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[11] Gerasoulis A.: A fast algorithm for the multiplication of generalized Hilbert matrices with vectors. Math. Comput. 50(181), 179–188 (1988) · Zbl 0648.65040 · doi:10.1090/S0025-5718-1988-0917825-9
[12] Gerasoulis A., Grigoriadis M.D., Sun L.: A fast algorithm for Trummer’s problem. SIAM J. Sci. Stat. Comput. 8(1), 135–138 (1987) · Zbl 0611.76091 · doi:10.1137/0908026
[13] Golub G.H., Van Loan C.F.: Matrix Computations. The John Hopkins University Press, Baltimore (1996) · Zbl 0865.65009
[14] Gould N.I.M., Lucidi S., Roma M., Toint Ph.L.: Solving the trust-region subproblem using the Lanczos method. SIAM J. Optim. 9(2), 504–525 (1999) · Zbl 1047.90510 · doi:10.1137/S1052623497322735
[15] Gould N.I.M., Orban D., Sartenaer A., Toint Ph.L.: Sensitivity of trust-region algorithms on their parameters. 4OR Q. J. Ital. French Belg. Soc. 3(3), 227–241 (2005) · Zbl 1086.65060
[16] Gould N.I.M., Orban D., Toint Ph.L.: CUTEr (and SifDec), a constrained and unconstrained testing environment, revisited. ACM Trans. Math. Softw. 29(4), 373–394 (2003) · Zbl 1068.90526 · doi:10.1145/962437.962439
[17] 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 (1981)
[18] Griewank A.: The ”global” convergence of Broyden-like methods with a suitable line search. J. Aust. Math. Soc. Ser. B 28, 75–92 (1986) · Zbl 0596.65034 · doi:10.1017/S0334270000005208
[19] Griewank, A., Toint, Ph.L.: Numerical experiments with partially separable optimization problems. Numerical Analysis: Proceedings Dundee 1983. Lecture Notes in Mathematics vol. 1066, pp. 203–220. Springer, Heidelberg (1984) · Zbl 0531.65033
[20] Moré, J.J.: Recent developments in algorithms and software for trust region methods. In: Bachem, A., Grötschel, M., Korte, B. Mathematical Programming: The State of the Art, pp. 258–287. Springer, Heidelberg (1983) · Zbl 0546.90077
[21] Nesterov Yu.: Introductory Lectures on Convex Optimization. Kluwer Academic Publishers, Dordrecht (2004) · Zbl 1086.90045
[22] Nesterov Yu.: Accelerating the cubic regularization of Newton’s method on convex problems. Math. Program. 112(1), 159–181 (2008) · Zbl 1167.90013 · doi:10.1007/s10107-006-0089-x
[23] 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 · doi:10.1007/s10107-006-0706-8
[24] Nocedal J., Wright S.J.: Numerical Optimization. Springer, New York (1999) · Zbl 0930.65067
[25] Thomas, S.W.: Sequential estimation techniques for quasi-Newton algorithms. Ph.D. Thesis, Cornell University, Ithaca (1975)
[26] 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 · doi:10.1080/10556780600605129
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.