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

Chen, Xiaojun; Xiang, Shuhuang

Math. Program. 106, No. 3 (A), 513-525 (2006).

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.

MSC:

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

Keywords:

accuracy; error bounds; linear complementarity problems

References:

[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