A projection algorithm for strictly monotone linear complementarity problems

Complementary problems play a central role in equilibrium finding, physical sim- ulation, and optimization. As a consequence, we are interested in understanding how to solve these problems quickly, and this often involves approximation. In this paper we present a method for approximately solving strictly monotone linear complementarity problems with a Galerkin approximation. We also give bounds for the approximate error, and prove novel bounds on perturbation error. These perturbation bounds suggest that a Galerkin approximation may be much less sen- sitive to noise than the original LCP.