ERROR-BOUNDS FOR NONDEGENERATE MONOTONE LINEAR COMPLEMENTARITY-PROBLEMS

Error bounds and upper Lipschitz continuity results are given for monotone linear complementarity problems with a nondegenerate solution. The existence of a nondegenerate solution considerably simplifies the error bounds compared with problems for which all solutions are degenerate. Thus when a point satisfies the linear inequalities of a nondegenerate complementarity problem, the residual that bounds the distance from a solution point consists of the complementarity condition alone, whereas for degenerate problems this residual cannot bound the distance to a solution without adding the square root of the complementarity condition to it. This and other simplified results are a consequence of the polyhedral characterization of the solution set as the intersection of the feasible region {z{divides}Mz + q ≥ 0, z ≥ 0} with a single linear affine inequality constraint. © 1990 The Mathematical Programming Society, Inc.