Limited memory solution of bound constrained convex quadratic problems arising in video games
RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 1, pp. 19-34.

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.

DOI : 10.1051/ro:2007009
Classification : 90C20, 90C51
Mots clés : interior point method, nonlinear complementarity problem, bound constrained problem, limited memory method
Ferris, Michael C.  ; Wathen, Andrew J.  ; Armand, Paul 1

1 Laboratoire XLIM, Université de Limoges, Faculté des Sciences et Techniques, 123, avenue Albert Thomas, 87060 Limoges, France
@article{RO_2007__41_1_19_0,
     author = {Ferris, Michael C. and Wathen, Andrew J. and Armand, Paul},
     title = {Limited memory solution of bound constrained convex quadratic problems arising in video games},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {19--34},
     publisher = {EDP-Sciences},
     volume = {41},
     number = {1},
     year = {2007},
     doi = {10.1051/ro:2007009},
     mrnumber = {2310537},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro:2007009/}
}
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 - Recherche Opérationnelle
PY  - 2007
SP  - 19
EP  - 34
VL  - 41
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro:2007009/
DO  - 10.1051/ro:2007009
LA  - en
ID  - RO_2007__41_1_19_0
ER  - 
%0 Journal Article
%A Ferris, Michael C.
%A Wathen, Andrew J.
%A Armand, Paul
%T Limited memory solution of bound constrained convex quadratic problems arising in video games
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2007
%P 19-34
%V 41
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro:2007009/
%R 10.1051/ro:2007009
%G en
%F RO_2007__41_1_19_0
Ferris, Michael C.; Wathen, Andrew J.; Armand, Paul. Limited memory solution of bound constrained convex quadratic problems arising in video games. RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 1, pp. 19-34. doi : 10.1051/ro:2007009. http://archive.numdam.org/articles/10.1051/ro:2007009/

[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. | Zbl

[3] L. Bergamaschi, J. Gondzio and G. Zilli, Preconditioning indefinite systems in interior point methods for optimization. Comput. Optim. Appl. 28 (2004) 149-171. | Zbl

[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. | Zbl

[5] E.G. Birgin, J.M. Martinez and M. Raydan, Algorithm 813: Spg - software for convex-constrained optimization. ACM Trans. Math. Software 27 (2001) 340-349. | Zbl

[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). | Zbl

[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. | Zbl

[8] S.P. Dirkse and M.C. Ferris, The PATH solver: A non-monotone stabilization scheme for mixed complementarity problems. Optim. Meth. Software 5 (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. | Zbl

[10] E.D. Dolan and J.J. Moré, Benchmarking optimization software with performance profiles. Math. Program. 91 (2002) 201-213. | Zbl

[11] M.C. Ferris and T.S. Munson, Complementarity problems in GAMS and the PATH solver. J. Econ. Dyn. Control 24 (2000) 165-188. | Zbl

[12] E.M. Gertz and S.J. Wright, Object-oriented software for quadratic programming. ACM Trans. Math. Software 29 (2003) 58-81. | Zbl

[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. | Zbl

[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. Software 29 (2003) 353-372. | Zbl

[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. | Zbl

[16] C.J. Lin and J. Moré, Incomplete Cholesky factorizations with limited memory. SIAM J. Sci. Comput. 21 (1999) 24-45. | Zbl

[17] C.J. Lin and J. Moré, Newton's method for large bound-constrained optimization problems. SIAM J. Optim. 9 (1999) 1100-1127. | Zbl

[18] J.L. Morales and J. Nocedal, Automatic preconditioning by limited memory quasi-Newton updating. SIAM J. Optim. 10 (2000) 1079-1096. | Zbl

[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. | Zbl

[21] C.C. Paige and M.A. Saunders, LSQR: An algorithm for sparse linear equations and sparse least squares. ACM Trans. Math. Software 8 (1982) 43-71. | Zbl

[22] Y. Saad, Iterative Methods for Sparse Linear Systems. PWS Publishing Company, Boston, Massachusetts (1996). | Zbl

[23] S.J. Wright, Primal-Dual Interior-Point Methods. SIAM, Philadelphia, Pennsylvania (1997). | Zbl

[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. Software 23 (1997) 550-560. | Zbl

Cité par Sources :