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

John Rust (), J. F. Traub () and H. Wozniakowski ()
Additional contact information
J. F. Traub: Department of Computer Science, Columbia University, New York, USA
H. Wozniakowski: Department of Computer Science, Columbia University, New York, USA and Institute of Applied Mathematics and Mechanics, University of Warsaw, Poland

Econometrica, 2002, vol. 70, issue 1, pages 285-329

Abstract: This paper analyzes the complexity of the "contraction fixed point problem": compute an epsilon-approximation to the fixed point "V"*Gamma("V"*) of a contraction mapping Gamma that maps a Banach space "B-sub-d" of continuous functions of "d" variables into itself. We focus on "quasi linear contractions" where Gamma 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 Gamma, 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 epsilon-approximation to a fixed point "V"* is an element of "B-sub-d" increases exponentially in "d". We show that the curse of dimensionality disappears if the domain of Gamma has additional special structure. We identify a particular type of special structure for which the problem is "strongly tractable" even in the worst case, i.e., the number of function evaluations and arithmetic operations needed to compute an epsilon-approximation of "V"* is bounded by "C"epsilon-super- - "p" where "C" and "p" are constants independent of "d". 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 exponent "p"1 is nearly achieved. Copyright The Econometric Society 2002.

Date: 2002
View citations in EconPapers

Downloads: (external link)
http://www.blackwellpublishing.com/ecta/asp/abstract.asp?iid=1&aid=276&vid=70 link to full text (text/html)
Access to full text is restricted to subscribers.

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: http://EconPapers.repec.org/RePEc:ecm:emetrp:v:70:y:2002:i:1:p:285-329

Ordering information: This journal article can be ordered from
http://www.blackwell ... mb.asp?ref=0012-9682

Access Statistics for this article

Econometrica is edited by Stephen Morris

More articles in Econometrica from Econometric Society
Contact information at EDIRC.
Series data maintained by Christopher F. Baum ().