Help
Cart
Skip main navigation

Available Issues

August 2, 2017 - March 17, 2026

Available Issues

August 2, 2017 - March 17, 2026

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

Published Online:10 May 2013https://doi.org/10.1287/12-SSY074

References

  • Bradtke, S. J. and Barto, A. G., Linear least-squares algorithms for temporal difference learning. Machine Learning, 22:33–57, 1996.Google Scholar
  • Bellman, R., Introduction to Matrix Analysis, 2nd edition. McGraw-Hill, New York, 1970. MR0258847Google Scholar
  • Bertsekas, D. P., Approximate policy iteration: A survey and some new methods. Journal of Control Theory and Applications, 9:310–335, 2010. MR2833999Google Scholar
  • Bertsekas, D. P., Temporal difference methods for general projected equations. IEEE Trans. on Automatic Control, 56:2128–2139, 2011. MR2865769Google Scholar
  • Bertsekas, D. P., Dynamic Programming and Optimal Control, Vol. II: Approximate Dynamic Programming. Athena Scientific, Belmont, MA, 2012. MR2182753Google Scholar
  • 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. MR0654697Google Scholar
  • Ben-Israel, A. and Greville, T. N. E., Generalized Inverse: Theory and Applications. Wiley-Interscience, Springer-Verlag, New York, 1974. MR0396607Google Scholar
  • Benveniste, A., Metivier, M., and Priouret, P., Adaptive Algorithms and Stochastic Approximations. Springer-Verlag, New York, 1990. MR1082341Google Scholar
  • Bertsekas, D. P. and Tsitsiklis, J. N. Parallel and Distributed Computation: Numerical Methods. Athena Scientific, Belmont, MA, 1989.Google Scholar
  • Bertsekas, D. P. and Tsitsiklis, J. N. Neuro-Dynamic Programming. Athena Scientific, Belmont, MA, 1996.Google Scholar
  • Borkar, V. S., Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press, MA, 2008. MR2442439Google Scholar
  • Boyan, J. A., Technical update: Least-squares temporal difference learning. Machine Learning, 49:233–246, 2002.Google Scholar
  • 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. MR2512758Google Scholar
  • Cottle, R. W., Pang, J. S., and Stone, R. E., The Linear Complementarity Problem. Academic Press, Boston, MA, 1992. MR1150683Google Scholar
  • Dax, A., The convergence of linear stationary iterative processes for solving singular unstructured systems of linear equations. SIAM Review, 32:611–635, 1990. MR1084572Google Scholar
  • Drineas, P., Mahoney, M. W., and Muthukrishnan, S., Sampling algorithms for L2 regression and applications. Proc. 17th Annual SODA, pages 1127–1136, 2006. MR2373840Google Scholar
  • Drineas, P., Mahoney, M. W., Muthukrishnan, S., and Sarlos, T., Faster least squares approximation. Numerische Mathematik, 117:219–249, 2011. MR2754850Google Scholar
  • Facchinei, F. and Pang, J. S., Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, NY, 2003.Google Scholar
  • Goldberg, J. L., Matrix Theory with Applications. McGraw-Hill, New York, 1991.Google Scholar
  • Hageman, L. A. and Young, D. M., Applied Iterative Methods. Academic Press, NY, 1981. MR0630192Google Scholar
  • Keller, H. B., On the solution of singular and semidefinite linear systems by iteration. J. SIAM: Series B, Numerical Analysis, 2:281–290, 1965. MR0195244Google Scholar
  • 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.Google Scholar
  • Konda, V., Actor-critic algorithms. PhD Thesis, MIT, 2002.Google Scholar
  • Korpelevich, G. M., An extragradient method for finding saddle points and for other problems. Matecon, 12:747–756, 1976. MR0451121Google Scholar
  • Kosinski, K. M., On the functional limits for sums of a function of partial sums. Statistics and Probability Letters, 79:1552–1527, 2009.Google Scholar
  • Krasnoselskii, M. A., Approximate Solution of Operator Equations. D. Wolters-Noordhoff Pub., Groningen, 1972. MR0385655Google Scholar
  • Kannan, A. and Shanbhag, U. V., Distributed online computation of nash equilibria via iterative regularization techniques. SIAM Journal of Optimization (to appear), 2013.Google Scholar
  • 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. MR1885572Google Scholar
  • Kushner, H. J. and Yin, G., Stochastic Approximation and Recursive Algorithms and Applications. Springer, New York, 2003. MR1993642Google Scholar
  • 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. MR1110086Google Scholar
  • Sibony, M. Methodes iteratives pour les equations et inequations aux derivees partielles non lineaires de type monotone. Calcolo, 7:65–183, 1970. MR0659098Google Scholar
  • Martinet, B., Regularisation d’inequation variationelles par approximations successives. Rev. Francaise Inf. Rech. Oper., pages 154–159, 1970. MR0298899Google Scholar
  • Meyn, S. P., Control Techniques for Complex Systems. Cambridge University Press, MA, 2007.Google Scholar
  • Nedić, A. and Bertsekas, D. P., Least-squares policy evaluation algorithms with linear function approximation. Journal of Discrete Event Systems, 13:79–110, 2003. MR1972051Google Scholar
  • Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A., Robust stochastic approximation approach t stochastic programming. SIAM J. of Optimization, 19:1574–1609, 2009.Google Scholar
  • Pasupathy, R., On choosing parameters in retrospective-approximation algorithms for stochastic root finding and simulation optimization. Operations Research, 58:889–901, 2010.Link, Google Scholar
  • Powell, B. W., Approximate Dynamic Programming: Solving the Curses of Dimensionality, 2nd Ed. J. Wiley, New York, 2011. MR2839330Google Scholar
  • Puterman, M. L., Markovian Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, New York, NY, 1994. MR1270015Google Scholar
  • 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, New York, 2010.Google Scholar
  • Rockafellar, R. T., Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14:877–898, 1976. MR0410483Google Scholar
  • Saad, Y., Iterative Methods for Sparse Linear Systems. J. SIAM, Philadelphia, PA, 2003. MR1990645Google Scholar
  • Sutton, R. S. and Barto, A. G., Reinforcement Learning. MIT Press, Cambridge, MA, 1998.Google Scholar
  • Shapiro, A., Dentcheva, D., and Ruszczynski, A., Lectures on Stochastic Programming: Modeling and Theory. SIAM, Philadelphia, PA, 2009. MR2562798Google Scholar
  • Shapiro, A., Monte Carlo Sampling Methods, in Stochastic Programming. Handbook in OR & MS, Vol. 10, North-Holland, Amsterdam, 2003. MR2052758Google Scholar
  • Stewart, G. W. and Sun, J. G., Matrix Perturbation Theory. Academic Press, Boston, MA, 1990. MR1061154Google Scholar
  • Stewart, G. W., Introduction to Matrix Computations. Academic Press, New York, 1973. MR0458818Google Scholar
  • Stewart, G. W., Perturbation Theory for the Singular Value Decomposition. CS-TR-2539, College Park, MD, 1990.Google Scholar
  • Tanabe, K., Characterization of linear stationary iterative processes for solving a singular system of linear equations. Numerische Mathematik, 22:349–359, 1974. MR0351059Google Scholar
  • Trefethen, L. N. and Bau, D., Numerical Linear Algebra. J. SIAM, Philadelphia, Philadelphia, PA, 1997. MR1444820Google Scholar
  • 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.Google Scholar
  • Wedin, P. A., Perturbation bounds in connection with singular value decomposition. BIT, 12:99–111, 2012. MR0309968Google Scholar
  • 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, MA, 2009.Google Scholar
  • 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.Google Scholar
  • Young, D. M., On the consistency of linear stationary iterative methods. SIAM Journal on Numerical Analysis, 9:89–96, 1972. MR0312710Google Scholar
  • 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.Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree