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.
Mots-clés : interior point method, nonlinear complementarity problem, bound constrained problem, limited memory method
@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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ro:2007009/
[1] A limited memory algorithm for inequality constrained minimization. Technical Report 2003-08, University of Limoges (France) 2003.
and ,[2] Two-point step size gradient methods. IMA J. Numer. Anal. 8 (1988) 141-148. | Zbl
and ,[3] Preconditioning indefinite systems in interior point methods for optimization. Comput. Optim. Appl. 28 (2004) 149-171. | Zbl
, and ,[4] Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optim. 10 (2000) 1196-1211. | Zbl
, and ,[5] Algorithm 813: Spg - software for convex-constrained optimization. ACM Trans. Math. Software 27 (2001) 340-349. | Zbl
, and ,[6] An interior point algorithm for large-scale nonlinear programming. SIAM J. Optim. 9 (1999) 877-900 (electronic). | Zbl
, and ,[7] Representations of quasi-Newton matrices and their use in limited memory methods. Math. Program. 63 (1994) 129-156. | Zbl
, and ,[8] The PATH solver: A non-monotone stabilization scheme for mixed complementarity problems. Optim. Meth. Software 5 (1995) 123-156.
and ,[9] 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
and ,[10] Benchmarking optimization software with performance profiles. Math. Program. 91 (2002) 201-213. | Zbl
and ,[11] Complementarity problems in GAMS and the PATH solver. J. Econ. Dyn. Control 24 (2000) 165-188. | Zbl
and ,[12] Object-oriented software for quadratic programming. ACM Trans. Math. Software 29 (2003) 58-81. | Zbl
and ,[13] Gilbert, Cleve Moler and Robert Schreiber, Sparse matrices in MATLAB: design and implementation. SIAM J. Matrix Anal. Appl. 13 (1992) 333-356. | Zbl
[14] GALAHAD, a library of thread-safe Fortran 90 packages for large-scale nonlinear optimization. ACM Trans. Math. Software 29 (2003) 353-372. | Zbl
, and ,[15] Constraint preconditioning for indefinite linear systems. SIAM J. Matrix Anal. Appl. 21 (2000) 1300-1317. | Zbl
, and ,[16] Incomplete Cholesky factorizations with limited memory. SIAM J. Sci. Comput. 21 (1999) 24-45. | Zbl
and ,[17] Newton's method for large bound-constrained optimization problems. SIAM J. Optim. 9 (1999) 1100-1127. | Zbl
and ,[18] Automatic preconditioning by limited memory quasi-Newton updating. SIAM J. Optim. 10 (2000) 1079-1096. | Zbl
and ,[19] The semismooth algorithm for large scale complementarity problems. INFORMS J. Comput. 13 (2001) 294-311.
, , , and ,[20] A note on preconditioning for indefinite linear systems. SIAM J. Sci. Comput. 21 (2000) 1969-1972. | Zbl
, and ,[21] LSQR: An algorithm for sparse linear equations and sparse least squares. ACM Trans. Math. Software 8 (1982) 43-71. | Zbl
and ,[22] Iterative Methods for Sparse Linear Systems. PWS Publishing Company, Boston, Massachusetts (1996). | Zbl
,[23] Primal-Dual Interior-Point Methods. SIAM, Philadelphia, Pennsylvania (1997). | Zbl
,[24] L-BFGS-B, FORTRAN routines for large scale bound constrained optimization. ACM Trans. Math. Software 23 (1997) 550-560. | Zbl
, , and ,Cité par Sources :