Convergence of splitting and Newton methods for complementarity problems: An application of some sensitivity results

This paper is concerned with two well-known families of iterative methods for solving the linear and nonlinear complementarity problems. For the linear complementarity problem, it considers the class of matrix splitting methods and establishes, under a finiteness assumption on the number of solutions, a necessary and sufficient condition for the convergence of the sequence of iterates produced. A rate of convergence result for this class of methods is also derived under a stability assumption on the limit solution. For the nonlinear complementarity problem, the paper establishes the convergence of the Newton method under the assumption of a ‘pseudo-regular’ solution which generalizes Robinson’s concept of a ‘strongly regular’ solution. In both instances, the convergence proofs rely on a common sensitivity result of the linear complementarity problem under perturbation.