Многоуровневый метод решения больших матричных игр
Ключевые слова:
матричные игры, итерационные методы, прямой решатель, базовый итерационный метод, процедура сужения, процедура продолжения, многоуровневый методАннотация
Для численного решения специального класса матричных игр предложен многоуровневый метод. Содержанием работы является адаптация идей метода Федоренко-Бахвалова, хорошо известного как многосеточный метод для решения эллиптических дифференциальных задач, к итерационному решению матричных игр. Работа выполнена при частичной финансовой поддержке РФФИ (кoд проекта 09–01–00625а).
Библиографические ссылки
- Karmarkar N. A new polonomial-time algorithm for linear programming // Combinatorica. 1984. 4, N 4. 373-395.
- 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.
- Nemirovski A.S., Todd M.J. Interior-point methods for optimization // Acta Numerica. 2008. 17. 191-234.
- Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал, 1998.
- Хачиян Л.Г. Сложность задач линейного программирования. М.: Знание, 1987.
- Colombo M. Advances in interior point methods for large-scale linear programming. PhD Thesis in Optimization. School of Mathematics. University of Edinburgh. Edinburgh, 2007.
- Бабенко К.И. Основы численного анализа. М.: Наука, 1986.
- Федоренко Р.П. Релаксационный метод решения разностных эллиптических уравнений // Журн. вычисл. матем. и матем. физ. 1961. 1, № 5. 922-927.
- Федоренко Р.П. О скорости сходимости одного итерационного процесса // Журн. вычисл. матем. и матем. физ. 1964. 4, № 3. 227-235.
- Бахвалов Н.С. О сходимости одного релаксационного метода для эллиптического оператора с естественными ограничениями // Журн. вычисл. матем. и матем. физ. 1966. 6, № 5. 101-135.
- Ольшанский М.А. Лекции и упражнения по многосеточным методам. М.: Физматлит, 2005.
- Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. М.: Наука, 1970.
- 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.
- Robinson J. An iterative method of solving a game // Ann. Math. 1951. 54. 296-301.
- Shapiro H.N. Note on a computation method in the theory of games // Commun. Pure Appl. Math. 1958. 11. 587-593.
- Szacute ep J., Forgacute o F. Introduction to the theory of games. Dordrecht: Reidel, 1985.
- Беленький В.З., Волконский В.А., Иванков С.А., Поманский А.Б., Шапиро А.Д. Итеративные методы в теории игр и программировании. М.: Наука, 1974.
- 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.
- Washburn A. A new kind of fictitious play // Naval Research Logistics. 2001. 48. 269-280.
- Садовский А.Л. Монотонный итеративный алгоритм решения матричных игр // Доклады АН СССР. 1978. 238, № 3. 538-540.
- 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.
- Матричные игры / Под ред. Н.Н. Воробьева. М.: ГИФМЛ, 1961.
- Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.
- Бахвалов Н.С. Численные методы. М.: Наука, 1973.
- Vaserstein L.N. Matrix games, linear programming, and linear approximation // arXiv.org, math.cs/0609056v1[cs.GT], 27 Jan 2006.
Загрузки
Опубликован
17-09-2009
Как цитировать
Чижонков Е. Многоуровневый метод решения больших матричных игр // Вычислительные методы и программирование. 2009. 10. 327-339
Выпуск
Раздел
Раздел 1. Вычислительные методы и приложения
