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

This file is part of IDEAS, which uses RePEc data

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

Author Info

John Rust (Department of Economics Yale University)
Joseph Traub (Computer Science, Columbia University)
Henryk Wozniakowski (Computer Science, Columbia University)

Additional information is available for the following registered author(s):

John Rust

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.

Download Info
To download:

If you experience problems downloading a file, check if you have the proper application to view it first. Information about this may be contained in the File-Format links below. In case of further problems read the IDEAS help file. Note that these files are not on the IDEAS site. Please be patient as the files may be large.

Publisher Info
Paper provided by EconWPA in its series Computational Economics with number 9902001.

Download reference. The following formats are available: HTML (with abstract), plain text (with abstract), BibTeX, RIS (EndNote), ReDIF
Length: 40 pages
Date of creation: 01 Feb 1999
Date of revision:
Handle: RePEc:wpa:wuwpco:9902001

Note: TeX file, Postscript version submitted, 40 pages
Contact details of provider:
Web page: http://129.3.20.41

For technical questions regarding this item, or to correct its listing, contact: (EconWPA).

Related research
Keywords:

Other versions of this item:

Find related papers by JEL classification:
C8 - Mathematical and Quantitative Methods - - Data Collection and Data Estimation Methodology; Computer Programs

This paper has been announced in the following NEP Reports:

NEP-ALL-1999-02-15 (All new papers)
NEP-DGE-1999-02-15 (Dynamic General Equilibrium)

References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:

Rust, John, 1985. "Stationary Equilibrium in a Market for Durable Assets," Econometrica, Econometric Society, vol. 53(4), pages 783-805, July. [Downloadable!] (restricted)
John Rust, 1997. "Using Randomization to Break the Curse of Dimensionality," Econometrica, Econometric Society, vol. 65(3), pages 487-516, May.
Other versions:
- John Rust & Department of Economics & University of Wisconsin, 1994. "Using Randomization to Break the Curse of Dimensionality," Computational Economics 9403001, EconWPA, revised 04 Jul 1994. [Downloadable!]
John Rust, 1997. "A Comparison of Policy Iteration Methods for Solving Continuous-State, Infinite-Horizon Markovian Decision Problems Using Random, Quasi-random, and Deterministic Discretizations," Computational Economics 9704001, EconWPA. [Downloadable!]
Tauchen, George & Hussey, Robert, 1991. "Quadrature-Based Methods for Obtaining Approximate Solutions to Nonlinear Asset Pricing Models," Econometrica, Econometric Society, vol. 59(2), pages 371-96, March. [Downloadable!] (restricted)
Spassimir H. Paskov & Joseph F. Traub, 1995. "Faster Valuation of Financial Derivatives," Working Papers 95-03-034, Santa Fe Institute.

Full references

Cited by:
(explanations, Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.)

George J. Hall & John Rust, 1999. "An Empirical Model of Inventory Investment by Durable Commodity Intermediaries," Cowles Foundation Discussion Papers 1228, Cowles Foundation, Yale University. [Downloadable!]
Other versions:
- George Hall & John Rust, 1999. "An Empirical Model of Inventory Investment by Durable Commodity Intermediaries," Macroeconomics 9904005, EconWPA. [Downloadable!]
- Hall, George & Rust, John, 2000. "An empirical model of inventory investment by durable commodity intermediaries," Carnegie-Rochester Conference Series on Public Policy, Elsevier, vol. 52(1), pages 171-214, June. [Downloadable!] (restricted)

Statistics

Access and download statistics

Did you know? You too can volunteer for RePEc, for example by editing a NEP report.

This page was last updated on 2009-7-2.

This information is provided to you by IDEAS at the Department of Economics, College of Liberal Arts and Sciences, University of Connecticut using RePEc data on a server sponsored by the Society for Economic Dynamics.