A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems. (English) Zbl 0871.90096

Summary: A new algorithm for the solution of large-scale nonlinear complementarity problems is introduced. The algorithm is based on a nonsmooth equation reformulation of the complementarity problem and on an inexact Levenberg-Marquardt-type algorithm for its solution. Under mild assumptions, and requiring only the approximate solution of a linear system at each iteration, the algorithm is shown to be both globally and superlinearly convergent, even on degenerate problems. Numerical results for problems with up to \(10 000\) variables are presented.


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


Full Text: DOI


[1] D.P. Bertsekas,Constrained Optimization and Lagrange Multiplier Methods (Academic, New York, NY, 1982). · Zbl 0572.90067
[2] C. Chen and O.L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems,Computational Optimization and Applications 5 (1996) 97–138. · Zbl 0859.90112
[3] F.H. Clarke.Optimization and Nonsmooth Analysis (Wiley, New York, NY, 1983). · Zbl 0582.49001
[4] R.W. Cottle, J.-S. Pang and R.W. Stone.The Linear Complementarity Problem (Academic, New York, NY, 1992). · Zbl 0757.90078
[5] T. De Luca, F. Facchinei and C. Kanzow. A semismooth equation approach to the solution of nonlinear complementarity problems,Mathematical Programming 75 (1996) 407–439. · Zbl 0874.90185
[6] R.S. Dembo, S.C. Eisenstat and T. Steihaug, Inexact Newton methods,SIAM Journal on Numerical Analysis 19 (1982) 400–408. · Zbl 0478.65030
[7] J.E. Dennis and R.B. Schnabel,Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Prentice-Hall, Englewood Cliffs, NJ, 1983). · Zbl 0579.65058
[8] S.P. Dirkse and M.C. Ferris, MCPLIB: A collection of nonlinear mixed complementarity problems,Optimization Methods and Software 5 (1995) 319–345.
[9] F. Facchinei, Minimization of SC1 functions and the Maratos effect,Operations Research Letters 17 (1995) 131–137. · Zbl 0843.90108
[10] F. Facchinei and J. Soares. A new merit function for nonlinear complementarity problems and a related algorithm.SIAM Journal on Optimization 7 (1997) 225–247. · Zbl 0873.90096
[11] M.C. Ferris and J.-S. Pang, Engineering and economic applications of complementarity problems, Technical Report 95-07, Computer Sciences Department, University of Wisconsin (Madison, WJ, 1995) · Zbl 0891.90158
[12] A. Fischer, A special Newton-type optimization method,Optimization 24 (1992) 269–284. · Zbl 0814.65063
[13] A. Fischer, An NCP-function and its use for the solution of complementarity problems, in: D.-Z. Du, L. Qi and R. Womersley, eds.,Recent Advances in Nonsmooth Optimization (World Scientific, Singapore, 1995) 88–105. · Zbl 0948.90133
[14] A. Fischer, Solution of monotone complementarity problems with locally Lipschitzian functions, Preprint 9/1995, Institute of Numerical Mathematics, Technical University of Dresden (Dresden, 1995).
[15] S.A. Gabriel and J.-S. Pang, An inexact NE/SQP method for solving the nonlinear complementarity problem,Computational Optimization and Applications 1 (1992) 67–91. · Zbl 0794.90071
[16] L. Grippo, F. Lamparicllo and S. Lucidi. A nonmonotone line search technique for Newton’s method.SIAM Journal on Numerical Analysis 23 (1986) 707–716. · Zbl 0616.65067
[17] M.A. Gomes-Ruggiero, M.M. Martínez and S.A. Santos, Solving nonsmooth equations by means of quasi-Newton methods with globalization, in: D.-Z. Du, L. Qi and R. Womersley, eds.,Recent Advances in Nonsmooth Optimization (World Scientific, Singapore, 1995) 121–140. · Zbl 0928.65061
[18] P.T. Harker and J.-S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications,Mathematical Programming 48 (1990) 161–220. · Zbl 0734.90098
[19] P.T. Harker and B. Xiao, Newton’s method for the nonlinear complementarity problem: A B-differentiable equation approach,Mathematical Programming 48 (1990) 339–357. · Zbl 0724.90071
[20] G. Isac,Complementarity Problems, Lecture Notes in Mathematics, Vol. 1528 (Springer, Berlin, 1992).
[21] H. Jiang and L. Qi. A new nonsmooth equations approach to nonlinear complementarity problems.SIAM Journal on Control and Optimization 35 (1997) 178–193. · Zbl 0872.90097
[22] L. Lukšan, Inexact trust region method for large sparse systems of nonlinear equations,Journal of Optimization Theory and Applications 81 (1994) 569–590. · Zbl 0803.65071
[23] O.L. Mangasarian, Equivalence of the complementarity problem to a system of nonlinear equations.SIAM Journal on Applied Mathematics 31 (1976) 89–92. · Zbl 0339.90051
[24] J.M. Martínez and L. Qi, Inexact Newton methods for solving nonsmooth equations,Journal of Computational and Applied Mathematics 60 (1995) 127–145. · Zbl 0833.65045
[25] R. Mifflin, Semismooth and semiconvex functions in constrained optimization,SIAM Journal on Control and Optimization 15 (1977) 957–972. · Zbl 0376.90081
[26] J.J. Moré and D.C. Sorensen, Computing a trust region step,SIAM Journal on Scientific and Statistical Computing 4 (1983) 553–572. · Zbl 0551.65042
[27] J.-S. Pang, Inexact Newton methods for the nonlinear complementarity problem,Mathematical Programming 36 (1986) 54–71. · Zbl 0613.90097
[28] J.-S. Pang, Complementarity problems, in: R. Horst and P.M. Pardalos, eds.,Handbook of Global Optimization (Kluwer Academic, Dordrecht, 1994) 271–338. · Zbl 0833.90114
[29] J.-S. Pang and S.A. Gabriel, NE/SQP. A robust algorithm for the nonlinear complementarity problem.Mathematical Programming 60 (1993) 295–337. · Zbl 0808.90123
[30] J.-S. Pang and L. Qi, Nonsmooth equations: Motivation and algorithms.SIAM Journal on Optimization 3 (1993) 443–465. · Zbl 0784.90082
[31] B.N. Pshenichny and J.M. Danilin,Numerical Methods in Extremal Problems (Mir, Moscow, 1978).
[32] L. Qi. A convergence analysis of some algorithms for solving nonsmooth equations,Mathematics of Operations Research 18 (1993) 227–244. · Zbl 0776.65037
[33] L. Qi and J. Sun, A nonsmooth version of Newton’s method,Mathematical Programming 58 (1993) 353–368. · Zbl 0780.90090
[34] S.M. Robinson, Generalized equations, in: A. Bachem, M. Groetschel and B. Korte, eds.,Mathematical Programming: The State of the Art (Springer, Berlin, 1983) 346–367.
[35] P.K. Subramanian, Gauss-Newton methods for the complementarity problem,Journal of Optimization Theory and Applications 77 (1993) 467–482. · Zbl 0792.90082
[36] Ph.L. Toint, A non-monotone trust-region algorithm for nonlinear optimization subject to convex constraints, Report 92/94, Department of Mathematics, FUNDP (Namur, 1994).
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.