Computation of error bounds for P-matrix linear complementarity problems. (English) Zbl 1134.90043

Summary: We give new error bounds for the linear complementarity problem where the involved matrix is a P-matrix. Computation of rigorous error bounds can be turned into a P-matrix linear interval system. Moreover, for the involved matrix being an H-matrix with positive diagonals, an error bound can be found by solving a linear system of equations, which is sharper than the Mathias-Pang error bound. Preliminary numerical results show that the proposed error bound is efficient for verifying accuracy of approximate solutions.


90C31 Sensitivity, stability, parametric optimization
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
Full Text: DOI


[1] Alefeld, G.E., Chen, X., Potra, F.A.: Numerical validation of solutions of linear complementarity problems. Numer. Math. 83, 1–23 (1999) · Zbl 0933.65072
[2] Berman, A., Plemmons, R.J.: Nonnegative matrix in the mathematical sciences. SIAM Publisher, Philadelphia, 1994 · Zbl 0815.15016
[3] Chen, B.: Error bounds for R 0-type and monotone nonlinear complementarity problems. J. Optim. Theory Appl. 108, 297–316 (2001) · Zbl 1041.90055
[4] Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem, Academic Press, Boston, MA, 1992
[5] Ferris, M.C., Mangasarian, O.L.: Error bounds and strong upper semicontinuity for monotone affine variational inequalities, Ann. Oper. Res. 47, 293–305 (1993) · Zbl 0794.49008
[6] Mathias, R., Pang, J.-S.: Error bounds for the linear complementarity problem with a P-matrix. Linear Algebra Appl. 132, 123–136 (1990) · Zbl 0711.90077
[7] Gabriel, S.A., Moré, J.J.: Smoothing of mixed complementarity problems. In: M.C.Ferris and J.-S. Pang (ed.) Complementarity and Variational Problems: State of the Art. SIAM Publications, Philadelphia, PA, pp 105–116 1997 · Zbl 0886.90154
[8] Mangasarian, O.L., Ren, J.: New improved error bounds for the linear complementarity problem. Math. Programming 66, 241–257 (1994) · Zbl 0829.90124
[9] Pang, J.-S.: Error bounds in mathematical programming. Math. Programming 79, 299–332 (1997) · Zbl 0887.90165
[10] Rohn, J.: Systems of linear interval equations. Linear Algebra Appl. 126, 39–78 (1989) · Zbl 0712.65029
[11] Schäfer, U.: An enclosure method for free boundary problems based on a linear complementarity problem with interval data. Numer. Func. Anal. Optim. 22, 991–1011 (2001) · Zbl 1022.90033
[12] Schäfer, U.: A linear complementarity problem with a P-matrix, SIAM Review 46, 189–201 (2004) · Zbl 1133.90402
[13] Xiu, N., Zhang, J.: A characteristic quantity of P-matrices. Appl. Math. Lett. 15, 41–46 (2002) · Zbl 1175.90421
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.