Stabilization of stochastic iterative methods for singular and nearly singular linear systems

Mengdi Wang, Dimitri P. Bertsekas

Research output: Contribution to journalArticle

7 Scopus citations

Abstract

We consider linear systems of equations, Ax Db, with an emphasis on the case where A is singular. Under certain conditions, necessary as well as sufficient, linear deterministic iterative methods generate sequences {x that converge to a solution as long as there exists at least one solution. This convergence property can be impaired when these methods are implemented with stochastic simulation, as is often done in important classes of large-scale problems. We introduce additional conditions and novel algorithmic stabilization schemes under which {x converges to a solution when A is singular and may also be used with substantial benefit when A is nearly singular.

Original languageEnglish (US)
Pages (from-to)1-30
Number of pages30
JournalMathematics of Operations Research
Volume39
Issue number1
DOIs
StatePublished - Feb 2014
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Computer Science Applications
  • Management Science and Operations Research

Keywords

  • Approximate dynamic programming
  • Projected equation
  • Regularization
  • Simulation
  • Singular system
  • Sstabilization
  • Stochastic algorithm

Fingerprint Dive into the research topics of 'Stabilization of stochastic iterative methods for singular and nearly singular linear systems'. Together they form a unique fingerprint.

  • Cite this