An algorithm for the fast solution of symmetric linear complementarity problems |
| |
Authors: | José Luis Morales Jorge Nocedal Mikhail Smelyanskiy |
| |
Institution: | (1) Departamento de Matemáticas, Instituto Tecnológico Autónomo de México, Mexico City, Mexico;(2) Department of Electrical Engineering and Computer Science, Northwestern University, Chicago, USA;(3) The Intel Corporation, Santa Clara, CA, USA |
| |
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.
The research of J. L. Morales was supported by Asociación Mexicana de Cultura AC and CONACyT-NSF grant J110.388/2006.
The research of J. Nocedal was supported by National Science Foundation grant CCF-0514772, Department of Energy grant DE-FG02-87ER25047-A004
and a grant from the Intel Corporation. |
| |
Keywords: | Mathematics Subject Classification (2000)" target="_blank">Mathematics Subject Classification (2000) 65K05 90C30 |
本文献已被 SpringerLink 等数据库收录! |
|