Convergence properties of the regularized Newton method for the unconstrained nonconvex optimization. (English) Zbl 1228.90087

Summary: The regularized Newton method (RNM) is one of the efficient solution methods for the unconstrained convex optimization. It is well-known that the RNM has good convergence properties as compared to the steepest descent method and the pure Newton’s method. For example, Li, Fukushima, Qi and Yamashita showed that the RNM has a quadratic rate of convergence under the local error bound condition. Recently, Polyak showed that the global complexity bound of the RNM, which is the first iteration \(k\) such that \(\| \nabla f(x _{k })\| \leq \varepsilon \), is \(O(\varepsilon ^{ - 4})\), where \(f\) is the objective function and \(\varepsilon \) is a given positive constant. In this paper, we consider a RNM extended to the unconstrained “nonconvex” optimization. We show that the extended RNM (E-RNM) has the following properties. (a) The E-RNM has a global convergence property under appropriate conditions. (b) The global complexity bound of the E-RNM is \(O(\varepsilon ^{ - 2})\) if \(\nabla ^{2} f\) is Lipschitz continuous on a certain compact set. (c) The E-RNM has a superlinear rate of convergence under the local error bound condition.


90C26 Nonconvex programming, global optimization
90C53 Methods of quasi-Newton type
Full Text: DOI


[1] Dan, H., Yamashita, N., Fukushima, M.: Convergence properties of the inexact Levenberg-Marquardt method under local error bound conditions. Optim. Methods Softw. 17, 605–626 (2002) · Zbl 1030.65049
[2] Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1985) · Zbl 0576.15001
[3] Li, Y.J., Li, D.H.: Truncated regularized Newton method for convex minimizations. Comput. Optim. Appl. 43, 119–131 (2009) · Zbl 1176.90461
[4] Li, D.H., Fukushima, M., Qil, L., Yamashita, N.: Regularized Newton methods for convex minimization problems with singular solutions. Comput. Optim. Appl. 28, 131–147 (2004) · Zbl 1056.90111
[5] Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, New York (1999) · Zbl 0930.65067
[6] Polyak, R.A.: Regularized Newton method for unconstrained convex optimization. Math. Program., Ser. B 120, 125–145 (2009) · Zbl 1189.90121
[7] Yamashita, N., Fukushima, M.: On the rate of convergence of the Levenberg-Marguardt method. Comput., Suppl (Wien) 15, 227–238 (2001) · Zbl 1001.65047
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.