Error Bounds for Monotone Linear Complementarity Problems

摘要

The authors give a bound on the distance between an arbitrary point and the solution set of a monotone linear complementarity problem in terms of a condition constant which depends on the problem data only and a residual function of the violations of the complementarity problem conditions by the point considered. When the point satisfies the linear inequalities of the complementarity problem, the residual consists of the complementarity condition x(Mx + q) plus its square root: (x(Mx + q)) to the 1/2 power. This latter term is essential and without which the error bound cannot hold. It is also shown that another natural residual that has been employed to bound errors for strictly monotone linear complementarity problems, fails to bound errors for the monotone case considered here.