New improved error bounds for the linear complementarity problem. (English) Zbl 0829.90124

For the linear complementarity problem \[ \text{LCP}(M, q): Mx+ q\geq 0,\;x\geq 0,\;x(Mx+ q)= 0, \] with \(M\) an \(R_0\)-matrix, i.e. the \(\text{LCP}(M, 0)\) has zero as its unique solution, new error bounds are given. Various residuals used in these error bounds are discussed. In some sense the “best” residual is proposed.
Reviewer: E.Iwanow (Wien)


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


error bounds
Full Text: DOI


[1] R.W. Cottle, J.-S. Pang and R.E. Stone,The Linear Complementarity Problem (Academic Press, New York, 1992). · Zbl 0757.90078
[2] Z.-Q. Luo, O.L. Mangasarian, J. Ren and M.V. Solodov, ”New error bounds for the linear complementarity problem,”Mathematics of Operations Research, 19(3) (1994). · Zbl 0833.90113
[3] Z.-Q. Luo and P. Tseng, ”Error bound and the convergence analysis of matrix splitting algorithms for the affine variational inequality problem,”SIAM Journal in Optimization 2 (1992) 43–54. · Zbl 0777.49010
[4] O.L. Mangasarian and T.-H. Shiau, ”Error bounds for monotone linear complementarity problems,”Mathematical Programming 36 (1986) 81–89. · Zbl 0613.90095
[5] O.L. Mangasarian, ”Error bounds for nondegenerate monotone linear complementarity problems,”Mathematical Programming 48 (1990) 437–445. · Zbl 0716.90094
[6] O.L. Mangasarian, ”Global error bounds for monotone affine variational inequality problems,”Linear Algebra and Its Applications 174 (1992) 153–163. · Zbl 0794.90072
[7] R. Mathias and J.-S. Pang, ”Error bounds for the linear complementarity problem with aP-matrix,”Linear Algebra and Applications 132 (1990) 123–136. · Zbl 0711.90077
[8] K.G. Murty,Linear Complementarity, Linear and Nonlinear Programming (Heldermann Verlag, Berlin, 1988).
[9] J.-S. Pang, ”Inexact newton methods for the nonlinear complementarity problem,”Mathematical Programming 36 (1986) 54–71. · Zbl 0613.90097
[10] S.M. Robinson, ”Some continuity properties of polyhedral multifunctions,”Mathematical Programming Study 14 (1981) 206–214. · Zbl 0449.90090
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.