Cubic regularization of Newton method and its global performance. (English) Zbl 1142.90500

Summary: In this paper, we provide theoretical analysis for a cubic regularization of Newton method as applied to unconstrained minimization problem. For this scheme, we prove general local convergence results. However, the main contribution of the paper is related to global worst-case complexity bounds for different problem classes including some nonconvex cases. It is shown that the search direction can be computed by standard linear algebra technique.


90C53 Methods of quasi-Newton type
90C30 Nonlinear programming
Full Text: DOI


[1] Bennet, A.A.: Newton’s method in general analysis. Proc. Nat. Ac. Sci. USA. 2 (10), 592–598 (1916)
[2] Conn, A.B., Gould, N.I.M., Toint, Ph.L.: Trust Region Methods. SIAM, Philadelphia, 2000 · Zbl 0958.65071
[3] Dennis, J.E., Jr., Schnabel, R.B.: Numerical Methods for Unconstrained Optimization and Nonlinear Equations. SIAM, Philadelphia, 1996 · Zbl 0847.65038
[4] Fletcher, R.: Practical Methods of Optimization, Vol. 1, Unconstrained Minimization. John Wiley, NY, 1980 · Zbl 0439.93001
[5] Goldfeld, S., Quandt, R., Trotter, H.: Maximization by quadratic hill climbing. Econometrica. 34, 541–551 (1966) · Zbl 0145.40901
[6] Kantorovich, L.V.: Functional analysis and applied mathematics. Uspehi Matem. Nauk. 3 (1), 89–185 (1948), (in Russian). Translated as N.B.S. Report 1509, Washington D.C. (1952) · Zbl 0034.21203
[7] Levenberg, K.: A method for the solution of certain problems in least squares. Quart. Appl. Math. 2, 164–168 (1944) · Zbl 0063.03501
[8] Marquardt, D.: An algorithm for least-squares estimation of nonlinear parameters. SIAM J. Appl. Math. 11, 431–441 (1963) · Zbl 0112.10505
[9] Nemirovsky, A., Yudin, D.: Informational complexity and efficient methods for solution of convex extremal problems. Wiley, New York, 1983
[10] Nesterov, Yu.: Introductory lectures on convex programming: a basic course. Kluwer, Boston, 2004 · Zbl 1086.90045
[11] Nesterov, Yu., Nemirovskii, A.: Interior-Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia, 1994 · Zbl 0824.90112
[12] Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, NY, 1970 · Zbl 0241.65046
[13] Polyak, B.T.: Gradient methods for minimization of functionals. USSR Comp. Math. Math. Phys. 3 (3), 643–653 (1963) · Zbl 0196.47701
[14] Polyak, B.T.: Convexity of quadratic transformations and its use in control and optimization. J. Optim. Theory and Appl. 99 (3), 553–583 (1998) · Zbl 0961.90074
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.