×

Modified inexact Levenberg-Marquardt methods for solving nonlinear least squares problems. (English) Zbl 1425.90112

Summary: In the present paper, we propose a modified inexact Levenberg-Marquardt method (LMM) and its global version by virtue of Armijo, Wolfe or Goldstein line-search schemes to solve nonlinear least squares problems (NLSP), especially for the underdetermined case. Under a local error bound condition, we show that a sequence generated by the modified inexact LMM converges to a solution superlinearly and even quadratically for some special parameters, which improves the corresponding results of the classical inexact LMM in [H. Dan et al., Optim. Methods Softw. 17, No. 4, 605–626 (2002; Zbl 1030.65049)]. Furthermore, the quadratical convergence of the global version of the modified inexact LMM is also established. Finally, preliminary numerical experiments on some medium/large scale underdetermined NLSP show that our proposed algorithm outperforms the classical inexact LMM.

MSC:

90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
90C25 Convex programming

Citations:

Zbl 1030.65049

Software:

minpack; UTV
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahookhosh, M., Aragón, F.J., Fleming, R.M.T., Vuongx, P.T.: Local convergence of Levenberg-Marquardt methods under Hölder metric subregularity. arXiv:1703.07461, March 21 (2017)
[2] Armijo, L.: Minimization of functions having continuous partial derivatives. Pac. J. Math. 16, 1-3 (1966) · Zbl 0202.46105 · doi:10.2140/pjm.1966.16.1
[3] Bao, J.F., Li, C., Shen, W.P., Yao, J.C., Guu, S.M.: Approximate Gauss-Newton methods for solving underdetermined nonlinear least squares problems. Appl. Numer. Math. 111, 92-110 (2017) · Zbl 1353.65042 · doi:10.1016/j.apnum.2016.08.007
[4] Behling, R., Fischer, A., Herrich, M., Iusem, A., Ye, Y.: A Levenberg-Marquardt method with approximate projections. Comput. Optim. Appl. 59, 5-26 (2014) · Zbl 1298.90103 · doi:10.1007/s10589-013-9573-4
[5] Ben-Israel, A.: A Newton-Raphson method for the solution of systems of equations. J. Math. Anal. Appl. 15, 243-252 (1966) · Zbl 0139.10301 · doi:10.1016/0022-247X(66)90115-6
[6] Bertsekas, D.P.: Nonlinear Programming. Athena Scientific, Belmont (1995) · Zbl 0935.90037
[7] Björk, A.: Numerical Methods for Least Squares Problems. SIAM, Philadelphia (1996) · Zbl 0847.65023 · doi:10.1137/1.9781611971484
[8] Bonnans, J.F., Ioffe, A.: Second-order sufficiency and quadratic growth for nonisolated minima. Math. Oper. Res. 20, 801-817 (1995) · Zbl 0846.90095 · doi:10.1287/moor.20.4.801
[9] Burke, J.V., Ferris, M.C.: Weak sharp minima in mathematical programming. SIAM J. Control Optim. 31, 1340-1359 (1993) · Zbl 0791.90040 · doi:10.1137/0331063
[10] Burke, J.V., Ferris, M.C.: A Gauss-Newton method for convex composite optimization. Math. Program. 71, 179-194 (1995) · Zbl 0846.90083
[11] Courtier, P., Thepaut, J.N., Hollingsworth, A.: A strategy for operational implementation of 4D-Var, using an incremental approach. Quart. J. R. Meteorol. Soc. 120, 1367-1387 (1994) · doi:10.1002/qj.49712051912
[12] 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
[13] Dembo, R.S., Eisenstat, S.C., Steihaug, T.: Inexact Newton methods. SIAM J. Numer. Anal. 19, 400-408 (1982) · Zbl 0478.65030 · doi:10.1137/0719025
[14] Dennis, J.E., Schnabel, R.B.: Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice-Hall, Englewood Cliffs (1983) · Zbl 0579.65058
[15] Deuflhard, P., Heindl, G.: Affine invariant convergence theorems for Newton’s method and extensions to related methods. SIAM J. Numer. Anal. 16(1), 1-10 (1979) · Zbl 0395.65028 · doi:10.1137/0716001
[16] Fan, J.Y., Pan, J.Y.: Convergence properties of a self-adaptive Levenberg-Marquardt algorithm under local error bound condition. Comput. Optim. Appl. 34, 47-62 (2006) · Zbl 1111.90103 · doi:10.1007/s10589-005-3074-z
[17] Fan, J.Y., Pan, J.Y.: Inexact Levenberg-Marquardt method for nonlinear equations. Discrete Contin. Dyn. Syst. Ser. B 4, 1223-1232 (2004) · Zbl 1059.65043 · doi:10.3934/dcdsb.2004.4.1223
[18] Fan, J.Y., Pan, J.Y.: 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
[19] Fan, J.Y., Yuan, Y.X.: On the quadratic convergence of the Levenberg-Marquardt method without nonsingularity assumption. Computing 74, 23-39 (2005) · Zbl 1076.65047 · doi:10.1007/s00607-004-0083-1
[20] Fischer, A., Shukla, P.K.: A Levenberg-Marquardt algorithm for unconstrained multicriteria optimization. Oper. Res. Lett. 36, 643-646 (2008) · Zbl 1210.90155 · doi:10.1016/j.orl.2008.02.006
[21] Fischer, A., Shukla, P.K., Wang, M.: On the inexactness level of robust Levenberg-Marquardt methods. Optimization 59, 273-287 (2010) · Zbl 1196.65097 · doi:10.1080/02331930801951256
[22] Guo, L., Lin, G.H., Ye, J.J.: Solving mathematical programs with equilibrium constraints. J. Optim. Theory Appl. 166, 234-256 (2015) · Zbl 1327.90233 · doi:10.1007/s10957-014-0699-z
[23] Hanson, P.C.: Rank-Deficient and Discrete Ill-Posed Problems: Numerical Aspects of Linear Inversion. SIAM, Philadelphia (1998) · Zbl 0890.65037 · doi:10.1137/1.9780898719697
[24] Häußer, W.M.: A Kantorovich-type convergence analysis for the Gauss-Newton method. Numer. Math. 48, 119-125 (1986) · Zbl 0598.65025 · doi:10.1007/BF01389446
[25] Hoffman, A.J.: On approximate solutions of systems of linear inequalities. J. Res. Natl. Bur. Stand. 49, 263-265 (1952) · doi:10.6028/jres.049.027
[26] Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, New York (1985) · Zbl 0576.15001 · doi:10.1017/CBO9780511810817
[27] Hu, Y.H., Li, C., Meng, K.W., Qin, J., Yang, X.Q.: Group sparse optimization via \[\ell_{p, q}\] ℓp,q regularization. J. Mach. Learn. Res. 18, 1-52 (2017) · Zbl 1433.90202
[28] Hu, Y.H., Li, C., Yang, X.Q.: On convergence rates of linearized proximal algorithms for convex composite optimization with applications. SIAM J. Optim. 26, 1207-1235 (2016) · Zbl 1338.65159 · doi:10.1137/140993090
[29] Hu, Y.H., Yang, X.Q., Sim, C.-K.: Inexact subgradient methods for quasi-convex optimization problems. Eur. J. Oper. Res. 240, 315-327 (2015) · Zbl 1357.90116 · doi:10.1016/j.ejor.2014.05.017
[30] Kiwiel, K.C., Murty, K.: Convergence of the steepest descent method for minimization quasiconvex functions. J. Optim. Theory Appl. 89(1), 221-226 (1996) · Zbl 0866.90094 · doi:10.1007/BF02192649
[31] Lawless, A.S., Gratton, S., Nichols, N.K.: An investigation of incremental 4D-Var using non-tangent linear models. Quart. J. R. Meteorol. Soc. 131, 459-476 (2005) · doi:10.1256/qj.04.20
[32] Levenberg, K.: A method for the solution of certain nonlinear problems in least squares. Quart. Appl. Math. 2, 164-166 (1944) · Zbl 0063.03501 · doi:10.1090/qam/10666
[33] Li, G.: On the asymptotically well behaved functions and global error bound for convex polynomials. SIAM J. Optim. 20(4), 1923-1943 (2010) · Zbl 1208.90135 · doi:10.1137/080733668
[34] Li, G.: Global error bounds for piecewise convex polynomials. Math. Program. 137, 37-64 (2013) · Zbl 1270.90080 · doi:10.1007/s10107-011-0481-z
[35] Li, C., Hu, N.C., Wang, J.H.: Convergence behavior of Gauss-Newton’s method and extensions of the Smale point estimate theory. J. Complex. 26, 268-295 (2010) · Zbl 1192.65057 · doi:10.1016/j.jco.2010.02.001
[36] Li, C., Wang, X.: On convergence of the Gauss-Newton method for convex composite optimization. Math. Program. 91, 349-356 (2002) · Zbl 1049.90132 · doi:10.1007/s101070100249
[37] Luo, X.D., Luo, Z.Q.: Extension of Hoffman’s error bound to polynomial systems. SIAM J. Optim. 4, 383-392 (1994) · Zbl 0821.90113 · doi:10.1137/0804021
[38] Luo, Z.Q., Pang, J.S.: Error bounds for analytic systems and their applications. Math. Program. 67, 1-28 (1994) · Zbl 0813.90116 · doi:10.1007/BF01582210
[39] Macconi, M., Morini, B., Porcelli, M.: A Gauss-Newton method for solving bound constrained underdetermined nonlinear systems. Optim. Methods Softw. 24, 219-235 (2009) · Zbl 1181.90289 · doi:10.1080/10556780902753031
[40] Marquardt, D.W.: An algorithm for least-squares estimation of nonlinear inequalities. SIAM J. Appl. Math. 11, 431-441 (1963) · Zbl 0112.10505 · doi:10.1137/0111030
[41] Moré, JJ; Watson, GA (ed.), The Levenberg-Marquardt algorithm: implementation and theory, 105-116 (1978), New York · Zbl 0372.65022
[42] Moré, J.J., Garbow, B.S., Hillstrom, K.E.: Testing unconstrained optimization software. ACM Trans. Math. Softw. 7, 17-41 (1981) · Zbl 0454.65049 · doi:10.1145/355934.355936
[43] Ngai, H.V., Théra, M.: Error bounds for convex differentiable inequality systems in Banach spaces. Math. Program. 104, 465-482 (2005) · Zbl 1089.49028 · doi:10.1007/s10107-005-0624-1
[44] Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, New York (1999) · Zbl 0930.65067 · doi:10.1007/b98874
[45] Pang, J.S.: Error bounds in mathematical programming. Math. Program. 79, 299-332 (1997) · Zbl 0887.90165
[46] Porcelli, M.: On the convergence of an inexact Gauss-Newton trust-region method for nonlinear least-squares problems with simple bounds. Optim. Lett. 7, 447-465 (2013) · Zbl 1268.90091 · doi:10.1007/s11590-011-0430-z
[47] Stewart, G.W., Sun, J.G.: Matrix Perturbation Theory. Academic Press, New York (1990) · Zbl 0706.65013
[48] Studniarski, M., Ward, D.E.: Weak sharp minima: characterizations and sufficient conditions. SIAM J. Control Optim. 38, 219-236 (1999) · Zbl 0946.49011 · doi:10.1137/S0363012996301269
[49] Sun, W., Yuan, Y.X.: Optimization Theory and Methods: Nonlinear Programming. Springer, New York (2006) · Zbl 1129.90002
[50] Wang, J.H., Hu, Y.H., Li, C., Yao, J.-C.: Linear convergence of CQ algorithms and applications in gene regulatory network inference. Inverse Probl. 33, 055017 (2017) · Zbl 1368.65080 · doi:10.1088/1361-6420/aa6699
[51] Yamashita, N., Fukushima, M.: On the rate of convergence of the Levenberg-Marquardt method. Comput. Suppl. 15, 239-249 (2001) · Zbl 1001.65047 · doi:10.1007/978-3-7091-6217-0_18
[52] Yang, W.H.: Error bounds for convex polynomials. SIAM J. Optim. 19, 1633-1647 (2008) · Zbl 1191.47068 · doi:10.1137/070689838
[53] Ypma, T.J.: Historical development of the Newton-Raphson method. SIAM Rev. 37, 531-551 (1995) · Zbl 0842.01005 · doi:10.1137/1037125
[54] Zhu, X., Lin, G.H.: Improved convergence results for a modified Levenberg-Marquardt method for nonlinear equations and applications in MPCC. Optim. Methods Softw. 31, 791-804 (2016) · Zbl 1386.90154 · doi:10.1080/10556788.2016.1171863
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.