A multi-level method for solving large-scale matrix games

Authors

  • E.V. Chizhonkov

Keywords:

matrix games
iterative methods
direct solver
basic iterative method
procedure of restriction
procedure of prolongation
multi-level method

Abstract

A multi-level method is proposed to solve the matrix games of a special class. The essence of the paper is the adaptation of ideas of the Fedorenko-Bakhvalov method, well known as a multi-grid method for solving elliptic differential problems, to the iterative solution of matrix games. The work was supported by the Russian Foundation for Basic Research (project no. 09–01–00625a).

New computational technologies

Downloads

Published

2009-09-17

Issue

Vol. 10 (2009): Issue 3.

Section

Section 1. Numerical methods and applications

Author Biography

E.V. Chizhonkov

Lomonosov Moscow State University,
Faculty of Mechanics and Mathematics
• Professor

References

  1. Karmarkar N. A new polonomial-time algorithm for linear programming // Combinatorica. 1984. 4, N 4. 373-395.
  2. Wright M.H. The interior-point revolution in optimization: history, recent developments, and lasting consequences // Bull. Amer. Math. Soc. 2004. 42, N 1. 39-56.
  3. Nemirovski A.S., Todd M.J. Interior-point methods for optimization // Acta Numerica. 2008. 17. 191-234.
  4. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал, 1998.
  5. Хачиян Л.Г. Сложность задач линейного программирования. М.: Знание, 1987.
  6. Colombo M. Advances in interior point methods for large-scale linear programming. PhD Thesis in Optimization. School of Mathematics. University of Edinburgh. Edinburgh, 2007.
  7. Бабенко К.И. Основы численного анализа. М.: Наука, 1986.
  8. Федоренко Р.П. Релаксационный метод решения разностных эллиптических уравнений // Журн. вычисл. матем. и матем. физ. 1961. 1, № 5. 922-927.
  9. Федоренко Р.П. О скорости сходимости одного итерационного процесса // Журн. вычисл. матем. и матем. физ. 1964. 4, № 3. 227-235.
  10. Бахвалов Н.С. О сходимости одного релаксационного метода для эллиптического оператора с естественными ограничениями // Журн. вычисл. матем. и матем. физ. 1966. 6, № 5. 101-135.
  11. Ольшанский М.А. Лекции и упражнения по многосеточным методам. М.: Физматлит, 2005.
  12. Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. М.: Наука, 1970.
  13. Brown G.W. Iterative solution of games by fictitious play // Activity analysis of production and allocation. / Edited by T.C. Koopmans. New York: Wiley, 1951. 374-376.
  14. Robinson J. An iterative method of solving a game // Ann. Math. 1951. 54. 296-301.
  15. Shapiro H.N. Note on a computation method in the theory of games // Commun. Pure Appl. Math. 1958. 11. 587-593.
  16. Szacute ep J., Forgacute o F. Introduction to the theory of games. Dordrecht: Reidel, 1985.
  17. Беленький В.З., Волконский В.А., Иванков С.А., Поманский А.Б., Шапиро А.Д. Итеративные методы в теории игр и программировании. М.: Наука, 1974.
  18. Gaas S.I, Zafra P.M., Qui Z. Modified fictitious play for solving matrix games and linear programming problems // Comp. Oper. Res. 1995. 22. 893-903.
  19. Washburn A. A new kind of fictitious play // Naval Research Logistics. 2001. 48. 269-280.
  20. Садовский А.Л. Монотонный итеративный алгоритм решения матричных игр // Доклады АН СССР. 1978. 238, № 3. 538-540.
  21. Gale D., Kuhn H.W., Tucker A.W. On symmetric games // Contributions to the theory of games / Edited by H.W. Kuhn and A.W. Tucker. Annals of Mathematics Study N 24. Princeton: Princeton University Press. 1950. 1. 81-87.
  22. Матричные игры / Под ред. Н.Н. Воробьева. М.: ГИФМЛ, 1961.
  23. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.
  24. Бахвалов Н.С. Численные методы. М.: Наука, 1973.
  25. Vaserstein L.N. Matrix games, linear programming, and linear approximation // arXiv.org, math.cs/0609056v1[cs.GT], 27 Jan 2006.