×

zbMATH — the first resource for mathematics

A nonmonotone Levenberg-Marquardt method for nonlinear complementarity problems under local error bound. (English) Zbl 1359.65093
Summary: In this paper, we propose a new Levenberg-Marquardt algorithm for nonlinear complementarity problems. The algorithm is based on a semismooth equation reformulation of the complementarity problem using the FB function. To obtain the global convergence, we use a modified nonmonotone line search rule. Under the local error bound assumption, which is weaker than the nonsingularity condition, we get the local superlinear/quadratic convergence of the algorithm. 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; minpack
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahn, BH, Iterative methods for linear complementarity problem with upperbounds and lowerbounds, Math Prog, 26, 265-337, (1983)
[2] Clarke FH (1983) Optimization and nonsmooth analysis. Wiley, New York · Zbl 0582.49001
[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
[4] Dirkse, S; Ferris, M, MCPLIB: a collection of nonlinear mixed complementarity problems, Optim Methods Softw, 5, 319-345, (1995)
[5] Du, S; Gao, Y, Convergence analysis of nonmonotne Levenberg-Marquardt algorithms for complementarity problem, Appl Math Comput, 216, 1652-1659, (2010) · Zbl 1202.65073
[6] Facchinei, F; Kanzow, C, A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems, Math Prog, 76, 493-512, (1997) · Zbl 0871.90096
[7] Fischer, A, Solution of monotone complementarity problems with locally Lipschitz functions, Math Prog, 76, 669-713, (1997)
[8] Ferris, MC; Pang, JS, Engineering and economic applications of complementarity problems, SIAM Rev, 39, 669-713, (1997) · Zbl 0891.90158
[9] Gu, NZ; Mo, JT, Incorporating nonmonotone strategies into the trust region method for unconstrained optimization, Appl Math Comput, 55, 2158-2172, (2008) · Zbl 1183.90387
[10] Harker, PT; Pang, JS, Finite-dimensional vriational inequality and nonlinear complementarity problem: a survey of theory, algorithms and applications, Math Program, 48, 161-220, (1990) · Zbl 0734.90098
[11] Kanzow, C, Global convergence properties of some iterative methods for linear complementarity problems, SIAM J Optim, 6, 326-341, (1996) · Zbl 0847.90132
[12] Levenberg, K, A method for the solution of certain nonlinear problems in least squares, Quart Appl Math, 2, 164-166, (1944) · Zbl 0063.03501
[13] Luks̆an L (1994) Inexact trust region method for large sparse systems of nonlinear equations. J Optim Theory Appl 81:569-590
[14] 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
[15] Luo ZQ (2000) New error bounds and their applications to convergence analysis of iterative algorithm. Math Program Ser B 88-341 (2000)
[16] Ma, C; Tang, J, The quadratic convergence of a smoothing Levenberg-Marquardt method for nonlinear complementarity problem, Appl Math Comput, 197, 566-581, (2008) · Zbl 1141.65044
[17] Marquardt, DW, An algorithm for least-squares estimation of nonlinear inequalities, SIAM J Appl Math, 11, 431-441, (1963) · Zbl 0112.10505
[18] Mifflin, R, Semismooth and semiconvex functions in constrained optimization, SIAM J Control Optim, 15, 957-972, (1977) · Zbl 0376.90081
[19] Moré, JJ; Garbow, BS; Hillstrom, KH, Testing unconstrained optimization software, ACM Trans Math Softw, 7, 17-41, (1981) · Zbl 0454.65049
[20] Pang, JS, Error bounds in mathematical programming, Math Program, 79, 299-332, (1997) · Zbl 0887.90165
[21] Pang, JS; Qi, L, Nonsmooth equations: motivation and algorithms, SIAM J Optim, 3, 443-465, (1993) · Zbl 0784.90082
[22] Qi, L; Sun, J, A nonsmooth version of newton’s method, Math Program, 58, 353-367, (1993) · Zbl 0780.90090
[23] Ruggiero MAG, Mart\(\acute{1}\)nez JM, Santos SA (1995) Solving nonsmooth equations by means of quasi-Newton methods with globalization. In: Recent advances in nonsmooth optimization. World Scientific, Singapore, pp 121-140 · Zbl 1104.65061
[24] Yamashita, N; Fukushima, M, On the rate of convergence of the Levenberg-Marquardt method, Computing, 15, 239-249, (2001) · Zbl 1001.65047
[25] 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
[26] Zhang, J; Zhang, X, A smoothing Levenberg-Marquardt method for NCP, Appl Math Comput, 178, 212-228, (2006) · Zbl 1104.65061
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.