The Contraction Mapping Theorem and Applications*

In this section, I present a number of mathematical results that are necessary for making progress with the dynamic programming formulation. In this sense, the current section is a “digression” from the main story line.

Recall from Appendix Chapter A that (S, d) is a metric space, if S is a space and d is a metric de fined over this space with the usual properties. The metric is referred to as “d” since it loosely corresponds to the “distance” between two elements of S. A metric space is more general than a finite-dimensional Euclidean space such as a subset of R^k. But as with the Euclidean space, we are most interested in defining mappings from the metric space into itself. These mappings are referred to as operators to distinguish them from real-valued functions and are often denoted by the letter T (thus T : S → S) and the standard notation often involves writing Tz for the image of a point z ∈ S under T (rather than the more familiar T (z)). Instead, the notation T (Z) stands for the image of a subset Z of S under T, that is,

then, T is a contraction mapping (with modulus β).

In other words, a contraction mapping brings elements of the space S “uniformly closer” to each other.

Definition 6.2.

Recall also that a metric space (S, d) is complete if every Cauchy sequence (whose elements are getting closer) in S converges to an element in S (see Appendix Chapter A). Despite its simplicity, the following theorem is one of the most powerful results in functional analysis.

Theorem 6.7. (Contraction Mapping Theorem) Let (S,d) be a complete metric space and suppose that T : S → S is a contraction. Then, T has a unique fixed point, z, i.e., there exists a unique z ∈ S such that

213

Repeating this argument

The Contraction Mapping Theorem can be used to prove many well-known results. The next example and Exercise 6.4 show how it can be used to prove existence of unique solutions to differential equations. Exercise 6.5 shows how it can be used to prove the Implicit Function Theorem (Theorem A.26 in Appendix Chapter A).

EXAMPLE 6.3. Consider the following one-dimensional differential equation

The Contraction Mapping Theorem, Theorem 6.7, can be used to prove the existence of a continuous function x* (t) that is the unique solution to this differential equation on any compact interval, in particular on [0,s] for some_ To do this, consider the space of continuous functions and define the following operator, T such that for any

Notice that T is a mapping from the space of continuous functions on [0,s] into itself, i.e., Moreover, it can be verified T is a contraction for some s. This follows by the Lipschitz continuity of f (∙).

where recall thatdenotes the sup norm, now defined over the space of functions. Choosing s < 1/M establishes that for s sufficiently small, T is indeed a contraction. Then, from Theorem 6.7, there exists a unique fixed point of T over C [0,s]. This fixed point is the unique solution to the differential equation and it is also continuous. Exercise 6.4 asks you to verify some of these steps and shows how the result can be extended so that it applies to C [0,x].

The main use of the Contraction Mapping Theorem for us is that it can be applied to any metric space and thus to the space of functions. Applying it to eq. (6.1) will establish the existence of a unique value function V in Problem A2, greatly facilitating the analysis of such dynamic models. Before doing this, let us consider another useful result. Recall that if (S, d) is a complete metric space and S' is a closed subset of S, then (S',d) is also a complete metric space.

The second part of this theorem is very important to prove results such as strict concavity or strict monotonicity of a function. This is because the set (space) of strictly concave func­tions or the set of the strictly increasing functions are not closed (and complete). Therefore, 215

the Contraction Mapping Theorem cannot be directly applied to these spaces of functions. The second part of this theorem enables us to circumvent this problem.

The previous two theorems show that the contraction mapping property is both simple and powerful. Nevertheless, beyond some simple cases, such as Example 6.2, it is difficult to check whether an operator is indeed a contraction. This may seem particularly difficult in the case of spaces whose elements correspond to functions, which are those that are relevant in the context of dynamic programming. The next theorem provides us with sufficient conditions for an operator to be a contraction that are typically straightforward to check. For this theorem, let us use the following notation: for a real valued function f (∙) and some constant c ∈ R we define (f + c)(x) ? f (x) + c. Then:

We will see that Blackwell’s sufficient conditions are straightforward to check in many economic applications, including the models of optimal or equilibrium growth.

6.5.