Abstract
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.
Similar content being viewed by others
References
Alefeld, G.E., Chen, X., Potra, F.A.: Numerical validation of solutions of linear complementarity problems. Numer. Math. 83, 1–23 (1999)
Berman, A., Plemmons, R.J.: Nonnegative matrix in the mathematical sciences. SIAM Publisher, Philadelphia, 1994
Chen, B.: Error bounds for R 0-type and monotone nonlinear complementarity problems. J. Optim. Theory Appl. 108, 297–316 (2001)
Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem, Academic Press, Boston, MA, 1992
Ferris, M.C., Mangasarian, O.L.: Error bounds and strong upper semicontinuity for monotone affine variational inequalities, Ann. Oper. Res. 47, 293–305 (1993)
Mathias, R., Pang, J.-S.: Error bounds for the linear complementarity problem with a P-matrix. Linear Algebra Appl. 132, 123–136 (1990)
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
Mangasarian, O.L., Ren, J.: New improved error bounds for the linear complementarity problem. Math. Programming 66, 241–257 (1994)
Pang, J.-S.: Error bounds in mathematical programming. Math. Programming 79, 299–332 (1997)
Rohn, J.: Systems of linear interval equations. Linear Algebra Appl. 126, 39–78 (1989)
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)
Schäfer, U.: A linear complementarity problem with a P-matrix, SIAM Review 46, 189–201 (2004)
Xiu, N., Zhang, J.: A characteristic quantity of P-matrices. Appl. Math. Lett. 15, 41–46 (2002)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work is partly supported by a Grant-in-Aid from Japan Society for the Promotion of Science.
Rights and permissions
About this article
Cite this article
Chen, X., Xiang, S. Computation of Error Bounds for P-matrix Linear Complementarity Problems. Math. Program. 106, 513–525 (2006). https://doi.org/10.1007/s10107-005-0645-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-005-0645-9