Projected equation methods for approximate solution of large linear systems (Q1012492)

The motivation of this comprehensive and very well organized study comes from recent advances in the field of dynamic programming, where large systems of equations of the form: \(x=Ax+b,\; A\in\mathbb{R}^{n\times n},\; b\in\mathbb{R}^{n}\) appear in the context of evaluation of the cost of a stationary policy in a Markovian decision problems. The authors focus on the case where \(n\) is very large, and a need to consider a low approximation of a solution within a subspace \(S=\{\Phi r|\;\Phi\in\mathbb{R}^{n\times s},\; r\in\mathbb{R}^s\}, s\ll n\) is inevitable. In general, the algorithms are extensions of recent approximate dynamic programming methods, known as temporal difference methods, which solve a projected form of Bellman's equation by using simulation-based approximations to this equation, or by using a projected value iteration method. Two types of methods are considered: (i) equation approximation methods and (ii) approximate Jacobi methods. They are developed separately and later a relation of both is widely discussed. Multi-step analogs of both are developed in the meaning of methods of approximate dynamic programming. Special methods using basis functions of the form \(A^m g, m\geq 0\), where \(g\) is some vector the components of which can be exactly computed are proposed and investigated. Stochastic iterative algorithms, based on simulation, which converge to the approximate solution and are suitable for very large-dimensional problems are proposed. A selection of Markov chains is discussed and some related examples and special cases are presented. Some new algorithms for Markovian decision problems are derived. Some extensions as well as related methods are considered as well. In particular it concerns a general approach for linear least squares problems and applications to some non-linear fixed point problems. The approximate dynamic programming methods proposed for optimal stopping problems are significantly generalized. Some applications concerning special cases and related problems are outlined. Numerical experiments are not given. The list of references is adequate related to the problem itself and giving links to other areas.