# 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

## Access Full Article

top## Abstract

top## How to cite

topFerris, 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- P. Armand and P. Ségalat, A limited memory algorithm for inequality constrained minimization. Technical Report 2003-08, University of Limoges (France) 2003.
- J. Barzilai and J.M. Borwein, Two-point step size gradient methods. IMA J. Numer. Anal.8 (1988) 141–148. Zbl0638.65055
- 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
- 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
- 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
- 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
- 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
- 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.
- 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
- E.D. Dolan and J.J. Moré, Benchmarking optimization software with performance profiles. Math. Program.91 (2002) 201–213. Zbl1049.90004
- M.C. Ferris and T.S. Munson, Complementarity problems in GAMS and the PATH solver. J. Econ. Dyn. Control24 (2000) 165–188. Zbl1002.90070
- E.M. Gertz and S.J. Wright, Object-oriented software for quadratic programming. ACM Trans. Math. Software29 (2003) 58–81. Zbl1068.90586
- 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
- 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
- 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
- C.J. Lin and J. Moré, Incomplete Cholesky factorizations with limited memory. SIAM J. Sci. Comput.21 (1999) 24–45. Zbl0941.65033
- C.J. Lin and J. Moré, Newton's method for large bound-constrained optimization problems. SIAM J. Optim.9 (1999) 1100–1127. Zbl0957.65064
- J.L. Morales and J. Nocedal, Automatic preconditioning by limited memory quasi-Newton updating. SIAM J. Optim.10 (2000) 1079–1096. Zbl1020.65019
- 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
- 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
- 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
- Y. Saad, Iterative Methods for Sparse Linear Systems. PWS Publishing Company, Boston, Massachusetts (1996). Zbl1031.65047
- S.J. Wright, Primal–Dual Interior–Point Methods. SIAM, Philadelphia, Pennsylvania (1997). Zbl0863.65031
- 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 ?

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