×

On the convergence of simulation-based iterative methods for solving singular linear systems. (English) Zbl 1295.65037

Summary: We consider the simulation-based solution of systems of linear 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 \(\{Ax_k - b\}\) may be obtained, while the sequence of iterates \(\{x_k\}\) 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\).

MSC:

65F10 Iterative numerical methods for linear systems
65F20 Numerical solutions to overdetermined systems, pseudoinverses
65C05 Monte Carlo methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bradtke, S. J. and Barto, A. G., Linear least-squares algorithms for temporal difference learning. Machine Learning , 22:33-57, 1996. · Zbl 0845.68091 · doi:10.1007/BF00114723
[2] Bellman, R., Introduction to Matrix Analysis, 2nd edition . McGraw-Hill, N. Y, 1970. · Zbl 0216.06101
[3] Bertsekas, D. P., Approximate policy iteration: A survey and some new methods. Journal of Control Theory and Applications , 9:310-335, 2010. · Zbl 1249.90179 · doi:10.1007/s11768-011-1005-3
[4] Bertsekas, D. P., Temporal difference methods for general projected equations. IEEE Trans. on Automatic Control , 56:2128-2139, 2011. · Zbl 1368.90155 · doi:10.1109/TAC.2011.2115290
[5] Bertsekas, D. P., Dynamic Programming and Optimal Control, Vol. II: Approximate Dynamic Programming . Athena Scientific, Belmont, M. A, 2012. · Zbl 1298.90001
[6] Bertsekas, D. P. and Gafni, E. M., Projection methods for variational inequalities with application to the traffic assignment problem. Mathematical Programming Study , 17:139-159, 1982. · Zbl 0478.90071 · doi:10.1007/BFb0120965
[7] Ben-Israel, A. and Greville, T. N. E., Generalized Inverse: Theory and Applications . Wiley-Interscience, Springer-Verlag, N. Y, 1974. · Zbl 0305.15001
[8] Benveniste, A., Metivier, M., and Priouret, P., Adaptive Algorithms and Stochastic Approximations . Springer-Verlag, NY, 1990. · Zbl 0752.93073
[9] Bertsekas, D. P. and Tsitsiklis, J. N. Parallel and Distributed Computation: Numerical Methods . Athena Scientific, Belmont, MA, 1989. · Zbl 0743.65107
[10] Bertsekas, D. P. and Tsitsiklis, J. N. Neuro-Dynamic Programming . Athena Scientific, Belmont, MA, 1996. · Zbl 0924.68163
[11] Borkar, V. S., Stochastic Approximation: A Dynamical Systems Viewpoint . Cambridge University Press, MA, 2008. · Zbl 1159.60002
[12] Boyan, J. A., Technical update: Least-squares temporal difference learning. Machine Learning , 49:233-246, 2002. · Zbl 1014.68072 · doi:10.1023/A:1017936530646
[13] Bertsekas, D. P. and Yu, H., Projected equation methods for approximate solution of large linear systems. Journal of Computational and Applied Mathematics , 227:27-50, 2009. · Zbl 1165.65010 · doi:10.1016/j.cam.2008.07.037
[14] Cottle, R. W., Pang, J. S., and Stone, R. E., The Linear Complementarity Problem . Academic Press, Boston, MA, 1992. · Zbl 0757.90078
[15] Dax, A., The convergence of linear stationary iterative processes for solving singular unstructured systems of linear equations. SIAM Review , 32:611-635, 1990. · Zbl 0718.65021 · doi:10.1137/1032122
[16] Drineas, P., Mahoney, M. W., and Muthukrishnan, S., Sampling algorithms for L2 regression and applications. Proc. 17th Annual SODA , pages 1127-1136, 2006. · Zbl 1194.62010 · doi:10.1145/1109557.1109682
[17] Drineas, P., Mahoney, M. W., Muthukrishnan, S., and Sarlos, T., Faster least squares approximation. Numerische Mathematik , 117:219-249, 2011. · Zbl 1218.65037 · doi:10.1007/s00211-010-0331-6
[18] Facchinei, F. and Pang, J. S., Finite-Dimensional Variational Inequalities and Complementarity Problems . Springer, NY, 2003. · Zbl 1062.90002 · doi:10.1007/b97544
[19] Goldberg, J. L., Matrix Theory with Applications . McGraw-Hill, N. Y, 1991. · Zbl 0746.90055
[20] Hageman, L. A. and Young, D. M., Applied Iterative Methods . Academic Press, NY, 1981. · Zbl 0459.65014
[21] Keller, H. B., On the solution of singular and semidefinite linear systems by iteration. J. SIAM: Series B, Numerical Analysis , 2:281-290, 1965. · Zbl 0135.37503 · doi:10.1137/0702022
[22] Koshal, J., Nedić, A., and Shanbhag, U. V., Regularized iterative stochastic approximation methods for stochastic variational inequality problems. IEEE Transactions on Automatic Control , 58:594-608, 2013. · Zbl 1369.49012 · doi:10.1109/TAC.2012.2215413
[23] Konda, V., Actor-critic algorithms. PhD Thesis, MIT , 2002. · Zbl 1049.93095
[24] Korpelevich, G. M., An extragradient method for finding saddle points and for other problems. Matecon , 12:747-756, 1976. · Zbl 0342.90044
[25] Kosinski, K. M., On the functional limits for sums of a function of partial sums. Statistics and Probability Letters , 79:1552-1527, 2009. · Zbl 1168.60339 · doi:10.1016/j.spl.2009.03.011
[26] Krasnoselskii, M. A., Approximate Solution of Operator Equations . D. Wolters-Noordhoff Pub., Groningen, 1972.
[27] Kannan, A. and Shanbhag, U. V., Distributed online computation of nash equilibria via iterative regularization techniques. SIAM Journal of Optimization (to appear) , 2013. · Zbl 1281.90072
[28] Kleywegt, A. J., Shapiro, A., and Homem-de Mello, T., The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. , 12:479-502, 2002. · Zbl 0991.90090 · doi:10.1137/S1052623499363220
[29] Kushner, H. J. and Yin, G., Stochastic Approximation and Recursive Algorithms and Applications . Springer, NY, 2003. · Zbl 1026.62084
[30] Luo, Z. Q. and Tseng, P. On the convergence of a matrix splitting algorithm for the symmetric monotone linear complementarity problem. SIAM Journal of Control and Optimization , 29:1037-1060, 1989. · Zbl 0734.90101 · doi:10.1137/0329057
[31] Sibony, M. Methodes iteratives pour les equations et inequations aux derivees partielles non lineaires de type monotone. Calcolo , 7:65-183, 1970. · Zbl 0225.35010 · doi:10.1007/BF02575559
[32] Martinet, B., Regularisation d’inequation variationelles par approximations successives. Rev. Francaise Inf. Rech. Oper. , pages 154-159, 1970. · Zbl 0215.21103
[33] Meyn, S. P., Control Techniques for Complex Systems . Cambridge University Press, MA, 2007. · Zbl 1139.91002
[34] Nedić, A. and Bertsekas, D. P., Least-squares policy evaluation algorithms with linear function approximation. Journal of Discrete Event Systems , 13:79-110, 2003. · Zbl 1030.93061 · doi:10.1023/A:1022192903948
[35] Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A., Robust stochastic approximation approach t stochastic programming. SIAM J. of Optimization , 19:1574-1609, 2009. · Zbl 1189.90109 · doi:10.1137/070704277
[36] Pasupathy, R., On choosing parameters in retrospective-approximation algorithms for stochastic root finding and simulation optimization. Operations Research , 58:889=901, 2010. · Zbl 1228.90069
[37] Powell, B. W., Approximate Dynamic Programming: Solving the Curses of Dimensionality, 2nd Ed. J. Wiley, N. Y, 2011. · Zbl 1242.90002 · doi:10.1002/9781118029176
[38] Puterman, M. L., Markovian Decision Processes: Discrete Stochastic Dynamic Programming . John Wiley and Sons, New York, NY, 1994. · Zbl 0829.90134
[39] Polydorides, N., Wang, M., and Bertsekas, D. P., A quasi monte carlo method for large-scale linear inverse problems. Proc. Monte Carlo and Quasi-Monte Carlo, Springer, N. Y , 2010. · Zbl 1271.65008
[40] Rockafellar, R. T., Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization , 14:877-898, 1976. · Zbl 0358.90053 · doi:10.1137/0314056
[41] Saad, Y., Iterative Methods for Sparse Linear Systems . J. SIAM, Philadelphia, P. A, 2003. · Zbl 1031.65046
[42] Sutton, R. S. and Barto, A. G., Reinforcement Learning . MIT Press, Cambridge, M. A, 1998.
[43] Shapiro, A., Dentcheva, D., and Ruszczynski, A., Lectures on Stochastic Programming: Modeling and Theory . SIAM, Phila., PA, 2009. · Zbl 1183.90005
[44] Shapiro, A., Monte Carlo Sampling Methods, in Stochastic Programming . Handbook in OR & MS, Vol. 10, North-Holland, Amsterdam, 2003. · Zbl 1053.90103 · doi:10.1016/S0927-0507(03)10006-0
[45] Stewart, G. W. and Sun, J. G., Matrix Perturbation Theory . Academic Press, Boston, M. A, 1990. · Zbl 0706.65013
[46] Stewart, G. W., Introduction to Matrix Computations . Academic Press, NY, 1973. · Zbl 0302.65021
[47] Stewart, G. W., Perturbation Theory for the Singular Value Decomposition . CS-TR-2539, College Park, M. D. 1990.
[48] Tanabe, K., Characterization of linear stationary iterative processes for solving a singular system of linear equations. Numerische Mathematik , 22:349-359, 1974. · Zbl 0312.65031 · doi:10.1007/BF01436918
[49] Trefethen, L. N. and Bau, D., Numerical Linear Algebra . J. SIAM, Philadelphia, Philadelphia, P. A, 1997. · Zbl 0874.65013
[50] Wang, M. and Bertsekas, D. P., Stabilization of stochastic iterative methods for singular and nearly singular linear systems. Lab. for Information and Decision Systems Report , LIDS-P-2878:MIT, Cambridge, MA, 2011.
[51] Wedin, P. A., Perturbation bounds in connection with singular value decomposition. BIT , 12:99-111, 2012. · Zbl 0239.15015 · doi:10.1007/BF01932678
[52] Wang, M., Polydorides, N., and Bertsekas, D. P., Approximate simulation-based solution of large-scale least squares problems. Lab. for Information and Decision Systems Report LIDS-P-2819, MIT, Cambridge, M. A , 2009.
[53] Yu, H. and Bertsekas, D. P., Weighted bellman equations and their applications in dynamic programming. Lab. for Information and Decision Systems Report LIDS-P-2876, MIT , 2012.
[54] Young, D. M., On the consistency of linear stationary iterative methods. SIAM Journal on Numerical Analysis , 9:89-96, 1972. · Zbl 0234.65054 · doi:10.1137/0709010
[55] Zhang, L. X. and Huang, W., A note on the invariance principle of the product of sums of random variables. Elect. Comm. in Probability , 12:51-56, 2007. · Zbl 1130.60027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.