×

A Levenberg-Marquardt method for nonlinear complementarity problems based on nonmonotone trust region and line search techniques. (English) Zbl 1398.65122

Summary: Using the FB function, we propose a new Levenberg-Marquardt algorithm for nonlinear complementarity problem. To obtain the global convergence, the algorithm uses the nonmonotone trust region and line search techniques under a convenient boundedness assumption. Furthermore, we get local superlinear/quadratic convergence of the algorithm under a nonsingularity condition. Some numerical examples are given to illustrate the performance and efficiency of the presented algorithm.

MSC:

65K05 Numerical mathematical programming methods
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)

Software:

MCPLIB
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ferris, MC; Pang, J-S, Engineering and economic applications of complementarity problems, SIAM Rev., 39, 669-713, (1997) · Zbl 0891.90158 · doi:10.1137/S0036144595285963
[2] Chen, B; Harker, PT, Smoothing approximations to nonlinear complementarity problems, SIAM J. Optim., 7, 403-423, (1997) · Zbl 0879.90177 · doi:10.1137/S1052623495280615
[3] Luca, TD; Facchinei, F; Kanzow, C, A semismooth equation approach to the solution of nonlinear complementarity problems, Math. Prog., 75, 407-439, (1996) · Zbl 0874.90185
[4] Fischer, A, Solution of monotone complementarity problems with locally Lipschitz functions, Math. Prog., 76, 669-713, (1997)
[5] Chen, X; Qi, L; Sun, D, Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities, Math. Comput., 67, 519-540, (1998) · Zbl 0894.90143 · doi:10.1090/S0025-5718-98-00932-6
[6] Ma, C; Tang, J; Chen, XH, A globally convergent Levenberg-Marquardt method for solving nonlinear complementarity problem, Math. Comput., 192, 370-381, (2007) · Zbl 1193.90205
[7] Xie, Y; Ma, C, A smoothing Levenberg-Marquardt altorithm for solving a class of stochastic linear complementarity problem, Appl. Math. Comput., 217, 4459-4472, (2011) · Zbl 1217.65114
[8] Wang, X; Ma, C; Li, Meiyan, A smoothing trust region method for NCPs based on the smoothing generalized fischer-burmeister function, J. Comput. Math., 29, 261-286, (2011) · Zbl 1249.90289
[9] Chen, B; Ma, C, Superlinear/quadratic smoothing Broyden-like method for the generalized nonlinear complementarity problem, Nonlinear Anal. Real World Appl., 12, 1250-1263, (2011) · Zbl 1207.65077 · doi:10.1016/j.nonrwa.2010.09.021
[10] Tang, J; Ma, C, A smoothing Newton method for solving a class of stochastic linear complementarity problems, Nonlinear Anal. Real World Appl., 12, 3585-3601, (2011) · Zbl 1231.65113 · doi:10.1016/j.nonrwa.2011.06.017
[11] Chen, B; Ma, C, A new smoothing Broyden-like method for solving nonlinear complementarity problem with a P0-function, J. Glob. Optim., 51, 473-495, (2011) · Zbl 1269.90114 · doi:10.1007/s10898-010-9640-7
[12] Ma, C, A new smoothing and regularization Newton method for \(P_0\)-NCP, J. Glob. Optim., 48, 241-261, (2010) · Zbl 1228.90127 · doi:10.1007/s10898-009-9489-9
[13] Nocedal, J., Yuan, Y.X.: Combining trust region and line search techniques. In: Advances in Nonlinear Programming (Beijing, 1996), Appl. Optim., Vol .14, pp. 153-175. Kluwer Acad. Publ., Dordrecht (1998) · Zbl 0909.90243
[14] Zhang, H; Hager, WW, A nonmonotone line search technique and its application to unconstrained optimization, SIAM J. Optim., 14, 1043-1056, (2004) · Zbl 1073.90024 · doi:10.1137/S1052623403428208
[15] Qi, L; Sun, D; Zhou, G, A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems, Math. Prog., 87, 1-35, (2000) · Zbl 0989.90124 · doi:10.1007/s101079900127
[16] Yu, H; Pu, D, Smoothing Levenberg-Marquardt method for general nonlinear complementarity problems under local error bound, Appl. Math., 35, 1337-1348, (2011) · Zbl 1211.90253
[17] Yang, Y; Qi, L, Smoothing trust region methods for nonlinear complementarity problems with \(P_0\)-function, Ann. Oper. Res., 133, 99-117, (2005) · Zbl 1119.90062 · doi:10.1007/s10479-004-5026-x
[18] Ahn, BH, Iterative methods for linear complementarity problems with upperbounds on primary variables, Math. Prog., 26, 295-315, (1983) · Zbl 0506.90081 · doi:10.1007/BF02591868
[19] Pang, J-S; Qi, L, Nonsmooth equations: motivation and algorithms, SIAM J. Optim., 3, 443-465, (1993) · Zbl 0784.90082 · doi:10.1137/0803021
[20] Kanzow, C, Global convergence properties of some iterative methods for linear complementarity problems, SIAM J. Optim., 6, 326-341, (1996) · Zbl 0847.90132 · doi:10.1137/0806019
[21] Kanzow, C, Some equation-based methods for the nonlinear complementarity problem, Optim. Method. Softw., 3, 327-340, (1994) · doi:10.1080/10556789408805573
[22] Dirkse, S; Ferris, M, MCPLIB: a collection of nonlinear mixed complementarity problems, Optim. Methods Softw., 5, 319-45, (1995) · doi:10.1080/10556789508805619
[23] 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
[24] Marquardt, DW, An algorithm for least-squares estimation of nonlinear inequalities, SIAM J. Appl. Math., 11, 431-441, (1963) · Zbl 0112.10505 · doi:10.1137/0111030
[25] Yamashita, N; Fukushima, M, On the rate of convergence of the Levenberg-Marquardt method, Computing, 15, 239-249, (2001) · Zbl 1001.65047
[26] Qi, L; Sun, J, A nonsmooth version of newton’s method, Mathe. Prog., 58, 353-367, (1993) · Zbl 0780.90090 · doi:10.1007/BF01581275
[27] Clarke, FH, Generalized gradients and applications, Trans. Am. Math. Soc., 205, 247-262, (1975) · Zbl 0307.26012 · doi:10.1090/S0002-9947-1975-0367131-6
[28] Dan, H; Yamashita, N; Fukushima, M, Convergence properties of the inexact Levenberg-Marquardt method under local error bound conditions, Optimiz. Methods Softw., 17, 605-626, (2002) · Zbl 1030.65049 · doi:10.1080/1055678021000049345
[29] Zhang, J; Zhang, X, A smoothing Levenberg-Marquardt method for NCP, Appl. Math. Comput., 178, 212-228, (2006) · Zbl 1104.65061 · doi:10.1016/j.cam.2005.10.034
[30] Du, S; Gao, Y, Convergence analysis of nonmonotone Levenberg-Marquardt algorithms for complementarity, Appl. Math. Comput., 216, 1652-1659, (2010) · Zbl 1202.65073
[31] Fan, JY, A modified Levenberg-Marquardt algorithm for singular system of nonlinear equations, Math. Comput., 5, 625-636, (2003) · Zbl 1032.65053
[32] Yamashita, N; Fukushima, M, Modified Newton methods for solving a semismooth reformulation of monotone complementarity problem, Math. Prog., 76, 469-491, (1997) · Zbl 0872.90102
[33] Gao, DY, Analytic solutions and triality theory for nonconvex and nonsmooth variational problems with applications, Nonlinear Anal., 42, 1161-1193, (2000) · Zbl 0983.49024 · doi:10.1016/S0362-546X(99)00129-7
[34] Powell, MJD, Convergence properties of a class of minimization algorithms, Nonlinear Prog., 2, 1-27, (1975) · Zbl 0321.90045
[35] Dennis, J.E., Schnabel, R.B.: Numerical methods for unconstrained optimization and nonlinear equations. SIAM, Philadelphia (1996) · Zbl 0847.65038 · doi:10.1137/1.9781611971200
[36] Ruggiero, M.A.G., Martínez, J.M., Santos, S.A.: Solving nonsmooth equations by means of quasi-Newton methods with globalization. In: Recent Advances in Nonsmooth Optimization, pp. 121-140. World Scientific, Singapore (1995)
[37] Spedicato, E; Huang, Z, Numerical experience with Newton-like methods for nonlinear algebraic systems, Computing, 58, 69-89, (1997) · Zbl 0866.65033 · doi:10.1007/BF02684472
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.