Bhattacharya R., Majumdar M. Random Dynamical Systems: Theory and Applications

Подождите немного. Документ загружается.

1.9 Some Applications 83

The optimization problem can then be written as



)











maximize



∞

t=0

w(c

t+1

, x

)

subject to c

t+1

= f (x

) − x

t+1

for t ∈ Z

t+1

≥ 0, x

t+1

≥ 0 for t ∈ Z

= x > 0

1.9.6 Dynamic Programming

We now introduce a model of intertemporal optimization that is partic-

ularly amenable to the use of the techniques of dynamic programming

and accommodates a variety of “reduced” models both in micro- and

macroeconomics. There is a single decision maker (a ﬁrm, a consumer, a

social planner . . . ) facing an optimization problem that can be formally

speciﬁed by (, u,δ). Here,  is a (nonempty) set in

× R

,tobe

interpreted as a technology or a transition possibility set. Let x, y be

(nonnegative) numbers (interpreted as stocks of a commodity). Then

={(x, y):

× R

∈ y can be reached from x}.

The utility (immediate return, felicity, proﬁt,...)function u is a non-

negative real-valued function deﬁned on , i.e., u : →

and δ is the

discount factor 0 <δ<1.

A program x = (x

)

∞

from x

is a sequence satisfying

= x

, x

t+1

) ∈ for t = 0, 1, 2,.... (9.38)

Given a program x from an initial x

∈ S, we write

R(x) ≡

∞



t=0

u(x

, x

t+1

)

R(x) is the discounted sum of one-period returns generated by the

program x.

A program x

∗

= (x

∗

)

∞

from x

is optimal if

∞



t=0

u(x

∗

, x

∗

t+1

) 

∞



t=0

u(x

, x

t+1

) (9.39)

84 Dynamical Systems

for all programs from x

The following basic assumptions will be maintained throughout:

[A.1] ⊂

× R

is a closed and convex set containing (0, 0),

“(0, y) ∈” implies “y = 0”; for any x ≥ 0, there is some y ≥ 0

such that (x, y) ∈.

[A.2] u : →

is a bounded, concave, and upper semicontinuous

function.

[A.3] There is some K

> 0 such that “(x, y) ∈, x > K

” implies

“y < x.”

We now prove a useful boundedness property.

Lemma 9.5 There is some B



> 0 such that

“(x, y) ∈,x≤ K

” implies “0 ≤ y ≤ B



.” (9.40)

Proof. If the claim is false, there is a sequence (x

, y

) ∈such that

0 ≤ x

≤ K

and y

 n for all n ≥ 1. Since (0, 0) ∈and is convex,

it follows that (

, 1) ∈for all n = 1, 2,.... Since  is closed, by

taking the limit we get (0, 1) ∈, a contradiction.

Now choose B = max(K

, B



). Then it is not difﬁcult to verify that if

x = (x

)

∞

is any program from x

∈ [0, B]

0 ≤ x

≤ B for all t ≥ 0.

We shall consider S = [0, B] as the state space, and assume hereafter

that x

∈ S.Now,letb be any constant such that

0 ≤ u(x, y) ≤ b, where 0 ≤ x ≤ B,0≤ y ≤ B.

Then for any program x = (x

)

∞

t=0

from x

∈ S, one has

R(x) ≤

1 − δ

Proposition 9.6 If (, u,δ) satisﬁes [A.1]–[A.3], then there exists an

optimal program from every initial x

∈ S.

Proof. The proof is left as an exercise (consult the proof of Theorem

9.1).

1.9 Some Applications 85

In this section, we provide some basic results by using the dynamic

programming approach. We can associate with each dynamic optimiza-

tion problem two functions, called the (optimal) value function and the

(optimal) transition function. The value function deﬁnes the optimal re-

turn (i.e., the left-hand side of (9.39)) corresponding to each initial state

. If there is a unique optimal solution x

∗

= (x

∗

)

∞

for each initial state

∈ S, the transition function deﬁnes the ﬁrst period optimal state x

∗

corresponding to each initial state x.

Given the stationary recursive nature of the optimization problem, the

optimal transition function, in fact, generates the entire optimal solu-

tion, starting from any initial state. The value function helps us to study

the properties of the transition function, given the connection between

the two through the functional equation of dynamic programming (see

(9.40)).

1.9.6.1 The Value Function

Given the existence of an optimal program from every x ∈ S (Proposition

9.6), we can deﬁne the value function, V : S →

, as follows:

V (x) =

∞



t=0



∗

, x

∗

t+1



, (9.40)

where x

∗

= (x

∗

)

∞

is an optimal program from the initial state x ∈ S.

The following result summarizes the basic properties of the value

function. Deﬁne, for any x ≥ 0



={y ∈ S:(x, y) ∈}.

Clearly, 

is a (nonempty) compact, convex subset of S.

Proposition 9.7

(i) The value function V is a concave and continuous function on S.

(ii) V satisﬁes the following functional equation of dynamic program-

ming

V (x) = max

y∈

{u(x, y) + δV (y)} (9.41)

for all x ∈ S.

86 Dynamical Systems

(iii) x = (x

)

∞

is an optimal program if and only if

V (x

) = u(x

, x

t+1

) + δV (x

t+1

) for t ∈ Z

(9.42)

Proof.

(i) Concavity of V follows from a direct veriﬁcation.

In order to establish the continuity of V on S, we ﬁrst establish its

upper semicontinuity.

If V were not upper semicontinuous on S, we could ﬁnd x

∈ S for n =

1, 2, 3,...,with x

→ x

and V (x

) → V as n →∞, with V > V (x

Let us denote by (x

) an optimal program from x

for n = 0, 1, 2,....

Denoting [V − V (x

)] by ε, we can ﬁnd T large enough so that

bδ

T +1

/(1 − δ) ≤ (ε/4).

Clearly, we can ﬁnd a subsequence n



(of n) such that for t ∈

{0, 1,...,T },

n

→ x

as n



→∞.

Then, using the upper semicontinuity of u, we can ﬁnd N such that for

t ∈{0, 1,...,T },





, x



t+1



≤ u



, x

t+1



+ [ε(1 − δ)/4]

whenever n



≥ N . Thus, for n



≥ N , we obtain the following string of

inequalities:

V (x

) =

∞



t=0



, x

t+1



≥



t=0



, x

t+1



− (ε/4)

≥



t=0





, x



t+1



− (ε/2)

≥

∞



t=0





, x



t+1



− 3(ε/4)

= V (x



) − 3(ε/4).

Since V (x



) → V ,wehaveV (x

) ≥ V − 3(ε/4) > V − ε = V (x

), a

contradiction. Thus, V is upper semicontinuous on S.

1.9 Some Applications 87

V is concave on S, and hence continuous on int S = (0, B). To

show that V is continuous at 0, let x

be a sequence of points in

S (n = 1, 2, 3,...) converging to 0. Then V (x

) = V ((1 − (x

/B))

0 + (x

/B)B) ≥ [1 − (x

/B)]V (0) + (x

/B)V (B). Letting n →∞,

lim inf

n→∞

V (x

) ≥ V (0). On the other hand, since V is upper semi-

continuous on X , lim sup

n→∞

V (x

) ≤ V (0). Thus, lim

n→∞

V (x

) exists

and equals V (0). The continuity of V at B is established similarly.

(ii) Let y ∈

, and let (y

)

∞

be an optimal program from y. Then

(x, y

, y

,....) is a program from x, and hence, by deﬁnition of V ,

V (x) ≥ u(x, y

) +

∞



t=1

u(y

t−1

, y

)

= u(x, y

) + δ

∞



t=1

t−1

u(y

t−1

, y

)

= u(x, y

) + δ

∞



t=0

u(y

, y

t+1

)

= u(x, y

) + δV (y).

So we have established that

V (x) ≥ u(x, y) +δV (y) for all y ∈

. (9.43)

Next, let x = (x

)

∞

be an optimal program from x, and note that

V (x) = u(x

, x

) + δ



∞



t=1

t−1

u(x

, x

t+1

)



= u(x

, x

) + δ



∞



t=0

u(x

t+1

, x

t+2

)



≤ u(x

, x

) + δV (x

Using (9.43), we then have

V (x) = u(x

, x

) + δV (x

). (9.44)

Now, (9.43) and (9.44) establish (9.41).

(iii) If (x

)

∞

satisﬁes (9.41), then we get for any T ≥ 1,

V (x) =



t=0

u(x

, x

t+1

) + δ

T +1

V (x

T +1

). (9.45)

88 Dynamical Systems

Since 0 ≤ V (x) ≤ b/(1 − δ) for all x ∈ S and δ

T +1

→ 0asT →∞,we

have

8V (x) =

∞



t=0

u(x

, x

t+1

Then, by the deﬁnition of V, (x

)

∞

is an optimal program (from x).

To establish the converse implication, let (x

∗

)

∞

be an optimal program

from x = x

∗

. Then, for each T ≥ 1, (x

∗

, x

∗

T +1

,...) is an optimal program

from x

∗

.For,if(y

)

∞

is a program from y

= x

∗

such that

∞



t=0

u(y

, y

t+1

) >

∞



t=T

t−T



∗

, x

∗

t+1



then the sequence (x

∗

,...,x

∗

, y

,...) has a discounted sum of

utilities

T −1



t=0



∗

, x

∗

t+1



∞



t=T

u(y

, y

t+1

) >

∞



t=0



∗

, x

∗

t+1



which contradicts the optimality of (x

∗

)

∞

from x = x

∗

. Now, using the

result (9.43) in (ii) above, we have V (x

∗

) = u(x

∗

, x

∗

t+1

) + δV (x

∗

t+1

) for

t ∈

1.9.6.2 The Optimal Transition Function

Recall that Proposition 9.6 guarantees existence of an optimal program,

but not its uniqueness. However, a strict concavity assumption on u is

sufﬁcient to guarantee uniqueness.

[A.4] u is strictly concave in its second argument.

If [A.4] holds, then given any x ∈ S, there is a unique solution

to the maximization problem on the right-hand side of (9.40). For

if y and y



= y)in

both solve this problem, then V (x) =

u(x, y) + δV (y) and V (x) = u(x, y



) + δV (y



). However, (x,0.5y +

0.5y



) ∈, and u(x, 0.5y + 0.5y



) + δV (0.5y + 0.5y



) > 0.5u(x, y) +

0.5u(x, y



) + δ[0.5V (y) + 0.5V (y



)] = V (x), a contradiction to (9.40).

For each x, denote the unique state y ∈

, which solves the maxi-

mization problem on the right-hand side of (9.40) by h(x). We will call

h : S → S the optimal transition function.

The following result summarizes the basic properties of h.

1.9 Some Applications 89

Proposition 9.8

(i) The optimal transition function h : S → S is continuous on S.

(ii) For all (x, y) ∈with y = h(x) we have

u(x, y) + δV (y) < V (x) = u(x, h(x)) + δV (h(x)). (9.46)

(iii) (x

)

∞

is an optimal program from x if and only if

t+1

= h(x

) for t ∈ Z

. (9.47)

Proof.

(i) Let (x

)(n = 1, 2, 3,...) be a sequence of points in S converging

to x

. Then for n = 1, 2, 3,...,

V (x

) = u(x

, h(x

)) + δV (h(x

)). (9.48)

Let (y



) be an arbitrary convergent subsequence of (y

) ≡ (h(x

)) con-

verging to y

. We claim that y

= h(x

). For the subsequence n



, using

(9.48), the upper semicontinuity of u and the continuity of V ,

V (x

) = lim sup



→∞

u(x



, y



) + δV (y

)

≤ u(x

, y

) + δV (y

But, by (9.41), V (x

) ≥ u(x

, y

) + δV (y

), so that V (x

) =

u(x

, y

) + δV (y

). This means that y

= h(x

), establishing our claim.

Thus, h(x

) → h(x

)asn →∞, establishing continuity of h.

(ii) We have V (x) = u(x, h(x)) + δV (h(x)) from (9.41) and the def-

inition of h. For all y ∈

,wehaveu(x, y) + δV (y) ≤ V (x) by (9.41).

Further, if equality holds in the previous weak inequality, then y = h(x).

Thus if y = h(x), the strict inequality must hold. This establishes (9.46).

(iii) If (x

)

∞

is an optimal program from x, then by Proposition 9.7

(iii), for every t ∈

V (x

) = u(x

, x

t+1

) + δV (x

t+1

)

so that by the just established part (ii) of the proposition, x

t+1

= h(x

Conversely, if (9.48) holds, then by part (ii) of this proposition, we

have for t ∈

V (x

) = u(x

, x

t+1

) + δV (x

t+1

)

so that (x

)

∞

is an optimal program by Proposition 9.7 (iii).

90 Dynamical Systems

1.9.6.3 Monotonicity With Respect to the Initial State

The concept that is crucial to establishing monotonicity properties of the

policy function is known as supermodularity, and was introduced into

the optimization theory literature by Topkis (1978).

Let A be a subset of

and f be a function from A to

R. Then f

is supermodular on A if whenever (a, b) and (a



, b



) belong to A with



, b



) ≥ (a, b), we have

f (a, b) + f (a



, b



) ≥ f (a, b



) + f (a



, b), (9.49)

provided (a, b



) and (a



, b) belong to A.

If A is a rectangular region, then whenever (a, b) and (a



, b



) belong

to A,wehave(a, b



) and (a



, b) also in A. Further, for such a region if f

is continuous on A and C

on int A, then

(a, b) ≥ 0 for all (a, b) ∈ int A (9.50)

is equivalent to the condition that f is supermodular on A. (For this

result, see Ross (1983); Benhabib and Nishimura (1985).)

Let (, u,δ) be a dynamic optimization model. The principal result

on the montonicity of its optimal transition function h with respect to the

initial condition x is that if u is supermodular on , then h is monotone

nondecreasing in x. (This result is based on the analysis in Topkis (1978),

Benhabib and Nishimura (1985).) We need an additional assumption

on :

[A.5] If (x, z) ∈and x



∈ S, x



≥ x,0≤ z



≤ z, then (x



, z



) ∈.

Proposition 9.9 Let (, u,δ) be a dynamic optimization model, with

value function V and optimal transition function h. If u is supermodular

on , then h is monotone nondecreasing on S.

Proof. Let x, x



belong to S with x



> x. Denote h(x)byz and h(x



)

by z



. We want to show that z



≥ z. Suppose, on the contrary, that



< z. Since (x, z) ∈and z



∈ S with z



≤ z,wehave(x, z



) ∈.

Since (x, z) ∈and x



∈ S with x



≥ x,wehave(x



, z) ∈. Using the

deﬁnition of supermodularity, and (x



, z) ≥ (x, z



), we have

u(x, z



) + u(x



, z) ≥ u(x, z) + u(x



, z



). (9.51)

Since z = h(x) and z



= h(x



), we have

V (x) = u(x, z) + δV (z) (9.52)

1.9 Some Applications 91

and

V (x



) = u(x



, z



) + δV (z



). (9.53)

Since (x, z



) ∈and (x



, z) ∈, and z



= z,wehavez



= h(x), z =

h(x



), so

V (x) > u(x, z



) + δV (z



) (9.54)

and

V (x



) > u(x



, z) +δV (z). (9.55)

Adding (9.52) and (9.53),

V (x) + V (x



) = u(x, z) + u(x



, z



) + δV (z) + δV (z



). (9.56)

Adding (9.54) and (9.55)

V (x) + V (x



) > u(x, z



) + u(x



, z) +δV (z



) + δV (z). (9.57)

Using (9.56) and (9.57),

u(x, z) + u(x



, z



) > u(x, z



) + u(x



, z),

which contradicts (9.51) and establishes the result.

Exercise 9.6 Consider the optimization problem 1.9.4.1. Write down

the reduced form of this problem. [Hint: think of u(c

) =

u( f (x

t−1

) − x

).]

Remark 9.6 It follows from the above result that, in the framework of

Proposition 5.2, if (x

) is an optimal program starting from x ∈ S, then

either (i) x

t+1

≥ x

for all t ∈ Z

or (ii) x

t+1

≤ x

for all t ∈ Z

Remark 9.7 Some deﬁnitive results illuminating the link between the

discount factor δ and Li–Yorke chaos have been obtained. A comprehen-

sive treatment of this problem is available in Chapters 9–13 (written by

Mitra, Nishimura, Sorger, and Yano) of Majumdar, Mitra, and Nishimura

(2000). By introducing appropriate strict concavity and monotonicity

assumptions on  and u, Mitra (Chapter 11) proves that if the optimal

transition function h of a model (, u,δ) exhibits a three-period cycle,

then δ<[(

√

5 − 1)/2]

. Furthermore, this restriction on δ is the best

possible: whenever δ<[(

√

5 − 1)/2]

, Mitra constructs a technology 

92 Dynamical Systems

and a utility function u such that the optimal transition function h of

(, u,δ) exhibits a three-period cycle. This construction is based on the

example of Nishimura, Sorger and Yano (Chapter 9).

Here is a special case of Sorger (1992) (the proof of which is due to

T. Mitra). Choose units of measurement so that S = [0, 1], and assume

u(0, 0) = 0, strengthen [A.4] and assume that u : →

is strictly

concave: u(θ(x, y) +(1 − θ)(x



, y



)) >θu(x, y) +(1 − θ)u(x



, y



), for

0 <θ <1 (where (x, y) ∈,(x



, y



) ∈). Suppose that in this model

(, u,δ) the optimal transition function h is of the form

h(x) = 4x(1 − x)0≤ x ≤ 1. (9.57.1)

Then the discount factor δ must satisfy

δ<

, (R)

To see how the restriction (R) on δ emerges, note that if the optimal

transition function h is given by (9.57.1) then the sequence

∗



∗



∞

={(1/2), 1, 0, 0,...} (9.57.2)

is an optimal program from (1/2).

Now, suppose, to the contrary, that δ ≥ (1/2). Deﬁne θ = 1/(1 +2δ),

and note that 0 <θ ≤ (1/2). One establishes a contradiction by showing

that a program that starts at (1/2) then goes to θ in the next period and

thereafter follows an optimal program from θ, provides higher discounted

sum of utilities than the program (9.57.2) from 1/2; that is, u[(1/2),θ] +

δV (θ ) > V (1/2).

Since u(0, 0) = 0wehaveV (0) = 0. Now [(1/2),θ] = [θ(1/2) +

θδ(1) + θδ(0), θ (1) +θδ(0) +θδ(0)]. Since ((1/2), 1) ∈and (1, 0) ∈

 and (0, 0) ∈, and θ + θδ + θδ = 1, we have [(1/2),θ] ∈by con-

vexity of . Further, strict concavity of u and u(0, 0) = 0 imply that

u((1/2),θ) >θu((1/2), 1) + θδu(1, 0). (9.57.3)

Now, since 1 = h(1/2) and 0 = h(1), we have by the optimality equation

u((1/2), 1) = V (1/2) − δV (1) (9.57.4)

u(1, 0) = V (1) − δV (0) = V (1). (9.57.5)