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