Solution of monotone complementarity problems with locally Lipschitzian functions. (English) Zbl 0871.90097

Summary: The paper deals with complementarity problems \(\text{CP}(F)\), where the underlying function \(F\) is assumed to be locally Lipschitzian. Based on a special equivalent reformulation of \(\text{CP}(F)\) as a system of equations \(\Phi(x)=0\) or as the problem of minimizing the merit function \(\Psi=\frac{1}{2}|\Phi|_2^2\), we extend results which hold for sufficiently smooth functions \(F\) to the nonsmooth case.
In particular, if \(F\) is monotone in a neighbourhood of \(x\), it is proved that \(0\in\partial\Psi(x)\) is necessary and sufficient for \(x\) to be a solution of \(\text{CP}(F)\). Moreover, for monotone functions \(F\), a simple derivative-free algorithm that reduces \(\Psi\) is shown to possess global convergence properties. Finally, the local behaviour of a generalized Newton method is analyzed. To this end, the result by Mifflin that the composition of semismooth functions is again semismooth is extended to \(p\)-order semismooth functions. Under a suitable regularity condition and if \(F\) is \(p\)-order semismooth the generalized Newton method is shown to be locally well defined and superlinearly convergent with the order of \(1+p\).


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


Full Text: DOI


[1] S.C. Billups and M.C. Ferris, QPCOMP: A quadratic programming based solver for mixed complementarity problems,Mathematical Programming 76 (1997) 533–562 (this issue). · Zbl 0873.90095
[2] B. Chen and P.T. Harker, Smooth approximations to nonlinear complementarity problems, Technical Report, Department of Management and Systems, College of Business and Economics, Washington State University (Pullman, WA 1995). · Zbl 0879.90177
[3] 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
[4] F.H. Clarke,Optimization and Nonsmooth Analysis (Wiley, New York, 1983). · Zbl 0582.49001
[5] R.W. Cottle, J.-S. Pang and R.E. Stone,The Linear Complementarity Problem (Academic, New York, 1992).
[6] T. De Luca, F. Facchinci and C. Kanzow, A semismooth equation approach to the solution of nonlinear complementarity problems,Mathematical Programming 75 (1996) 407–439. · Zbl 0874.90185
[7] S.P. Dirkse and M.C. Ferris, The PATH solver: A non-monotone stabilization scheme for mixed complementarity problems.Optimization Methods and Software 5 (1995) 123–156.
[8] F. Facchinei, A. Fischer and C. Kanzow, A semismooth Newton method for variational inequalities: Theoretical results and preliminary numerical experience, Preprint MATH-NM-21-1995, Institute for Numerical Mathematics, Technical University of Dresden (Dresden, 1995).
[9] 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
[10] M.C. Ferris and D. Ralph, Projected gradient methods for nonlinear complementarity problems via normal maps, in: D.Z. Du, L. Qi and R.S. Womersley, eds.,Recent Advances in Nonsmooth Optimization (World Scientific, Singapore, 1995) 57–87. · Zbl 0946.90090
[11] M.C. Ferris and S. Lucidi, Nonmonotone stabilization methods for nonlinear equations,Journal of Optimization Theory and Applications 81 (1994) 53–71. · Zbl 0803.65070
[12] A. Fischer, A special Newton-type optimization method,Optimization 24 (1992) 269–284. · Zbl 0814.65063
[13] A. Fischer, A Newton-type method for positive semidefinite linear complementarity problems,Journal of Optimization Theory and Applications 86 (1995) 585–608. · Zbl 0839.90121
[14] A. Fischer, On the superlinear convergence of a Newton-type method for LCP under weak conditions,Optimization Methods and Software 6 (1995) 83–107.
[15] A. Fischer, An NCP-function and its use for the solution of complementarity problems, in: D.Z. Du, L. Qi and R.S. Womersley, eds.,Recent Advances in Nonsmooth Optimization (World Scientific, Singapore, 1995) 88–105. · Zbl 0948.90133
[16] A. Friedlander, J.M. Martinez and S.A. Santos, Solution of linear complementarity problems using minimization with simple bounds,Global Optimization 6 (1995) 253–267. · Zbl 0835.90101
[17] C. Geiger and C. Kanzow, On the resolution of monotone complementarity problems,Computational Optimization and Applications 5 (1996) 155–173. · Zbl 0859.90113
[18] P.T. Harker and B. Xian, Newton’s method for the nonlinear complementarity problem: a B-differentiable equation approach,Mathematical Programming 48 (1990) 339–357. · Zbl 0724.90071
[19] J.-B. Hiriart-Urruty and C. Lemaréchal,Convex Analysis and Minimization Algorithms (Springer, Heidelberg, 1993).
[20] H. Jiang, Unconstrained minimization approaches to nonlinear complementarity problems,Journal of Global Optimization 9 (1996) 169–181. · Zbl 0868.90122
[21] H. Jiang and L. Qi, Local uniqueness and convergence of iterative methods for nonsmooth variational inequalities,Journal of Mathematical Analysis and Applications 196 (1995) 314–331. · Zbl 0845.65028
[22] H. Jiang and L. Qi, Globally and superlinearly convergent trust region algorithm for convex SC1 minimization problems and its application to stochastic programs,Journal of Optimization Theory and Applications 90 (1996) 653–673. · Zbl 0866.90093
[23] 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
[24] S.-P. Han, J.-S. Pang and N. Rangaraj, Globally convergent Newton methods for nonsmooth equations,Mathematics of Operations Research 17 (1992) 586–607. · Zbl 0777.90057
[25] C. Kanzow, Some equation-based methods for the nonlinear complementarity problem,Optimization Methods and Saftware 3 (1994) 327–340.
[26] C. Kanzow, An unconstrained optimization technique for large-scale linearly constrained convex minimization problems,Computing 53 (1994) 101–117. · Zbl 0820.90099
[27] C. Kanzow, Global convergence properties of some iterative methods for linear complementarity problems,SIAM Journal on Optimization, to appear. · Zbl 0847.90132
[28] M. Kojima and S. Shindo, Extensions of Newton and quasi-Newton methods to systems ofPC 1 equations,Journal of Operations Research Society of Japan 29 (1986) 352–374. · Zbl 0611.65032
[29] B. Kummer, Newton’s method for non-differentiable functions, in: J. Guddat et al., eds.,Mathematical Research, Advances in Mathematical Optimization (Akademie, Berlin, 1988) pp. 114–125. · Zbl 0662.65050
[30] B. Kummer, Newton’s method based on generalized derivatives for nonsmooth functions: Convergence analysis, in: W. Oettli and D. Pallaschke, eds.,Advances in Optimization, Lecture Notes in Economics and Mathematical Systems, Vol. 382 (Springer, Heidelberg, 1992) pp. 171–194. · Zbl 0768.49012
[31] 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
[32] O.L. Mangasarian and M.V. Solodov, Nonlinear complementarity as unconstrained and constrained minimization,Mathematical Programming 62 (1993) 277–297. · Zbl 0813.90117
[33] R. Mifflin, Semismooth and semiconvex functions in constrained optimization,SIAM Journal on Control and Optimization 15 (1977) 959–972. · Zbl 0376.90081
[34] J.J. Moré, Global methods for nonlinear complementarity problems,Mathematics of Operations Research, to appear.
[35] J.-S. Pang, Newton’s method for B-differentiable equations,Mathematics of Operations Research 15 (1990) 311–341. · Zbl 0716.90090
[36] J.-S. Pang, A B-differentiable equation-based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems,Mathematical Programming 51 (1991) 101–131. · Zbl 0733.90063
[37] 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
[38] J.-S. Pang and L. Qi, Nonsmooth equations: Motivation and algorithms,SIAM Journal on Optimization 3 (1993) 443–465. · Zbl 0784.90082
[39] J.-S. Pang and L. Qi, A globally convergent Newton method for convex SC1 minimization problems,Journal of Optimization Theory and Applications 85 (1995) 633–648. · Zbl 0831.90095
[40] L. Qi, Convergence analysis of some algorithms for solving nonsmooth equations,Mathematics of Operations Research 18 (1993) 227–244. · Zbl 0776.65037
[41] L. Qi and H. Jiang, Karush-Kuhn-Tucker equations and convergence analysis of Newton methods and quasi-Newton methods for solving these equations,Mathematics of Operations Research, to appear. · Zbl 0881.65054
[42] L. Qi and J. Sun, A nonsmooth version of Newton’s method,Mathematical Programming 58 (1993) 353–367. · Zbl 0780.90090
[43] D. Ralph, Global convergence of damped Newton’s method for nonsmooth equations via the path search,Mathematics of Operations Research 19 (1994) 352–389. · Zbl 0819.90102
[44] S.M. Robinson, Mathematical foundations of nonsmooth embedding methods,Mathematical Programming 48 (1990) 221–229. · Zbl 0728.90084
[45] S.M. Robinson, Newton’s method for a class of nonsmooth functions,Set Valued Analysis 2 (1994) 291–305. · Zbl 0804.65062
[46] R.T. Rockafellar, Computational schemes for large-scale problems in extended linear quadratic programming,Mathematical Programming 48 (1990) 447–474. · Zbl 0735.90050
[47] R.T. Rockafellar and R.J.-B. Wets, A Lagrangian finite-generation technique for solving linear-quadratic problems in stochastic programming,Mathematical Programming Study 28 (1986) 63–93. · Zbl 0599.90090
[48] P.K. Subramanian, Gauss-Newton methods for the complementarity problem,Journal of Optimization Theory and Applications 77 (1993) 467–482. · Zbl 0792.90082
[49] P. Tseng, Growth behaviour of a class of merit functions for the nonlinear complementarity problem,Journal of Optimization Theory and Applications 89 (1996) 17–37. · Zbl 0866.90127
[50] P. Tseng, An infeasible path-following method for monotone complementarity problem,SIAM Journal on Optimization, to appear. · Zbl 0882.90123
[51] P. Tseng, N. Yamashita and M. Fukushima, Equivalence of complementarity problems to differentiable minimization: A unified approach,SIAM Journal on Optimization, to appear. · Zbl 0853.65067
[52] N. Yamashita and M. Fukushima, On stationary points of the implicit Lagrangian for nonlinear complementarity problems,Journal of Optimization Theory and Applications 84 (1995) 653–663. · Zbl 0824.90131
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.