On the Convergence of a Matrix Splitting Algorithm for the Symmetric Monotone Linear Complementarity Problem

A matrix splitting algorithm for the linear complementarily problem is considered, where the matrix is symmetric positive semidefinite. It is shown that if the splitting is regular, then the iterates generated by the algorithm are well defined and converge to a solution. This result resolves in the affirmative a long standing question about the convergence of the point successive overrelaxation (SOR) method for solving this problem. This result is also extended to related iterative methods. As direct consequences, convergence of the methods of, respectively, Aganagic, Cottle et al., Mangasarian, Pang, and others, is obtained, without making any additional assumptions on the problem.