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

Michael C. Ferris; Andrew J. Wathen; Paul Armand

RAIRO - Operations Research (2007)

  • Volume: 41, Issue: 1, page 19-34
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Ferris, Michael C., Wathen, Andrew J., and Armand, Paul. "Limited memory solution of bound constrained convex quadratic problems arising in video games." RAIRO - Operations Research 41.1 (2007): 19-34. <http://eudml.org/doc/250140>.

@article{Ferris2007,
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. },
author = {Ferris, Michael C., Wathen, Andrew J., Armand, Paul},
journal = {RAIRO - Operations Research},
keywords = {Interior point method; nonlinear complementarity problem; bound constrained problem; limited memory method.},
language = {eng},
month = {6},
number = {1},
pages = {19-34},
publisher = {EDP Sciences},
title = {Limited memory solution of bound constrained convex quadratic problems arising in video games},
url = {http://eudml.org/doc/250140},
volume = {41},
year = {2007},
}

TY - JOUR
AU - Ferris, Michael C.
AU - Wathen, Andrew J.
AU - Armand, Paul
TI - Limited memory solution of bound constrained convex quadratic problems arising in video games
JO - RAIRO - Operations Research
DA - 2007/6//
PB - EDP Sciences
VL - 41
IS - 1
SP - 19
EP - 34
AB - 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.
LA - eng
KW - Interior point method; nonlinear complementarity problem; bound constrained problem; limited memory method.
UR - http://eudml.org/doc/250140
ER -

References

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

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.