No Curse of Dimensionality for Contraction Fixed Points Even in the Worst Case
AbstractWe 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 InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by EconWPA in its series Computational Economics with number 9902001.
Length: 40 pages
Date of creation: 01 Feb 1999
Date of revision:
Note: TeX file, Postscript version submitted, 40 pages
Contact details of provider:
Web page: http://126.96.36.199
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:
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.
- John Rust & Department of Economics & University of Wisconsin, 1994.
"Using Randomization to Break the Curse of Dimensionality,"
9403001, EconWPA, revised 04 Jul 1994.
- John Rust, 1997. "Using Randomization to Break the Curse of Dimensionality," Econometrica, Econometric Society, vol. 65(3), pages 487-516, May.
- 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.
- Spassimir H. Paskov & Joseph F. Traub, 1995. "Faster Valuation of Financial Derivatives," Working Papers 95-03-034, Santa Fe Institute.
- 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.
- 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.
- George Hall & John Rust, 1999. "An Empirical Model of Inventory Investment by Durable Commodity Intermediaries," Macroeconomics 9904005, EconWPA.
- George J. Hall & John Rust, 1999. "An Empirical Model of Inventory Investment by Durable Commodity Intermediaries," Cowles Foundation Discussion Papers 1228, Cowles Foundation for Research in Economics, Yale University.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (EconWPA).
If references are entirely missing, you can add them using this form.