No Curse of Dimensionality for Contraction Fixed Points Even in the Worst Case

John Rust (), Joseph Traub and Henryk Wozniakowski
Additional contact information
Joseph Traub: Computer Science, Columbia University
Henryk Wozniakowski: Computer Science, Columbia University

Computational Economics from University Library of Munich, Germany

Abstract: We consider the problem of computing approximations to fixed points of quasilinear contraction mappings defined on the space of continuous functions of $d$ variables. Our main emphasis is on large d. Examples of such mappings include the Bellman operator from the theory of dynamic programming. This paper proves that there exist deterministic algorithms for computing approximations to fixed points for some classes of quasilinear contraction mappings which are strongly tractable, i.e., in the worst case the number of function evaluations needed to compute an e-approximation to the solution at any finite number of points in its domain is bounded by C/e^p where both C and p are independent of d. This is done by using relations between the quasilinear contraction problem and the conditional expectation and approximation problems. The conditional expectation problem is equivalent to weighted multivariate integration. This allows us to apply recent proof technique and results on the strong tractability of weighted multivariate integration and approximation to establish strong tractability for the quasilinear fixed point problem. In particular, this holds when the fixed points belong to a Sobolev space for a specific weighted norm.

JEL-codes: C8 (search for similar items in EconPapers)
Pages: 40 pages
Date: 1999-02-01
New Economics Papers: this item is included in nep-dge
Note: TeX file, Postscript version submitted, 40 pages
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://econwpa.ub.uni-muenchen.de/econ-wp/comp/papers/9902/9902001.ps.gz (application/postscript)
https://econwpa.ub.uni-muenchen.de/econ-wp/comp/papers/9902/9902001.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wpa:wuwpco:9902001

Access Statistics for this paper

More papers in Computational Economics from University Library of Munich, Germany
Bibliographic data for series maintained by EconWPA ( this e-mail address is bad, please contact ).