"An Algorithm for the Fast Solution of Linear Complementarity Problems"
J.L. Morales, J. Nocedal, M. Smelyanskiy.
Numerische Mathematik, DOI: 10.1007/s00211-008-0183-5 (2007)

This paper studies algorithms for the solution of mixed symmetric linear comple- mentarity problems. The goal is to compute fast and approximate solutions of medium to large sized problems, such as those arising in computer game simulations and Amer- ican options pricing. The paper proposes an improvement of a method described by Kocvara and Zowe [19] that combines projected Gauss-Seidel iterations with subspace minimization steps. The proposed algorithm employs a recursive subspace minimiza- tion designed to handle severely ill-conditioned problems. Numerical tests indicate that the approach is more efficient than interior-point and gradient projection methods on some physical simulation problems that arise in computer game scenarios.
Download (pdf)