No Curse of Dimensionality for Contraction Fixed Points Even in the Worst Case
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.
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.
- 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-396, March.
- Spassimir H. Paskov & Joseph F. Traub, 1995. "Faster Valuation of Financial Derivatives," Working Papers 95-03-034, Santa Fe Institute.
- John Rust, 1997.
"Using Randomization to Break the Curse of Dimensionality,"
Econometric Society, vol. 65(3), pages 487-516, May.
- 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.
- Rust, J., 1994. "Using Randomization to Break the Curse of Dimensionality," Working papers 9429, Wisconsin Madison - Social Systems.
- 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. Full references (including those not matched with items on IDEAS)