An algorithm for the fast solution of symmetric linear complementarity problems

José Luis Morales, Jorge Nocedal*, Mikhail Smelyanskiy

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

30 Scopus citations

Abstract

This paper studies algorithms for the solution of mixed symmetric linear complementarity 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 American options pricing. The paper proposes an improvement of a method described by Kocvara and Zowe (Numer Math 68:95-106, 1994) that combines projected Gauss-Seidel iterations with subspace minimization steps. The proposed algorithm employs a recursive subspace minimization 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.

Original languageEnglish (US)
Pages (from-to)251-266
Number of pages16
JournalNumerische Mathematik
Volume111
Issue number2
DOIs
StatePublished - Dec 1 2008

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'An algorithm for the fast solution of symmetric linear complementarity problems'. Together they form a unique fingerprint.

Cite this