A Newton-type method for positive-semidefinite linear complementarity problems. (English) Zbl 0839.90121

Summary: The paper presents a damped and perturbed Newton-type method for solving linear complementarity problems with positive-semidefinite matrices \(M\). In particular, the following properties hold: all occurring subproblems are linear equations: each subproblem is uniquely solvable without any assumption; every accumulation point generated by the method solves the linear complementarity problem.
The additional property of \(M\) to be an \(R_0\)-matrix is sufficient, but not necessary, for the boundedness of the iterates. Provided that \(M\) is positive definite on a certain subspace, the method converges \(Q\)-quadratically.


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


[1] Fischer, A.,A Special Newton-Type Optimization Method, Optimization, Vol. 24, pp. 269–284, 1992. · Zbl 0814.65063
[2] Fischer, A., andSchönefeld, K.,Some Iterative Methods for Quadratic Programming, Technical Report No. 07-09-91, Department of Mathematics, Dresden University of Technology, 1991.
[3] Fischer, A.,A Globally and Locally Q-Quadratically Convergent Newton-Type Method for Positive-Semidefinite Linear Complementarity Problems, Technical Report No. MATH-NM-04-1992, Department of Mathematics, Dresden University of Technology, 1992.
[4] Mangasarian, O. L.,Equivalence of the Complementarity Problem to a System of Nonlinear Equations, SIAM Journal on Applied Mathematics, Vol. 31, pp. 89–92, 1976. · Zbl 0339.90051
[5] Wierzbicki, A. P.,Note on the Equivalence of Kuhn-Tucker Complementarity Conditions to an Equation, Journal of Optimization Theory and Applications, Vol. 37, pp. 401–405, 1982. · Zbl 0465.90088
[6] Aganagić, M.,Newton’s Method for Linear Complementarity Problems, Mathematical Programming, Vol. 28, pp. 349–362, 1984. · Zbl 0533.90088
[7] Grippo, L., andLucidi, S.,A Differentiable Exact Penalty Function for Bound-Constrained Quadratic Programming, Optimization, Vol. 22, pp. 557–578, 1991. · Zbl 0734.90063
[8] Di Pillo, G., andGrippo, L.,An Exact Penalty Method with Global Convergence Properties for Nonlinear Programming Problems, Mathematical Programming, Vol. 36, pp. 1–18, 1986. · Zbl 0631.90061
[9] Kojima, M., andShindo, S.,Extension of Newton and Quasi-Newton Methods to Systems of PC 1-Equations, Journal of the Operations Research Society of Japan, Vol. 29, pp. 352–374, 1986. · Zbl 0611.65032
[10] Kummer, B.,Newton’s Method for Nondifferentiable Functions, Mathematical Research, Advances in Mathematical Optimization, Edited by J. Guddat et al., Akademie Verlag, Berlin, Germany, pp. 114–125, 1988.
[11] Kummer, B.,Newton’s Method Based on Generalized Derivatives for Nonsmooth Functions: Convergence Analysis, Working Paper, Department of Mathematics, Humboldt University, Berlin, Germany, 1991.
[12] Robinson, S. M.,Newton’s Method for a Class of Nonsmooth Functions, Manuscript, Department of Industrial Engineering, University of Wisconsin, Madison, Wisconsin, 1988.
[13] Ralph, D.,Global Convergence of Damped Newtons Method for Nonsmooth Equations via the Path Search, Technical Report No. TR 90-1181, Department of Computer Science, Cornell University, Ithaca, New York, 1990.
[14] Pang, J. S.,Newton’s Method for B-Differentiable Equations, Mathematics of Operations Research, Vol. 15, pp. 311–341, 1990. · Zbl 0716.90090
[15] Harker, P. T., andPang, J. S.,A Damped Newton Method for the Linear Complementarity Problem, Computational Solution of Nonlinear Systems of Equations, Lectures in Applied Mathematics, Edited by G. Allgower and K. Georg, American Mathematical Society, Providence, Rhode Island, Vol. 26, pp. 265–284, 1990.
[16] Pang, J. S.,A B-Differentiable Equation-Based, Globally and Locally Quadratically Convergent Algorithm for Nonlinear Programs, Complementarity, and Variational Inequality Problems, Mathematical Programming, Vol. 51, pp. 101–131, 1991. · Zbl 0733.90063
[17] Burmeister, W., Private Communication, Dresden, Germany, 1985.
[18] Clarke, F. H.,Optimization and Nonsmooth Analysis, Wiley, New York, New York, 1983. · Zbl 0582.49001
[19] Pšeničnyj, B. N., andDanilin, Ju. M.,Numerische Methoden für Extremalaufgaben, Deutscher Verlag der Wissenschaften, Berlin, Germany, 1982.
[20] Schwetlick, H.,Numerische Lösung Nichtlinearer Gleichungen, Deutscher Verlag der Wissenschaften, Berlin, Germany, 1979.
[21] Mangasarian, O. L.,Locally Unique Solutions of Quadratic Programs, Linear, and Nonlinear Complementarity Problems, Mathematical Programming., Vol. 19, pp. 200–212, 1980. · Zbl 0442.90089
[22] Cottle, R. W., Pang, J. S., andStone, R. E.,The Linear Complementarity Problem, Academic Press, San Diego, California, 1992. · Zbl 0757.90078
[23] Watson, L. T.,Solving the Nonlinear Complementarity Problem by a Homotopy Method, SIAM Journal on Control and Optimization, Vol. 17 pp. 36–46, 1979. · Zbl 0407.90083
[24] Pang, J. S.,Solution Differentiability and Continuation of Newton’s Method for Variational Inequality Problems over Polyhedral Sets, Journal of Optimization Theory and Applications, Vol. 66, pp. 121–135, 1990. · Zbl 0681.49011
[25] Kojima, M., Mizuno, S., andNoma, T.,A New Continuation Method for Complementarity Problems with Uniform P-Functions, Mathematical Programming, Vol. 43, pp. 107–114, 1989. · Zbl 0673.90084
[26] Robinson, S. M.,Generalized Equations and Their Solution, Part 1: Basic Theory, Mathematical Programming Studies, Vol. 10, pp. 128–141, 1979. · Zbl 0404.90093
[27] Leder, D.,Automatische Schrittweitensteuerung bei global konvergenten Einbettungsmethoden, Zeitschrift für Angewandte Mathematik und Mechanik, Vol. 54, pp. 319–324, 1974. · Zbl 0284.65044
[28] Burmeister, W., Hess, W., andSchmidt, J. W.,Convex Spline Interpolants with Minimal Curvature, Computing, Vol. 35, pp. 219–229, 1985. · Zbl 0564.65005
[29] Schmidt, J. W., andHess, W.,Schwach verkoppelte Ungleichungssysteme und konvexe Spline-Interpolation, Elemente der Mathematik, Vol. 39, pp. 85–95, 1984. · Zbl 0518.65040
[30] Murty, K. G.,Linear Complementarity, Linear and Nonlinear Programming, Heldermann Verlag, Berlin, Germany, 1988.
[31] Grippo, L., Lampariello, F., andLucidi, S.,A Nonmonotone Line Search Technique for Newton’s Method, SIAM Journal on Numerical Analysis, Vol. 23, pp. 707–716, 1986. · Zbl 0616.65067
[32] Harker, P. T., andXiao, B.,Newton’s Method for the Nonlinear Complementarity Problem: A B-Differentiable Equation Approach, Mathematical Programming, Vol. 48, pp. 339–357, 1990. · Zbl 0724.90071
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.