Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-28T04:19:32.833Z Has data issue: false hasContentIssue false
  • English
  • Français

Limited memory solution of bound constrained convex quadratic problems arising in video games

Published online by Cambridge University Press:  15 June 2007

Michael C. Ferris ,
Andrew J. Wathen  and
Paul Armand
Michael C. Ferris
Affiliation:
Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford, OX1 3QD, UK. Computer Sciences Department, University of Wisconsin, 1210 West Dayton Street, Madison, Wisconsin 53706, USA.
Andrew J. Wathen
Affiliation:
Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford, OX1 3QD, UK.
Paul Armand
Affiliation:
Laboratoire XLIM, Université de Limoges, Faculté des Sciences et Techniques, 123, avenue Albert Thomas, 87060 Limoges, France; [email protected]
Get access

Abstract

We describe the solution of a bound constrained convex quadratic problem with limited memory resources. The problem arises from physical simulations occurring within video games. The motivating problem is outlined, along with a simple interior point approach for its solution. Various linear algebra issues arising in the implementation are explored, including preconditioning, ordering and a number of ways of solving an equivalent augmented system. Alternative approaches are briefly surveyed, and some recommendations for solving these types of problems are given.

Keywords

Interior point methodnonlinear complementarity problembound constrained problemlimited memory method.
Type
Research Article
Information
RAIRO - Operations Research , Volume 41 , Issue 1 , January 2007 , pp. 19 - 34
Copyright
© EDP Sciences, ROADEF, SMAI, 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

P. Armand and P. Ségalat, A limited memory algorithm for inequality constrained minimization. Technical Report 2003-08, University of Limoges (France) 2003.
Barzilai, J. and Borwein, J.M., Two-point step size gradient methods. IMA J. Numer. Anal. 8 (1988) 141–148. CrossRef
Bergamaschi, L., Gondzio, J. and Zilli, G., Preconditioning indefinite systems in interior point methods for optimization. Comput. Optim. Appl. 28 (2004) 149–171. CrossRef
Birgin, E.G., Martínez, J.M. and Raydan, M., Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optim. 10 (2000) 1196–1211. CrossRef
Birgin, E.G., Martinez, J.M. and Raydan, M., Algorithm 813: Spg – software for convex-constrained optimization. ACM Trans. Math. Software 27 (2001) 340–349. CrossRef
Byrd, R.H., Hribar, M.E. and Nocedal, J., An interior point algorithm for large-scale nonlinear programming. SIAM J. Optim. 9 (1999) 877–900 (electronic). CrossRef
Byrd, R.H., Nocedal, J. and Schnabel, R.B., Representations of quasi-Newton matrices and their use in limited memory methods. Math. Program. 63 (1994) 129–156. CrossRef
Dirkse, S.P. and Ferris, M.C., The PATH solver: A non-monotone stabilization scheme for mixed complementarity problems. Optim. Meth. Software 5 (1995) 123–156. CrossRef
S.P. Dirkse and M.C. Ferris, Crash techniques for large-scale complementarity problems, in Complementarity and Variational Problems: State of the Art, edited by M.C. Ferris and J.S. Pang. Philadelphia, Pennsylvania. SIAM Publications (1997) 40–61.
Dolan, E.D. and Moré, J.J., Benchmarking optimization software with performance profiles. Math. Program. 91 (2002) 201–213. CrossRef
Ferris, M.C. and Munson, T.S., Complementarity problems in GAMS and the PATH solver. J. Econ. Dyn. Control 24 (2000) 165–188. CrossRef
Gertz, E.M. and Wright, S.J., Object-oriented software for quadratic programming. ACM Trans. Math. Software 29 (2003) 58–81. CrossRef
John, R. Gilbert, Cleve Moler and Robert Schreiber, Sparse matrices in MATLAB: design and implementation. SIAM J. Matrix Anal. Appl. 13 (1992) 333–356.
Gould, N.I.M., Orban, D. and Toint, P.L., GALAHAD, a library of thread-safe Fortran 90 packages for large-scale nonlinear optimization. ACM Trans. Math. Software 29 (2003) 353–372. CrossRef
Keller, C., Gould, N.I.M. and Wathen, A.J., Constraint preconditioning for indefinite linear systems. SIAM J. Matrix Anal. Appl. 21 (2000) 1300–1317. CrossRef
Lin, C.J. and Moré, J., Incomplete Cholesky factorizations with limited memory. SIAM J. Sci. Comput. 21 (1999) 24–45. CrossRef
Lin, C.J. and Moré, J., Newton's method for large bound-constrained optimization problems. SIAM J. Optim. 9 (1999) 1100–1127. CrossRef
Morales, J.L. and Nocedal, J., Automatic preconditioning by limited memory quasi-Newton updating. SIAM J. Optim. 10 (2000) 1079–1096. CrossRef
Munson, T.S., Facchinei, F., Ferris, M.C., Fischer, A. and Kanzow, C., The semismooth algorithm for large scale complementarity problems. INFORMS J. Comput. 13 (2001) 294–311. CrossRef
Murphy, M.F., Golub, G.H. and Wathen, A.J., A note on preconditioning for indefinite linear systems. SIAM J. Sci. Comput. 21 (2000) 1969–1972. CrossRef
Paige, C.C. and Saunders, M.A., LSQR: An algorithm for sparse linear equations and sparse least squares. ACM Trans. Math. Software 8 (1982) 43–71. CrossRef
Y. Saad, Iterative Methods for Sparse Linear Systems. PWS Publishing Company, Boston, Massachusetts (1996).
S.J. Wright, Primal–Dual Interior–Point Methods. SIAM, Philadelphia, Pennsylvania (1997).
Zhu, C.Y., Byrd, R., Lu, P. and Nocedal, J., FORTRAN, L-BFGS-B routines for large scale bound constrained optimization. ACM Trans. Math. Software 23 (1997) 550–560. CrossRef