Name
Abstract | ||
|---|---|---|
Given a linear iteration of the form x := F(x), we consider modified versions of the form x := F(x + @cd), where d is a fixed direction, and @c is chosen to minimize the norm of the residual @?x + @cd - F(x + @cd)@?. We propose ways to choose d so that the convergence rate of the modified iteration is governed by the subdominant eigenvalue of the original. In the special case where F relates to a Markovian decision problem, we obtain a new extrapolation method for value iteration. In particular, our method accelerates the Gauss-Seidel version of the value iteration method for discounted problems in the same way that MacQueen's error bounds accelerate the standard version. Furthermore, our method applies equally well to Markov Renewal and undiscounted problems. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1016/0167-6377(95)00007-7 | Operations Research Letters |
Keywords | Field | DocType |
stochastic shortest path,value iteration method,linear iteration,standard version,generic rank-one correction,modified iteration,dynamic programming,value iteration,new extrapolation method,markov renewal,markovian decision problem,jacobi method,convergence rate,gauss-seidel method,gauss-seidel version,decision problem,gauss seidel method,gauss seidel | Mathematical optimization,Combinatorics,Jacobi method,Markov chain,Markov decision process,Extrapolation,Rate of convergence,Mathematics,Gauss–Seidel method,Power iteration,Eigenvalues and eigenvectors | Journal |
Volume | Issue | ISSN |
17 | 3 | Operations Research Letters |
Citations | PageRank | References |
2 | 0.52 | 1 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dimitri P. Bertsekas | 1 | 3052 | 499.08 |
| decision systems | 2 | 159 | 34.45 |