Some existence theorems for functional equations arising in dynamic programming

SOME EXISTENCE THEOREMS FOR FUNCTIONAL EQUATIONS ARISING IN DYNAMIC PROGRAMMING

Zeqing Liu, Jeong Sheok Ume ^∗ , and Shin Min Kang

Abstract. The existence, uniqueness and iterative approximation of solutions for a few classes of functional equations arising in dy- namic programming of multistage decision processes are discussed.

The results presented in this paper extend, improve and unify the results due to Bellman [2, 3], Bhakta-Choudhury [6], Bhakta-Mitra [7], and Liu [12].

1. Introduction and preliminaries

Bellman [2, 3] first studied the existence of solutions for several classes of functional equations arising in dynamic programming. Bellman and Roosta [5] constructed an approximation solution for a class of the infinite-stage equation arising in dynamic programming. Bellman and Lee [4] pointed out that the basic form of the functional equations of dynamic programming is

(1.1) f (x) = sup

y∈D

H(x, y, f (T (x, y))), x ∈ S,

where x and y represent the state and decision vectors, respectively, T represents the transformation of the process, and f (x) represents the op- timal return function with initial state x. Baskaran and Subrahmanyam [1], Bhakta and Choudhury [6], Bhakta and Mitra [7], Chang [8], Chang and Ma [9], Liu [10]-[12] and others extended the results of [2]-[5] in

Received July 24, 2004.

2000 Mathematics Subject Classification: 49L20, 49L99, 90C39.

Key words and phrases: dynamic programming, nonexpansive mapping, func- tional equation.

∗

This work was supported by Korea Research Foundation Grant (KRF-2003-015-

C00039).

various directions. Bhakta and Mitra [7] established the existence and uniqueness of solutions for the functional equation:

(1.2) f (x) = sup

y∈D

{u(x, y) + f (T (x, y))}, x ∈ S.

Under suitable conditions, Bellman [2], Bhakta and Choudhury [6] and Liu [12] obtained the existence or uniqueness of solutions for the func- tional equations:

(1.3) f (x) = inf

y∈D max{u(x, y), f (T (x, y))}, x ∈ S.

(1.4)

f (x) = inf

y≥x {u(x, y) + v(x, y)[

Z _+∞

y

p(s − y)q(s)ds

+ f (0) Z _+∞

y

q(s)ds + Z _y

0

f (y − s)q(s)ds]}.

Inspired and motivated by the work in [1]-[12], in this paper, we prove the existence, uniqueness and iterative approximation of solutions for the functional equations (1.4)-(1.6):

(1.5) f (x) = opt _y∈D {u(x, y) + f (T (x, y))}, x ∈ S,

(1.6) f (x) = opt y∈D max{u(x, y), f (T (x, y))}, x ∈ S,

where the opt denotes the sup or inf. The results presented in this paper extend, improve and unify the corresponding results of Bellman [2, 3], Bhakta-Choudhury [6], Bhakta-Mitra [7], and Liu [12].

Throughout this paper, N denotes the set of all positive integers, R = (−∞, +∞) and R ⁺ = [0, +∞). Define

Φ ₁ = {ϕ : ϕ : R ⁺ → R ⁺ is nondecreasing}, Φ ₂ = {ϕ : ϕ ∈ Φ ₁ and lim

n→∞ ϕ ⁿ (t) = 0 for t > 0}, Φ 3 = {ϕ : ϕ ∈ Φ 1 , ϕ(0) = 0 and ϕ is right continuous at 0}.

Remark 1.1. It is easy to see that ϕ ∈ Φ ₂ implies ϕ(t) < t for any

t > 0.

Let us recall the following concept. Let X be a nonempty set and let {d _n } _n∈N be a countable family of pseudometrics on X such that for any distinct x, y ∈ X, d _k (x, y) 6= 0 for some k ∈ N . Define

d(x, y) = X ∞ k=1

2 ^−k d _k (x, y)

1 + d k (x, y) for all x, y ∈ X.

It is clear that d is a metric on X. A sequence {x n } n∈N in X converges to a point x ∈ X if and only if d _k (x _n , x) → 0 as n → ∞ and {x _n } _n∈N is a Cauchy sequence if and only if d k (x n , x m ) → 0 as n, m → ∞ for each k ∈ N .

Lemma 1.1. ([12]) Let a, b, c be in R. Then

|opt {a, c} − opt {b, c}| ≤ |a − b|.

2. Existence and uniqueness theorems

Let (X, k · k) and (Y, k · k ⁰ ) be real Banach spaces, S ⊆ X be the state space, and D ⊆ Y be the decision space. Denote by BB(S) the set of all real-valued mappings on S that are bounded on bounded subsets of S. It is easy to verify that BB(S) is a linear space over R under usual definitions of addition and multiplication by scalars. For any k ∈ N and a, b ∈ BB(S), let

d _k (a, b) = sup{|a(x) − b(x)| : x ∈ B(0, k)}, d(a, b) =

X ∞ k=1

2 ^−k d _k (a, b) 1 + d k (a, b) ,

where B(0, k) = {x : x ∈ S and kxk ≤ k}. Clearly, {d k } k∈N is a count- able family of pseudometrics on BB(S) and (BB(S), d) is a complete metric space.

Theorem 2.1. Let u : S × D → R, T : S × D → S be mappings and

(2.1)

a ₀ (x) = sup

y∈D

u(x, y), a n (x) = sup

y∈D

{u(x, y) + a n−1 (T (x, y))}, x ∈ S, n ∈ N.

If there exist ϕ ∈ Φ 2 and ψ ∈ Φ 1 such that

(2.2) kT (x, y)k ≤ ϕ(kxk) for all (x, y) ∈ S × D,

(2.3) |u(x, y)| ≤ ψ(kxk) for all (x, y) ∈ S × D, and

(2.4)

X ∞ n=0

ψ(ϕ ⁿ (t)) < ∞ for all t > 0,

then the functional equation (1.2) possesses a solution w ∈ BB(S) such that

(2.5) lim

n→∞ w(x n ) = 0 for any x 0 ∈ S,

{y _n } _n∈N ⊆ D, x _n = T (x _n−1 , y _n ), n ∈ N.

Moreover, the solution w of the functional equation (1.2) is also unique with respect to (2.5).

Proof. Put

H(x, y, a) = u(x, y) + a(T (x, y)) for all (x, y, a) ∈ S × D × BB(S), f a(x) = sup

y∈D H(x, y, a) for all (x, a) ∈ S × BB(S).

For any k ∈ N , y ∈ D and x ∈ B(0, k), by (2.2), (2.3), and Remark 1.1, we have

(2.6) |u(x, y)| ≤ ψ(kxk) ≤ ψ(k), kT (x, y)k ≤ ϕ(kxk) ≤ ϕ(k).

Using (2.6) and the definition of f , we infer that f a ∈ BB(S) for any a ∈ BB(S). That is, f maps BB(S) into BB(S).

Now we prove that f is a nonexpansive mapping in BB(S). For any a, b ∈ BB(S), ε > 0, k ∈ N and x ∈ B(0, k), there exist y, z ∈ D such that

(2.7) f a(x) − ε < H(x, y, a), f b(x) − ε < H(x, z, b),

f a(x) ≥ H(x, z, a), f b(x) ≥ H(x, y, b).

It follows from (2.7) that

|f a(x) − f b(x)|

< max{|H(x, z, a) − H(x, z, b)|, |H(x, y, a) − H(x, y, b)|} + ε

= max{|a(T (x, z) − b(T (x, z))|, |a(T (x, y)) − b(T (x, y))|} + ε

≤ d k (a, b) + ε,

which implies that d k (f a, f b) ≤ d k (a, b) + ε. Letting ε → 0, we have d _k (f a, f b) ≤ d _k (a, b) for all a, b ∈ BB(S), k ∈ N,

which yields that

d(f a, f b) = X ∞ k=1

2 ^−k d k (f a, f b) 1 + d _k (f a, f b) ≤

X ∞ k=1

2 ^−k d k (a, b)

1 + d _k (a, b) = d(a, b).

That is,

(2.8) d(f a, f b) ≤ d(a, b) for all a, b ∈ BB(S).

We claim that for any n ≥ 0,

(2.9) |a _n (x)| ≤ X n

i=0

ψ(ϕ ⁱ (kxk)) for all x ∈ S.

In fact, by (2.3) we conclude that

−ψ(kxk) ≤ u(x, y) ≤ ψ(kxk) for all (x, y) ∈ S × D, which means that

|a 0 (x)| = | sup

y∈D u(x, y)| ≤ ψ(kxk) for all x ∈ S.

Assume that (2.9) holds for some n ≥ 0. It follows from (2.2) that

(2.10) |a _n (T (x, y))| ≤ X n i=0

ψ(ϕ ⁱ (kT (x, y)k)) ≤ X n i=0

ψ(ϕ ⁱ⁺¹ (kxk))

for all (x, y) ∈ S × D. From (2.3) and (2.10) we know that

−

n+1 X

i=0

ψ(ϕ ⁱ (kxk)) ≤ u(x, y) + a _n (T (x, y))

≤

n+1 X

i=0

ψ(ϕ ⁱ (kxk)) for all (x, y) ∈ S × D.

This yields that

|a _n+1 (x)| = | sup

y∈D

{u(x, y) + a _n (T (x, y))}|

≤

n+1 X

i=0

ψ(ϕ ⁱ (kxk)) for all x ∈ S.

That is, (2.9) holds for all n ≥ 0.

Next we prove that {a n } n≥0 is a Cauchy sequence in BB(S). Let k ∈ N , ε > 0 and x 0 ∈ B(0, k) be given. (2.4) ensures that there exists some m ∈ N such that

(2.11)

n+p X

i=n

ψ(ϕ ⁱ (k)) < ε for all n ≥ m and p ∈ N.

For any n ≥ m and p ∈ N , by (2.1) we know that there exist v ₁ , w ₁ ∈ D and y 1 = T (x 0 , v 1 ), z 1 = T (x 0 , w 1 ) satisfying

(2.12)

a _n+p (x ₀ ) < H(x ₀ , v ₁ , a _n+p−1 ) + 2 ⁻¹ ε, a _n (x ₀ ) ≥ H(x ₀ , v ₁ , a _n−1 ), a _n (x ₀ ) < H(x ₀ , w ₁ , a _n−1 ) + 2 ⁻¹ ε, a _n+p (x ₀ ) ≥ H(x ₀ , w ₁ , a _n+p−1 ).

From (2.12) we have (2.13)

|a n+p (x 0 ) − a n (x 0 )|

< max{|H(x ₀ , v ₁ , a _n+p−1 ) − H(x ₀ , v ₁ , a _n−1 )|,

|H(x ₀ , w ₁ , a _n+p−1 ) − H(x ₀ , w ₁ , a _n−1 )|} + 2 ⁻¹ ε

= max{|a n−1 (y 1 ) − a n+p−1 (y 1 )|, |a n−1 (z 1 ) − a n+p−1 (z 1 )|} + 2 ⁻¹ ε

= |a _n−1 (x ₁ ) − a _n+p−1 (x ₁ )| + 2 ⁻¹ ε,

where x 1 = y 1 or z 1 and

|a _n−1 (x ₁ ) − a _n+p−1 (x ₁ )|

= max{|a n−1 (y 1 ) − a n+p−1 (y 1 )|, |a n−1 (z 1 ) − a n+p−1 (z 1 )|}.

Similarly, we conclude that there exist v _i , w _i ∈ D, y _i = T (x _i−1 , v _i ), z i = T (x i−1 , w i ), x i = y i or z i for 2 ≤ i ≤ n satisfying

(2.14)

|a _n+p−1 (x ₁ ) − a _n−1 (x ₁ )| < |a _n+p−2 (x ₂ ) − a _n−2 (x ₂ )| + 2 ⁻² ε,

|a _n+p−2 (x ₂ ) − a _n−2 (x ₂ )| < |a _n+p−3 (x ₃ ) − a _n−3 (x ₃ )| + 2 ⁻³ ε, .. .

|a _p+1 (x _n−1 ) − a ₁ (x _n−1 )| < |a _p (x _n ) − a ₀ (x _n )| + 2 ⁻ⁿ ε.

It follows from ϕ ∈ Φ ₂ , (2.2) and Remark 1.1 that (2.15)

kx n k ≤ ϕ(kx n−1 k) ≤ ϕ ² (kx n−2 k) ≤ · · · ≤ ϕ ⁿ (kx 0 k) ≤ kx 0 k ≤ k for any n ∈ N. In the light of (2.9), (2.11), and (2.13)-(2.15), we obtain that

(2.16)

|a _n+p (x ₀ ) − a _n (x ₀ )| < |a _p (x _n ) − a ₀ (x _n )| + ε,

≤ |a p (x n )| + |a 0 (x n )| + ε

≤ ψ(kx _n k) + X p i=0

ψ(ϕ ⁱ (kx _n k)) + ε

≤ ψ(ϕ ⁿ (kx 0 k)) + X p

i=0

ψ(ϕ ⁱ⁺ⁿ (kx 0 k)) + ε

≤ 2

n+p X

i=n

ψ(ϕ ⁱ (kkk)) + ε

< 3ε

for any n ≥ m and p ∈ N . Thus (2.15) and (2.16) yield that d _k (a _n , a _n+p )

≤ 3ε. That is, {a _n } _n≥0 is a Cauchy sequence in (BB(S), d) and hence it converges to some w ∈ BB(S). By virtue of (2.8), we get that

d(f w, w) ≤ d(f w, f a _n ) + d(a _n+1 , w) ≤ d(w, a _n ) + d(a _n+1 , w) → 0

as n → ∞. That is, w = f w is a fixed point of f and hence the functional equation (1.2) possesses a solution w ∈ BB(S).

We prove that (2.5) holds. For any x ₀ ∈ S, {y _n } _n∈N ⊆ D, x _n = T (x n−1 , y n ), n ∈ N , we have by (2.2)

(2.17)

kx n k = kT (x n−1 , y n )k ≤ ϕ(kx n−1 k) ≤ · · · ≤ ϕ ⁿ (kx 0 k) → 0, as n → ∞.

Put k = [kx ₀ k] + 1, where [t] denotes the largest integer not exceeding t.

From Remark 1.1 and (2.17) we conclude that {x _n } _n≥0 ⊆ B(0, k). Let k be in N . Note that lim _m→∞ d _k (w, a _m ) = 0. For given ε > 0, by (2.4) and (2.17) we know that there exists some m ∈ N such that

(2.18) max n

d _k (w, a _m ),

m+n X

i=n

ψ(ϕ ⁱ (kx ₀ k)) o

< ε for any n ≥ m.

By virtue of (2.9) and (2.18), we infer that

|w(x n )| ≤ |w(x n ) − a m (x n )| + |a m (x n )|

≤ d k (w, a m ) + X m i=0

ψ(ϕ ⁱ (kx n k))

≤ d _k (w, a _m ) +

m+n X

i=n

ψ(ϕ ⁱ (kx ₀ k))

< 2ε

for all n ≥ m. Therefore lim _m→∞ w(x _n ) = 0.

Finally we prove that w is a unique solution of the functional equation (1.2) in BB(S) satisfying (2.5). Suppose that v is also a solution of the functional equation (1.2) in BB(S) satisfying (2.5). Let x ₀ = t ₀ ∈ S and ε > 0 be given. By the definition of w and v, we conclude that there exist {y n } n≥1 ⊆ D, {z n } n≥1 ⊆ D, {x n } n≥1 ⊆ S and {t n } n≥1 ⊆ S with x _n = T (x _n−1 , y _n ), t _n = T (t _n−1 , z _n ) for all n ∈ N , such that

(2.19)

w(x _i ) <u(x _i , y _i+1 ) + w(x _i+1 ) + 2 ⁻ⁱ⁻¹ ε, v(t i ) <u(t i , z i+1 ) + v(t i+1 ) + 2 ⁻ⁱ⁻¹ ε,

w(t _i ) ≥u(t _i , z _i+1 ) + w(t _i+1 ), v(x _i ) ≥ u(x _i , y _i+1 ) + v(x _i+1 )

for all i ≥ 0. By (2.19) we easily deduce that

(2.20)

w(x ₀ ) < u(x ₀ , y ₁ ) + u(x ₁ , y ₂ ) + · · · + u(x _n−1 , y _n ) + w(x _n ) + (1 − 2 ⁻ⁿ )ε,

v(t 0 ) < u(t 0 , z 1 ) + u(t 1 , z 2 ) + · · · + u(t n−1 , z n ) + v(t n ) + (1 − 2 ⁻ⁿ )ε,

w(t ₀ ) ≥ u(t ₀ , z ₁ ) + u(t ₁ , z ₂ ) + · · · + u(t _n−1 , z _n ) + w(t _n ), v(x ₀ ) ≥ u(x ₀ , y ₁ ) + u(x ₁ , y ₂ ) + · · · + u(x _n−1 , y _n ) + v(x _n ) for any n ∈ N . Using (2.20) and x ₀ = t ₀ , we have

|w(x 0 ) − v(x 0 )| < |w(x n ) − v(x n )| + |w(t n ) − v(t n )| + (1 − 2 ⁻ⁿ )ε.

Letting n → ∞ in the above inequality, we obtain that |w(x ₀ )−v(x ₀ )| ≤ ε, which implies that w(x 0 ) = v(x 0 ) by letting ε → 0. This completes

the proof. ¤

Remark 2.1. Theorem 2.4 in [7] is a special case of Theorem 2.1 with ψ(t) = M t for all t ∈ R ⁺ , where M is a positive constant. The following example reveals that Theorem 2.1 generalizes properly Theorem 2.4 in [7].

Example 2.1. Let X = Y = R, S = D = R ⁺ . Define u : S ×D → R, T : S × D → S by

u(x, y) = x ² (1 − xy)

1 + xy , T (x, y) = x sin ² (x + y)

2 + y ² for all (x, y) ∈ S × D.

Choose ϕ(t) = 2 ⁻¹ t and ψ(t) = t ² for all t ∈ R ⁺ . It is easy to verify that the conditions of Theorem 2.1 are satisfied. Hence the functional equation (1.2) possesses a solution in BB(S). But Theorem 2.4 in [7] is not applicable since

|u(x, y)| = |u(M + 1, 0)| = (M + 1) ² > M |x|

for any M > 0 with (x, y) = (M + 1, 0) ∈ S × D.

A proof similar to that of Theorem 2.1 gives the following result and

is thus omitted.

Theorem 2.2. Let u : S × D → R, T : S × D → S be mappings and

(2.21)

a ₀ (x) = inf

y∈D u(x, y), a _n (x)

= inf

y∈D {u(x, y) + a _n−1 (T (x, y))}, x ∈ S, n ∈ N.

Suppose that there exist ϕ ∈ Φ 2 and ψ ∈ Φ 1 satisfying (2.2)-(2.4). Then the functional equation

(2.22) f (x) = inf

y∈D {u(x, y) + f (T (x, y))}, x ∈ S,

possesses a solution w ∈ BB(S) such that (2.5) holds. Moreover, the solution w of the functional equation (2.22) is also unique with respect to (2.5).

Theorem 2.3. Let u : S × D → R, T : S × D → S be mappings and

(2.23)

a 0 (x) = sup

y∈D

u(x, y), a n (x)

= sup

y∈D

max{u(x, y), a _n−1 (T (x, y))}, x ∈ S, n ∈ N.

Suppose that there exist ϕ ∈ Φ 2 and ψ ∈ Φ 3 satisfying (2.2) and (2.3).

Then the functional equation (2.24) f (x) = sup

y∈D

max{u(x, y), f (T (x, y))}, x ∈ S, possesses a solution w ∈ BB(S) such that (2.5) holds and (2.25) w(x) ≥ 0 for all x ∈ S.

Moreover, the solution w of the functional equation (2.24) is also unique with respect to (2.5).

Proof. Set

H(x, y, a) = max{u(x, y), a(T (x, y))} for all (x, y, a) ∈ S × D × BB(S), f a(x) = sup

y∈D

H(x, y, a) for all (x, a) ∈ S × BB(S).

As in the proof of Theorem 2.1, we can conclude that f maps BB(S) into BB(S) and (2.8) holds. Now we claim that for all n ≥ 0,

(2.26) |a _n (x)| ≤ ψ(kxk) for all x ∈ S.

It is easy to verify that (2.3) implies that (2.26) holds for n = 0. Suppose that (2.26) holds for some n ≥ 0. From (2.2), ϕ ∈ Φ ₂ and Remark 1.1, we infer that

|a _n (T (x, y))| ≤ ψ(kT (x, y)k)

≤ ψ(ϕ(kxk)) ≤ ψ(kxk) for all (x, y) ∈ S × D.

(2.27)

Using (2.3) and (2.27), we have

−ψ(kxk) ≤ max{u(x, y), a _n (T (x, y))} ≤ ψ(kxk) for all (x, y) ∈ S × D, which implies that

|a n+1 (x)| = | sup

y∈D

max{u(x, y), a n (T (x, y))} ≤ ψ(kxk) for all x ∈ S.

Hence (2.26) holds for all n ≥ 0. On the other hand, (2.23) ensures that (2.28) a 0 (x) ≤ a 1 (x) ≤ · · · ≤ a n (x) ≤ a n+1 (x) ≤ · · · for all x ∈ S.

Next we show that {a _n } _n≥0 is a Cauchy sequence in BB(S). Let k ∈ N , ε > 0 and x 0 ∈ B(0, k) be given. Since ϕ ∈ Φ 2 and ψ ∈ Φ 3 , it follows that there exists some m ∈ N such that

(2.29) ψ(ϕ ⁿ (k)) < ε for all n ≥ m.

For any n ≥ m and p ∈ N , by (2.23) we easily conclude that there exist y ₁ ∈ D and x ₁ = T (x ₀ , y ₁ ) satisfying

(2.30) a _n+p (x ₀ ) < H(x ₀ , y ₁ , a _n+p−1 )+2 ⁻¹ ε, a _n (x ₀ ) ≥ H(x ₀ , y ₁ , a _n−1 ).

By virtue of (2.28), (2.30), and Lemma 1.1, we have (2.31)

0 ≤ a _n+p (x ₀ ) − a _n (x ₀ )

< H(x ₀ , y ₁ , a _n+p−1 ) − H(x ₀ , y ₁ , a _n−1 ) + 2 ⁻¹ ε

= max{u(x 0 , y 1 ), a n+p−1 (x 1 )} − max{u(x 0 , y 1 ), a n−1 (x 1 )} + 2 ⁻¹ ε

≤ a _n+p−1 (x ₁ ) − a _n−1 (x ₁ ) + 2 ⁻¹ ε.

Similarly, we conclude that there exist y i ∈ D, x i = T (x i−1 , y i ) ∈ S, 2 ≤ i ≤ n satisfying

(2.32)

0 ≤ a _n+p−1 (x ₁ ) − a _n−1 (x ₁ ) < a _n+p−2 (x ₂ ) − a _n−2 (x ₂ ) + 2 ⁻² ε, 0 ≤ a n+p−2 (x 2 ) − a n−2 (x 2 ) < a n+p−3 (x 3 ) − a n−3 (x 3 ) + 2 ⁻³ ε,

.. .

0 ≤ a _p+1 (x _n−1 ) − a ₁ (x _n−1 ) < a _p (x _n ) − a ₀ (x _n ) + 2 ⁻ⁿ ε.

It follows from (2.2), (2.3), (2.26), (2.29), (2.31), and (2.32) that 0 ≤ a _n+p (x ₀ ) − a _n (x ₀ ) < a _p (x _n ) − a ₀ (x _n ) + ε

≤ |a p (x n )| + |a 0 (x n )| + ε ≤ 2ψ(kx n k) + ε

= 2ψ(kT (x _n−1 , y _n )k) + ε ≤ 2ψ(ϕ(kx _n−1 k)) + ε

≤ 2ψ(ϕ ⁿ (kx ₀ k)) + ε ≤ 2ψ(ϕ ⁿ (k)) + ε < 3ε

for any n ≥ m and p ∈ N . This gives that d _k (a _n , a _n+p ) ≤ 3ε for any n ≥ m and p ∈ N . Consequently, {a n } n≥0 is a Cauchy sequence in (BB(S), d) and it converges to some w ∈ BB(S). From (2.8), we deduce that w = f w. That is, the functional equation (2.24) possesses a solution w ∈ BB(S).

We prove that (2.5) holds. For any x ₀ ∈ S, {y _n } _n∈N ⊆ D, x _n = T (x _n−1 , y _n ), n ∈ N , (2.2) yields that (2.17) holds. Note that ψ(0) = 0 and ψ is right continuous at 0. Thus (2.17) means that

(2.33) lim

n→∞ ψ(kx _n k) = ψ(0) = 0.

Put k = [kx ₀ k] + 1. It is easy to verify that {x _n } _n∈0 ⊆ B(0, k). Let k be in N and ε > 0. Since {a _n } _n∈N converges to w, by (2.33) we know that there exists some m ∈ N such that

(2.34) max{d _k (w, a _m ), ψ(kx _n k)} < ε for any n ≥ m.

By virtue of (2.26) and (2.34), we have

|w(x _n )| ≤ |w(x _n ) − a _m (x _n )| + |a _m (x _n )| ≤ d _k (w, a _m ) + ψ(kx _n k) < 2ε

for all n ≥ m. That is, lim _n→∞ w(x _n ) = 0.

Given x 0 ∈ S and {y n } n∈N ⊂ D, take x n = T (x n−1 , y n ) for all n ∈ N . Since w is a solution of the functional equation (2.24), by (2.5) we immediately infer that

w(x ₀ ) ≥ max{u(x ₀ , y ₁ ), w(T (x ₀ , y ₁ ))} ≥ w(x ₁ ) ≥ · · · ≥ w(x _n ) → 0 as n → ∞. That is, w(x ₀ ) ≥ 0 for all x ₀ ∈ S.

Finally we prove that w is a unique solution of the functional equation (2.24) in BB(S) satisfying (2.5). Suppose that v is also a solution of the functional equation (2.24) in BB(S) satisfying (2.5). Let x 0 = t 0 ∈ S and ε > 0 be given. By the definition of w and v, we conclude that there exist {y _n } _n≥1 ⊆ D, {z _n } _n≥1 ⊆ D, {x _n } _n≥1 ⊆ S and {t _n } _n≥1 ⊆ S with x n = T (x n−1 , y n ), t n = T (t n−1 , z n ) for all n ∈ N , such that

(2.35)

w(x _i ) < max{u(x _i , y _i+1 ), w(x _i+1 )} + 2 ⁻ⁱ⁻¹ ε, v(t i ) < max{u(t i , z i+1 ), v(t i+1 )} + 2 ⁻ⁱ⁻¹ ε,

w(t _i ) ≥ max{u(t _i , z _i+1 ), w(t _i+1 )}, v(x _i ) ≥ max{u(x _i , y _i+1 ), v(x _i+1 )}

for all i ≥ 0. By (2.35) we easily deduce that (2.36)

w(x ₀ ) < max{u(x ₀ , y ₁ ), u(x ₁ , y ₂ ), · · · , u(x _n−1 , y _n ), w(x _n )}+ (1 − 2 ⁻ⁿ )ε, v(t ₀ ) < max{u(t ₀ , z ₁ ), u(t ₁ , z ₂ ), · · · , u(t _n−1 , z _n ), v(t _n )} + (1 − 2 ⁻ⁿ )ε, w(t 0 ) ≥ max{u(t 0 , z 1 ), u(t 1 , z 2 ), · · · , u(t n−1 , z n ), w(t n )},

v(x ₀ ) ≥ max{u(x ₀ , y ₁ ), u(x ₁ , y ₂ ), · · · u(x _n−1 , y _n ), v(x _n )}

for any n ∈ N . Using (2.36), Lemma 1.1 and x ₀ = t ₀ , we have

|w(x ₀ ) − v(x ₀ )| < |w(x _n ) − v(x _n )| + |w(t _n ) − v(t _n )| + (1 − 2 ⁻ⁿ )ε.

Letting n → ∞ in the above inequality, we obtain that |w(x ₀ )−v(x ₀ )| ≤ ε, which implies that w(x ₀ ) = v(x ₀ ) by letting ε → 0. This completes

the proof. ¤

Following a similar argument as in the proof of Theorem 2.3, we have

the following.

Theorem 2.4. Let u : S × D → R, T : S × D → S be mappings and

a ₀ (x) = inf

y∈D u(x, y), a _n (x)

= inf

y∈D max{u(x, y), a _n−1 (T (x, y))}, x ∈ S, n ∈ N.

(2.37)

Suppose that there exist ϕ ∈ Φ ₂ and ψ ∈ Φ ₃ satisfying (2.2) and (2.3).

Then the functional equation (2.38) f (x) = inf

y∈D max{u(x, y), f (T (x, y))}, x ∈ S,

possesses a solution w ∈ BB(S) such that (2.5) and (2.25) hold. More- over, the solution w of the functional equation (2.38) is also unique with respect to (2.5).

Remark 2.2. Theorem 2.4 extends, improves and unifies Theorem 3.5 of Bhakta and Choudhury [6], Theorem 3.5 of Liu [12] and a result of Bullman [2, p.135]. The example below shows that Theorem 2.4 is indeed a generalization of the results due to Bhakta and Choudhury [6], Liu [12], and Bullman [2].

Example 2.2. Let X, Y, S, D be as in Example 2.1. Define u : S × D → R, T : S × D → S by

u(x, y) = x ⁴ (1 + xy)

1 + x ² + y ² , T (x, y) = x| sin(x + y)|

1 + x for all (x, y) ∈ S × D.

Put ϕ(t) = _1+t ^t , ψ(t) = t ⁴ for all t ∈ R ⁺ . Then the assumptions of Theorem 2.4 are fulfilled. However, we cannot invoke the results of Bhakta and Choudhury [6], Liu [12], and Bullman [2] to establish that the functional equation (2.38) possesses a solution in BB(S) because

|u(x, y)| =

¯ ¯

¯u ³ 3

2 (M + 1), 3

2 (M + 1)

´¯ ¯

¯ ≥ 2 3

h 3

2 (M + 1) i ₂

> M |x|

for any M > 0 with (x, y) =

³ 3

2 (M + 1), ³ ₂ (M + 1)

´

∈ S × D.

Let BC(R ⁺ ) denote the set of all bounded continuous real-valued

functions on R ⁺ . Put d(a, b) = sup{|a(x) − b(x)| : x ∈ R ⁺ } for all

a, b ∈ BC(R ⁺ ). It is easily seen that (BC(R ⁺ ), d) is a complete metric

space.

Theorem 2.5. Let X = Y = R, S = D = R ⁺ . Let u, v : S × D → R ⁺ be continuous, u(x, x) be bounded on S, lim _y→+∞ u(x, y) = +∞, u(x, ·) and v(x, ·) be nondecreasing with respect to the second argument on [x, +∞) for every x ∈ S, and

(2.39) 0 ≤ v(x, y) ≤ r for all (x, y) ∈ S × D,

where r is a positive constant. Let p, q : S → R ⁺ satisfy that p is continuous, nondecreasing, R _+∞

0 p(s)q(s)ds < +∞ and (2.40)

Z _+∞

0

q(s)ds = t > 0.

Assume that

a ₀ (x) = inf

y≥x u(x, y), x ∈ S, (2.41)

a n+1 (x) = inf

y≥x

n

u(x, y) + v(x, y) h Z +∞

y

p(s − y)q(s)ds

+ a n (0) Z _+∞

y

q(s)ds + Z _y

0

a n (y − s)q(s)ds io

, x ∈ S, n ≥ 0.

If rt < 1, then the functional equation (1.4) possesses a unique solution w ∈ BC(R ⁺ ) and

(2.42) d(a n+1 , w) ≤ (rt) ⁿ⁺¹ (1 − rt) ⁻¹ d(a 0 , a 1 ) for all n ≥ 0.

Proof. For all (x, y, b) ∈ S × D × BC(R ⁺ ), set

H(x, y, b) = u(x, y) + v(x, y) h Z +∞

y

p(s − y)q(s)ds

+ b(0) Z _+∞

y

q(s)ds + Z _y

0

b(y − s)q(s)ds i

.

Let

(2.43) f b(x) = inf

y≥x H(x, y, b) for all (x, b) ∈ S × BC(R ⁺ ).

It is easy to see that f maps BC(R ⁺ ) into itself. Let ε > 0, x ∈ S and b, c ∈ BC(R ⁺ ) be given. It follows from (2.43) that there exist y ₁ ≥ x and y ₂ ≥ x such that

(2.44) f b(x) > H(x, y 1 , b) − ε, f c(x) > H(x, y 2 , c) − ε, f b(x) ≤ H(x, y ₂ , b), f c(x) ≤ H(x, y ₁ , c).

By virtue of (2.39), (2.40), and (2.44), we deduced that

|f b(x) − f c(x)|

< max n

|H(x, y _i , b) − H(x, y _i , c)| : i = 1, 2 o

+ ε

≤ max n

v(x, y i ) h

|b(0) − c(0)|

Z _+∞

y

q(s)ds +

Z _y

0

|b(y i − s) − c(y i − s)|q(s)ds i

: i = 1, 2 o

+ ε

≤ max n

rd(b, c)

h Z +∞

y

q(s)ds + Z _y

0

q(s)ds i

: i = 1, 2 o

+ ε

= rtd(b, c) + ε, which implies that

d(f b, f c) = sup{|f b(x) − f c(x)| : x ∈ S} ≤ rtd(b, c) + ε.

Letting ε → 0, we easily conclude that

d(f b, f c) ≤ rtd(b, c) for all b, c ∈ BC(R ⁺ ).

It follows from Banach fixed-point theorem that f has a unique fixed point w ∈ BC(R ⁺ ) and (2.42) holds. Obviously, w is a unique solution of the functional equation (1.4). This completes the proof. ¤ Remark 2.3. Theorem 2.5 generalizes Theorem 3.6 of Bhakta and Choudhury [6] and a result of Bellman [2, p.129].

Problem 2.1. If rt < 1 is replaced by rt = 1 in Theorem 2.5, does the functional equation (1.4) possess a solution in BC(R ⁺ )?

Problem 2.2. If the answer to Problem 2.1 is no, then what addi-

tional hypotheses on u, v, p, q are needed to guarantee the existence of a

solution of the functional equation (1.4)?

References

[1] R. Baskaran and P. V. Subrahmanyam, A note on the solution of a class of functional equations, Appl. Anal. 22 (1986), no. 3-4, 235–241.

[2] R. Bellman, Dynamic programming, Princeton University Press, Princeton, N.

J., 1957.

[3] , Methods of Non-linear analysis, Vol. II, Mathematics in Science and Engineering, Vol. 61-II, Academic Press, New York-London, 1973.

[4] R. Bellman and E. S. Lee, Functional equations in dynamic programming, Ae- quationes Math. 17 (1978), no. 1, 1–18.

[5] R. Bellman and M. Roosta, A technique for the reduction of dimensionality in dynamic programming, J. Math. Anal. Appl. 88 (1982), no. 2, 543–546.

[6] P. C. Bhakta and S. R. Choudhury, Some existence theorems for functional equations arising in dynamic programming II, J. Math. Anal. Appl. 131 (1988), no. 1, 217–231.

[7] P. C. Bhakta and S. Mitra, Some existence theorems for functional equations arising in dynamic programming, J. Math. Anal. Appl. 98 (1984), no. 2, 348–

362.

[8] S. S. Chang, Some existence theorems of common and coincidence solutions for a class of functional equations arising in dynamic programming, Appl. Math.

Mech.(English Ed.) 12 (1991), no. 1, 33–39.

[9] S. S. Chang and Y. H. Ma, Coupled fixed points for mixed monotone condensing operators and an existence theorem of the solutions for a class of functional equations arising in dynamic programming, J. Math. Anal. Appl. 160 (1991), no. 2, 468–479.

[10] Z. Liu, Coincidence theorems for expansive mappings with applications to the solutions of functional equations arising in dynamic programming, Acta Sci.

Math. (Szeged) 65 (1999), no. 1-2, 359–369.

[11] , Compatible mappings and fixed points, Acta Sci. Math. (Szeged) 65 (1999), no. 1-2, 371–383.

[12] , Existence theorems of solutions for certain classes of functional equa- tions arising in dynamic programming, J. Math. Anal. Appl. 262 (2001), no. 2, 529–553.

Zeqing Liu

Department of Mathematics Liaoning Normal University

Dalian, Liaoning, 116029, P. R. China E-mail: [email protected]

Jeong Sheok Ume

Department of Applied Mathematics

Changwon National University

Changwon 641-773, Korea

E-mail: [email protected]

Shin Min Kang

Department of Mathematics

and Research Institute of Natural Science Gyeongsang National University

Chinju 660-701, Korea

E-mail: [email protected]