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.  Zbl0638.65055
  3. L. Bergamaschi, J. Gondzio and G. Zilli, Preconditioning indefinite systems in interior point methods for optimization. Comput. Optim. Appl.28 (2004) 149–171.  Zbl1056.90137
  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.  Zbl1047.90077
  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.  Zbl1070.65547
  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).  Zbl0957.65057
  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.  Zbl0809.90116
  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.  Zbl0886.90150
  10. E.D. Dolan and J.J. Moré, Benchmarking optimization software with performance profiles. Math. Program.91 (2002) 201–213.  Zbl1049.90004
  11. M.C. Ferris and T.S. Munson, Complementarity problems in GAMS and the PATH solver. J. Econ. Dyn. Control24 (2000) 165–188.  Zbl1002.90070
  12. E.M. Gertz and S.J. Wright, Object-oriented software for quadratic programming. ACM Trans. Math. Software29 (2003) 58–81.  Zbl1068.90586
  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.  Zbl0752.65037
  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.  Zbl1068.90525
  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.  Zbl0960.65052
  16. C.J. Lin and J. Moré, Incomplete Cholesky factorizations with limited memory. SIAM J. Sci. Comput.21 (1999) 24–45.  Zbl0941.65033
  17. C.J. Lin and J. Moré, Newton's method for large bound-constrained optimization problems. SIAM J. Optim.9 (1999) 1100–1127.  Zbl0957.65064
  18. J.L. Morales and J. Nocedal, Automatic preconditioning by limited memory quasi-Newton updating. SIAM J. Optim.10 (2000) 1079–1096.  Zbl1020.65019
  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.  Zbl1238.90123
  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.  Zbl0959.65063
  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.  Zbl0478.65016
  22. Y. Saad, Iterative Methods for Sparse Linear Systems. PWS Publishing Company, Boston, Massachusetts (1996).  Zbl1031.65047
  23. S.J. Wright, Primal–Dual Interior–Point Methods. SIAM, Philadelphia, Pennsylvania (1997).  Zbl0863.65031
  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.  Zbl0912.65057

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.