Andrzej Mackiewicz

New Tensor Method Strategy for Solving Large Games

901

Abstract

This paper presents a new, effective version of the Tensor Method for solving difficult, badly conditioned (or singular) medium-size systems of $n$ nonlinear equations which arise in Large Games Theory. It can be considered as an improvement of the classical Newton's method. In order to enrich a linear model around the current iteration, $p$ dynamically chosen ideal tensor directions are used (where $p$ changes from iteration to iteration). If it is possible, tensor steps are determined exactly (by the close formulas) in the most frequent cases, when $p=1\,$or $p=2$. Otherwise, they are distinguished approximately by unconstrained minimization algorithms or by the trust region technique. The objective function (Euclidean length of the functions) is allowed to increase at intermediate steps. The method considered is very competitive to the other Newton--like algorithms, when the cost of the problem function evaluation is high or the system of equations considered is too difficult for the classical methods (because of singularity or nondifferentiability).

Key words:
General Terms: Algorithms, Game Theory, Mathematical Software
Additional Key Words and Phrases: Equilibria, large games, roots of nonlinear equations; constrained nonlinear least squares, rank-deficient matrices, tensor methods, SVD decomposition