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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ageia physx. Web page. http://www.ageia.com/physx/ (2006)
Anitescu M., Potra F.A.: Formulating dynamic multi-rigid-body contact problems with friction as solvable linear complementarity problems. Nonlinear Dyn. 14, 231–247 (1997)
Bertsekas D.P.: Projected Newton methods for optimization problems with simple constraints. SIAM J. Control Optim. 20(2), 221–246 (1982)
Birgin E.G., Martínez J.M.: Large-scale active-set box-constrained optimization method with spectral projected gradients. Comput. Optim. Appl. 23, 101–125 (2002)
Birgin E.G., Martínez J.M., Raydan M.: Nonmonotone spectral projected gradient methods on convex sets. SIOPT 10, 1196–1211 (2000)
Birgin E.G., Martínez J.M., Raydan M.: Algorithm 813: Spg-software for convex-constrained optimization. ACM Trans. Math. Softw. 27, 340–349 (2001)
Burke J.V., Moré J.J.: On the identification of active constraints. SIAM J. Numer. Anal. 25(5), 1197–1211 (1998)
Catto, E.: Iterative dynamics with temporal coherence. Technical report, Crystal Dynamics, Menlo Park (2005)
Conn, A.R., Gould, N.I.M., Toint, Ph.L.: Global convergence of a class of trust region algorithms for optimization with simple bounds. SIAM J. Numer. Anal. 25(182):433–460 (1988) [See also SIAM J. Numer. Anal. 26:764–767 (1989)]
Conn A.R., Gould N.I.M., Toint Ph.L.: LANCELOT: a Fortran package for Large-scale Nonlinear Optimization (Release A). Springer Series in Computational Mathematics. Springer, Heidelberg (1992)
Cottle R.W., Dantzig G.B.: Complementarity pivot theory of mathematical programming. J. Linear Algebra Applns 1, 103–125 (1968)
Cottle R.W., Pang J.-S., Stone R.E.: The Linear Complementarity Problem. Academic Press, London (1992)
Dai, Y.H., Fletcher, R.: Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming. Numer. Math. 100 (2005)
Dolan, E.D., Moré, J.J., Munson, T.S.: Benchmarking optimization software with COPS 3.0. Technical Report ANL/MCS-TM-273, Argonne National Laboratory, Argonne (2004)
Ferris M.C., Pang J.S.: Engineering and economic applications of complementarity problems. SIAM Rev. 39(4), 669–713 (1997)
Ferris M.C., Wathen A.J., Armand P.: Limited memory solution of bound constrained convex quadratic problems arising in video games. RAIRO Oper. Res. 41, 19–34 (2007)
Hager W.W., Zhang H.: A new active set algorithm for box constrained optimization. SIOPT 17(2), 526–557 (2007)
Havok, F.X.: Web page. http://www.havok.com/content/view/187/77/ (2006)
Kocvara M., Zowe J.: An iterative two-step algorithm for linear complementarity problems. Numer. Math. 68, 95–106 (1994)
Kumar, S., Hughes, C.J., Nguyen, A. Carbon: architectural support for fine-grained parallelism on chip multiprocessors. In: Proceedings of IEEE/ACM International Symposium on Computer Architecture (ISCA), San Diego (2007)
Lin C.J., Moré J.J.: Newton’s method for large bound-constrained optimization problems. SIAM J. Optim. 9(4), 1100–1127 (1999)
Morales J.L, Sargent R.W.H.: Computational experience with several methods for large-scale convex quadratic programming. Aportaciones Matemáticas. Comunicaciones 14, 141–158 (1994)
Moré J.J., Toraldo G.: On the solution of large quadratic programming problems with bound constraints. SIAM J. Optim. 1(1), 93–113 (1991)
O’Leary D.P.: A generalized conjugate gradient algorithm for solving a class of quadratic programming problems. Linear Algebra Appl. 34, 371–399 (1980)
Schenk, O.: Scalable parallel sparse LU factorization methods on shared memory multiprocessors. PhD thesis, Swiss Federal Institute of Technology, Zurich (2000)
Schenk O., Gärtner K.: Solving unsymmetric sparse systems of linear equations with pardiso. J. Future Generation Comput. Syst. 20(3), 475–487 (2004)
Schenk O., Gärtner K.: On fast factorization pivoting methods for symmetric indefinite systems. Elec. Trans. Numer. Anal. 23, 158–179 (2006)
Smelyanskiy, M., Lee, V. W., Kim, D., Nguyen, A.D., Dubey, P.: Scaling performance of interior-point methods on a large-scale chip multiprocessor system. In: SC ’07: Proceedings of the 2007 ACM/IEEE conference on Supercomputing (2007)
Smith, R.: Open dynamics engine. Technical report. http://www.ode.org (2004)
Wilmott P.: Quantitative Finance. Wiley, London (2006)
Wright S.J.: Primal-Dual Interior-Point Methods. SIAM, Philadelphia (1997)
Zhu C., Byrd R.H., Lu P., Nocedal J.: Algorithm 78: L-BFGS-B: Fortran subroutines for large-scale bound constrained optimization. ACM Trans. Math. Softw. 23(4), 550–560 (1997)
Author information
Authors and Affiliations
Corresponding author
Additional information
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.
Rights and permissions
About this article
Cite this article
Morales, J.L., Nocedal, J. & Smelyanskiy, M. An algorithm for the fast solution of symmetric linear complementarity problems. Numer. Math. 111, 251–266 (2008). https://doi.org/10.1007/s00211-008-0183-5
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00211-008-0183-5