On the Convergence of Simulation-Based Iterative Methods for Singular Linear Systems

Content Provider	Semantic Scholar
Author	Mdwang, Mengdi Wang Bertsekas, Dimitri P.
Copyright Year	2012
Abstract	We consider the simulation-based solution of linear systems of equations, Ax = b, of various types frequently arising in large-scale applications, where A is singular. We show that the convergence properties of iterative solution methods are frequently lost when they are implemented with simulation (e.g., using sample average approximation), as is often done in important classes of large-scale problems. We focus on special cases of algorithms for singular systems, including some arising in least squares problems and approximate dynamic programming, where convergence of the residual sequence {Axk − b} may be obtained, while the sequence of iterates {xk} may diverge. For some of these special cases, under additional assumptions, we show that the iterate sequence is guaranteed to converge. For situations where the iterates diverge but the residuals converge to zero, we propose schemes for extracting from the divergent sequence another sequence that converges to a solution of Ax = b. Report LIDS-P-2879, April 2012 (Revised in December 2012) Massachusetts Institute of Technology, Cambridge, MA Laboratory for Information and Decision Systems
File Format	PDF HTM / HTML
Alternate Webpage(s)	http://www.mit.edu/~dimitrib/singular2.pdf
Alternate Webpage(s)	http://web.mit.edu/dimitrib/www/singular2.pdf
Alternate Webpage(s)	http://web.mit.edu/afs/athena.mit.edu/user/d/i/dimitrib/www/singular2.pdf
Alternate Webpage(s)	https://stuff.mit.edu/people/dimitrib/singular2.pdf
Alternate Webpage(s)	http://www.mit.edu/people/dimitrib/singular2.pdf
Alternate Webpage(s)	http://stuff.mit.edu/people/dimitrib/singular2.pdf
Language	English
Access Restriction	Open
Content Type	Text
Resource Type	Article