Operator Splitting Methods for Monotone Linear Complementarity Problems

摘要

This paper applies splitting techniques developed for set-valued maximal monotoneoperators to the monotone linear complementarity problem. The authors use the theory of three established operator splitting schemes to derive convergence results for six monotone linear complementarity algorithms, one of which is the classical gradient projection method, and another of which is essentially a special case of matrix splitting. The remaining four methods appear to be new, and their convergence proofs do not depend on the symmetry of M. The authors take two of these new algorithms and use them with some encouraging results to solve linear complementarity problems arising from random dense quadratic and extended linear-quadratic programs. The implementations are massively parallel, and run on the Connection Machine CM-2/200 computer family.