file.pdf (210.17 kB)

A projection algorithm for strictly monotone linear complementarity problems

Download (210.17 kB)
journal contribution
posted on 01.12.2013 by Erik Zawadski, Geoffrey J. Gordon, Andre Platzer

Complementary problems play a central role in equilibrium finding, physical simulation, 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 sensitive to noise than the original LCP.