×

Global complexity bound of the inexact Levenberg-Marquardt method. (English) Zbl 1413.65243

Summary: In this paper, we investigate the global complexity bound for the inexact Levenberg-Marquardt method, where the Jacobian may be perturbed and the solution is possibly not exact. Under reasonable assumptions, we show that the global complexity bound is \(O(\varepsilon^{-2})\), which is the same as the exact case. We also show that it can be reduced to \(O(\lg\varepsilon^{-1})\) under some regularity assumption.

MSC:

65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
49M15 Newton-type methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Fan, J, The modified Levenberg-Marquardt method for nonlinear equations with cubic convergence, Math. Comput., 81, 447-466, (2012) · Zbl 1242.65103 · doi:10.1090/S0025-5718-2011-02496-8
[2] Fan, J, A Shamanskii-like Levenberg-Marquardt method for nonlinear equations, Comput. Optim. Appl., 56, 63-80, (2013) · Zbl 1282.90176 · doi:10.1007/s10589-013-9549-4
[3] 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
[4] Fan, J; Pan, J, On the convergence rate of the inexact Levenberg-Marquardt method, J. Ind. Manag. Optim., 7, 199-210, (2011) · Zbl 1214.90112 · doi:10.3934/jimo.2011.7.199
[5] Cartis, C; Gould, N; Toint, P, On the complexity of steepest descent, newton’s and regularized newton’s methods for nonconvex unconstrained optimization problems, SIAM J. Optim., 20, 2833-2852, (2010) · Zbl 1211.90225 · doi:10.1137/090774100
[6] Cartis, C; Gould, NIM; Toint, PL, Adaptive cubic regularisation methods for unconstrained optimization. part II: worst-case function- and derivative-evaluation complexity, Math. Program., 130, 295-319, (2011) · Zbl 1229.90193 · doi:10.1007/s10107-009-0337-y
[7] Grapiglia, GN; Yuan, J; Yuan, YX, On the convergence and worst-case complexity of trust-region and regularization methods for unconstrained optimization, Math. Program., 152, 491-520, (2015) · Zbl 1319.90065 · doi:10.1007/s10107-014-0794-9
[8] Nesterov, Y, Modified Gauss-Newton scheme with worst case guarantees for global performance, Optim. Methods Softw., 22, 469-483, (2007) · Zbl 1136.65051 · doi:10.1080/08927020600643812
[9] Ueda, K; Yamashita, N, On a global complexity bound of the Levenberg-Marquardt method, J. Optim. Theory Appl., 147, 443-453, (2010) · Zbl 1203.90152 · doi:10.1007/s10957-010-9731-0
[10] Ueda, K; Yamashita, N, Global complexity bound analysis of the Levenberg-Marquardt method for nonsmooth equations and its application to the nonlinear complementarity problem, J. Optim. Theory Appl., 152, 450-467, (2012) · Zbl 1250.90116 · doi:10.1007/s10957-011-9907-2
[11] Zhao, R; Fan, J, Global complexity bound of the Levenberg-Marquardt method, Optim. Methods Softw., 31, 805-814, (2016) · Zbl 1406.65037 · doi:10.1080/10556788.2016.1179737
[12] Fan, J, A modified Levenberg-Marquardt algorithm for singular system of nonlinear equations, J. Comput. Math., 21, 625-636, (2003) · Zbl 1032.65053
[13] Powell, MJD, Convergence properties of a class of minimization algorithms, Nonlinear Program., 2, 1-27, (1975) · Zbl 0321.90045
[14] Nocedal, J., Wright, S.J.: Numerical optimization. Springer series in operations research, 2nd edn. Springer, New York (2006) · Zbl 1104.65059
[15] Steihaug, T, The conjugate gradient method and trust regions in large scale optimization, SIAM J. Numer. Anal., 20, 626-637, (1983) · Zbl 0518.65042 · doi:10.1137/0720042
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.