Abstract
We prove convergence of the whole sequence generated by any of a large class of iterative algorithms for the symmetric linear complementarity problem (LCP), under the only hypothesis that a quadratic form associated with the LCP is bounded below on the nonnegative orthant. This hypothesis holds when the matrix is strictly copositive, and also when the matrix is copositive plus and the LCP is feasible. The proof is based upon the linear convergence rate of the sequence of functional values of the quadratic form. As a by-product, we obtain a decomposition result for copositive plus matrices. Finally, we prove that the distance from the generated sequence to the solution set (and the sequence itself, if its limit is a locally unique solution) have a linear rate of R-convergence.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R.W. Cottle, J.S. Pang and R.S. Stone,The Linear Complementarity Problem (forthcoming).
A. De Pierro and A.N. Iunem, “Convergence properties of iterative methods for symmetric positive semidefinite Linear Complementarity Problems,” to appear in:Mathematics of Operations Research.
B.C. Eaves, “The Linear Complementarity Problem,”Management Science 17 (1971) 68–75.
B.C. Eaves, “On quadratic programming,”Management Science 17 (1971) 698–711.
Z.-Q. Luo and P. Tseng, “On the convergence of a matrix splitting algorithm for the symmetric Linear Complementarity Problem,” to appear in:SIAM Journal on Control and Optimization.
O.L. Mangasarian, “Solution of symmetric Linear Complementarity Problems by iterative methods,”Journal of Optimization Theory and Applications 22 (1977) 465–485.
O.L. Mangasarian, “Locally unique solution of quadratic programs, linear and non-linear complementarity problems,”Mathematical Programming 19 (1980) 200–212.
O.L. Mangasarian, “Convergence of iterates of an inexact matrix splitting algorithm for the symmetric monotone Linear Complementarity Problems,” to appear in:SIAM Journal on Optimization.
K. Murty,Linear Complementarity, Linear and Nonlinear Programming (Helderman, Berlin, 1988).
J.M. Ortega and W.S. Rheinboldt,Iterative Solutions of Nonlinear Equations in Several Variables (Academic Pres, New York, 1970).
J.S. Pang, “Necessary and sufficient conditions for the convergence of iterative methods for the Linear Complementarity Problem,”Journal of Optimization Theory and Applications 44 (1984) 1–17.
J.S. Pang, “More results on the convergence of iterative methods for the Linear Complementarity Problem,”Journal of Optimization Theory and Applications 49 (1986) 107–134.
F. Pereira, “On characterizations of copositive matrices,” Technical Report 72-8, Department of Operations Research, Stanford University (Stanford, CA, 1972).
S.M. Robinson, “Some continuity properties of polyhedral multifunctions,”Mathematical Programming Study 14 (1981) 206–214.
Author information
Authors and Affiliations
Additional information
Research for this work was partially supported by CNPq grant No. 301280/86.
Rights and permissions
About this article
Cite this article
Iusem, A.N. On the convergence of iterative methods for symmetric linear complementarity problems. Mathematical Programming 59, 33–48 (1993). https://doi.org/10.1007/BF01581236
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01581236