Is There a Curse of Dimensionality for Contraction Fixed Points in the Worst Case?

Econometrica · 2002 · Volume 70 · Issue 1

Abstract

This paper analyzes the complexity of thecontraction fixed point problem: compute an ε-approximation to the fixed pointV*Γ(V*) of a contraction mapping Γ that maps a Banach spaceBdof continuous functions ofdvariables into itself. We focus onquasi linear contractionswhere Γ is a nonlinear functional of a finite number of conditional expectation operators. This class includes contractive Fredholm integral equations that arise in asset pricing applications and the contractive Bellman equation from dynamic programming. In the absence of further restrictions on the domain of Γ, the quasi linear fixed point problem is subject to the curse of dimensionality, i.e., in the worst case the minimal number of function evaluations and arithmetic operations required to compute an ε-approximation to a fixed pointV*∈Bdincreases exponentially ind. We show that the curse of dimensionality disappears if the domain of Γ has additional special structure. We identify a particular type of special structure for which the problem isstrongly tractableeven in the worst case, i.e., the number of function evaluations and arithmetic operations needed to compute an ε-approximation ofV* is bounded byCε−pwhereCandpare constants independent ofd. We present examples of economic problems that have this type of special structure including a class of rational expectations asset pricing problems for which the optimal exponentp1 is nearly achieved.

Keywords

contraction mappings, quasi linear, curse of dimensionality, strong tractability, computational complexity, dynamic program, rational expectations models

Enable JavaScript for citation tools and additional paper interactions.