×

zbMATH — the first resource for mathematics

A regularized Newton method for degenerate unconstrained optimization problems. (English) Zbl 1258.90106
Summary: A regularized Newton method is presented in this paper to solve unconstrained nonconvex minimization problems without the nonsingularity assumption of solutions. The modified Cholesky factorization method proposed by Cheng and Higham is employed to calculate the regularized Newton step. Under suitable conditions, the global convergence of the regularized Newton method is established, and the fast local convergence result is achieved under the local error bound conditions. Some preliminary numerical results are also reported.

MSC:
90C53 Methods of quasi-Newton type
90C26 Nonconvex programming, global optimization
Software:
CUTE; CUTEr; levmar
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ashcraft C., Grimes R.G., Lewis J.G.: Accurate symmetric indefinite linear equation solvers. SIAM J. Matrix Anal. Appl. 20, 513–561 (1998) · Zbl 0923.65010 · doi:10.1137/S0895479896296921
[2] Avelino, C.P., Moguerza, J.M., Olivares, A., Prieto, F.J.: Combining and scaling descent and negative curvature directions. Math. Program. (2010, to appear). doi: 10.1007/s10107-009-0305-6 · Zbl 1227.49038
[3] Bongartz I., Conn A.R., Gould N.I.M., Toint Ph.L.: CUTE: constrained and unconstrained testing environment. ACM Trans. Math. Softw. 21, 123–160 (1995) · Zbl 0886.65058 · doi:10.1145/200979.201043
[4] Behling, R., Fischer, A.: A unified local convergence analysis of inexact constrained Levenberg– Marquardt methods. Optim. Lett. (2011, online). doi: 10.1007/s11590-011-0321-3 · Zbl 1279.90159
[5] Cheng S.H., Higham N.J.: A modified Cholesky algorithm based on a symmetric indefinite factorization. SIAM J. Matrix Anal. Appl. 19, 1097–1110 (1998) · Zbl 0949.65022 · doi:10.1137/S0895479896302898
[6] 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 · doi:10.1080/1055678021000049345
[7] Fan J.Y.: A modified Levenberg–Marquardt algorithm for singular system of nonlinear equations. J. Comput. Math. 21(5), 625–636 (2003) · Zbl 1032.65053
[8] Fan J.Y.: Convergence rate of the trust region method for nonlinear equations under local error bound condition. Comput. Optim. Appl. 34, 215–227 (2006) · Zbl 1121.65054 · doi:10.1007/s10589-005-3078-8
[9] Fan J.Y., Yuan Y.X.: On the quadratic convergence of the Levenberg–Marquardt method without nonsingularity assumption. Computing 74(1), 23–39 (2005) · Zbl 1076.65047 · doi:10.1007/s00607-004-0083-1
[10] Gill P.E., Murray W., Wright M.H.: Practical Optimization. Academic Press, London (1981)
[11] Higham N.J.: Computing a nearest symmetric positive semidefinite matrix. Linear Algebra Appl. 103, 103–118 (1988) · Zbl 0649.65026 · doi:10.1016/0024-3795(88)90223-6
[12] Kanzow C., Yamashita N., Fukushima M.: Levenberg–Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints. J. Comput. Appl. Math. 172, 375–397 (2004) · Zbl 1064.65037 · doi:10.1016/j.cam.2004.02.013
[13] Li D.H., Fukushima M., Qi L., Yamashita N.: Regularized newton methods for convex minimization problems with singular solutions. Comput. Optim. Appl. 28, 131–147 (2004) · Zbl 1056.90111 · doi:10.1023/B:COAP.0000026881.96694.32
[14] Nocedal J., Wright S.: Numerical Optimization, 2nd edn. Springer, New York (2006) · Zbl 1104.65059
[15] Ueda K., Yamashita N.: Convergence properties of the regularized Newton method for the unconstrained nonconvex optimization. Appl. Math. Optim. 62, 27–46 (2010) · Zbl 1228.90087 · doi:10.1007/s00245-009-9094-9
[16] Yamashita, N., Fukushima, M.: On the rate of convergence of the Levenberg–Marquardt method. Computing (Suppl 15), 237–249 (2001) · Zbl 1001.65047
[17] Zhou G., Toh K.C.: Superlinear convergence of a Newton-type algorithm for monotone equations. J. Optim. Theory Appl. 125(1), 205–221 (2005) · Zbl 1114.65055 · doi:10.1007/s10957-004-1721-7
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.