Solvability and Algorithms for Functional Equations Originating from Dynamic Programming

Abstract

The main purpose of this paper is to study the functional equation arising in dynamic programming of multistage decision processes f(x)=[subscript]opty∈D[/subscript] opt{p(x,y),q(x,y)f(a(x,y)),r(x,y)f(b(x,y)) , s(x,y)f(c(x,y))} for all x∈S . A few iterative algorithms for solving the functional equation are suggested. The existence, uniqueness and iterative approximations of solutions for the functional equation are discussed in the Banach spaces BC(S) and B(S) and the complete metric space BB(S) , respectively. The properties of solutions, nonnegative solutions, and nonpositive solutions and the convergence of iterative algorithms for the functional equation and other functional equations, which are special cases of the above functional equation, are investigated in the complete metric space BB(S) , respectively. Eight nontrivial examples which dwell upon the importance of the results in this paper are also given.

(ProQuest: ... denotes non-US-ASCII text omitted.)

Guojing Jiang 1 and Shin Min Kang 2 and Young Chel Kwun 3

Recommended by Yeol J. Cho

1, Organization Department, Dalian Vocational Technical College, Dalian, Liaoning 116035, China
2, Department of Mathematics and RINS, Gyeongsang National University, Jinju 660-701, Republic of Korea
3, Department of Mathematics, Dong-A University, Pusan 614-714, Republic of Korea

Received 5 January 2011; Accepted 11 February 2011

1. Introduction

The existence, uniqueness, and iterative approximations of solutions for several classes of functional equations arising in dynamic programming were studied by a lot of researchers; see [1-23] and the references therein. Bellman [3], Bhakta and Choudhury [7], Liu [12], Liu and Kang [15], and Liu et al. [18] investigated the following functional equations: [figure omitted; refer to PDF] and gave some existence and uniqueness results and iterative approximations of solutions for the functional equations in BB(S) . Liu and Kang [14] and Liu and Ume [17] generalized the results in [3, 7, 12, 15, 18] and studied the properties of solutions, nonpositive solutions and nonnegative solutions and the convergence of iterative approximations for the following functional equations, respectively [figure omitted; refer to PDF] in BB(S) .

The purpose of this paper is to introduce and study the following functional equations arising in dynamic programming of multistage decision processes: [figure omitted; refer to PDF] [figure omitted; refer to PDF] [figure omitted; refer to PDF] [figure omitted; refer to PDF] [figure omitted; refer to PDF] [figure omitted; refer to PDF] [figure omitted; refer to PDF] where opt denotes sup or inf , x and y stand for the state and decision vectors, respectively, a,b , and c represent the transformations of the processes, and f(x) represents the optimal return function with initial x .

This paper is divided into four sections. In Section 2, we recall a few basic concepts and notations, establish several lemmas that will be needed further on, and suggest ten iterative algorithms for solving the functional equations (1.3)-(1.9). In Section 3, by applying the Banach fixed-point theorem, we establish the existence, uniqueness, and iterative approximations of solutions for the functional equation (1.3) in the Banach spaces BC(S) and B(S) , respectively. By means of two iterative algorithms defined in Section 2, we obtain the existence, uniqueness, and iterative approximations of solutions for the functional equation (1.3) in the complete metric space BB(S) . Under certain conditions, we investigate the behaviors of solutions, nonpositive solutions, and nonnegative solutions and the convergence of iterative algorithms for the functional equations (1.3)-(1.7), respectively, in BB(S) . In Section 4, we construct eight nontrivial examples to explain our results, which extend and improve substantially the results due to Bellman [3], Bhakta and Choudhury [7], Liu [12], Liu and Kang [14, 15], Liu and Ume [17], Liu et al. [18], and others.

2. Lemmas and Algorithms

Throughout this paper, we assume that ...=(-∞,+∞) , ^...+ =[0,+∞) , ^...- =(-∞,0] , ... denotes the set of positive integers, and, for each t∈... , [t] denotes the largest integer not exceeding t . Let (X,||·||) and (Y,^{||·||[variant prime]} ) be real Banach spaces, S⊆X the state space, and D⊆Y the decision space. Define [figure omitted; refer to PDF] Clearly (B(S),_||·||1 ) and (BC(S),_||·||1 ) are Banach spaces with norm _||f||1 =_{sup x∈S} |f(x)| .

For any k∈... and f,g∈BB(S) , let [figure omitted; refer to PDF] where B...(0,k)={x:x∈S and ||x||≤k} . It is easy to see that {_dk}k∈... is a countable family of pseudometrics on BB(S) . A sequence {_xn}n∈... in BB(S) is said to be converge to a point x∈BB(S) if, for any k∈..._dk (_xn ,x)[arrow right]0 as n[arrow right]∞ and to be a Cauchy sequence if, for any k∈... , _dk (_xn ,_xm )[arrow right]0 as n,m[arrow right]∞ . It is clear that (BB(S),d) is a complete metric space.

Lemma 2.1.

Let {_ai ,_bi :1≤i≤n}⊂... . Then

(a) opt{_ai :1≤i≤n}=opt{opt{_ai :1≤i≤n-1},_an } ,

(b) opt{_ai :1≤i≤n}≤opt{_bi :1≤i≤n} for _ai ≤_bi , 1≤i≤n ,

(c) max {_aibi :1≤i≤n}≤max {_ai :1≤i≤n}max {_bi :1≤i≤n} for {_ai ,_bi :1≤i≤n}⊂^...+ ,

(d) min {_aibi :1≤i≤n}≥min {_ai :1≤i≤n}min {_bi :1≤i≤n} for {_ai ,_bi :1≤i≤n}⊂^...+ ,

(e) |opt{_ai :1≤i≤n}-opt{_bi :1≤i≤n}|≤max {|_ai -_bi |:1≤i≤n} .

Proof.

Clearly (a)-(d) are true. Now we show (e). Note that (e) holds for n=1 . Suppose that (e) is true for some n∈... . It follows from (a) and Lemma 2.1 in [17] that [figure omitted; refer to PDF] Hence (e) holds for any n∈... . This completes the proof.

Lemma 2.2.

Let {_ai :1≤i≤n}⊂... and {_bi :1≤i≤n}⊂^...+ . Then

(a) max {_aibi :1≤i≤n}≥min {_ai :1≤i≤n}max {_bi :1≤i≤n} ,

(b) min {_aibi :1≤i≤n}≤max {_ai :1≤i≤n}min {_bi :1≤i≤n} .

Proof.

It is clear that (a) is true for n=1 . Suppose that (a) is also true for some n∈... . Using Lemma 2.3 in [19] and Lemma 2.1, we infer that [figure omitted; refer to PDF] That is, (a) is true for n+1 . Therefore (a) holds for any n∈... . Similarly we can prove (b). This completes the proof.

Lemma 2.3.

Let {_a1n}n∈... , {_a2n}n∈... ,...,{_akn}n∈... be convergent sequences in ... . Then [figure omitted; refer to PDF]

Proof.

Put _{lim n[arrow right]∞ain} =_bi for 1≤i≤k . In view of Lemma 2.1 we deduce that [figure omitted; refer to PDF] which yields that [figure omitted; refer to PDF] This completes the proof.

Lemma 2.4.

(a) Assume that A:S×D[arrow right]... is a mapping such that _opty∈D A(_x0 ,y) is bounded for some _x0 ∈S . Then [figure omitted; refer to PDF]

(b) Assume that A,B:S×D[arrow right]... are mappings such that _opty∈D A(_x1 ,y) and _opty∈D B(_x2 ,y) are bounded for some _x1 ,_x2 ∈S . Then [figure omitted; refer to PDF]

Proof.

Now we show (a). If _{sup y∈D} |A(_x0 ,y)|=+∞ , (a) holds clearly. Suppose that _{sup y∈D} |A(_x0 ,y)|<+∞ . Note that [figure omitted; refer to PDF] It follows that [figure omitted; refer to PDF] which implies that [figure omitted; refer to PDF]

Next we show (b). If _{sup y∈D} |A(_x1 ,y)-B(_x2 ,y)|=+∞ , (b) is true. Suppose that _{sup y∈D} |A(_x1 ,y)-B(_x2 ,y)|<+∞ . Note that [figure omitted; refer to PDF] which yields that [figure omitted; refer to PDF] It follows that [figure omitted; refer to PDF] which gives that [figure omitted; refer to PDF] This completes the proof.

Algorithm 1.

For any _f0 ∈BC(S) , compute {_fn}n≥0 by [figure omitted; refer to PDF] where [figure omitted; refer to PDF]

Algorithm 2.

For any _f0 ∈B(S) , compute {_fn}n≥0 by (2.17) and (2.18).

Algorithm 3.

For any _f0 ∈BB(S) , compute {_fn}n≥0 by (2.17) and (2.18).

Algorithm 4.

For any _w0 ∈BB(S) , compute {_wn}n≥0 by [figure omitted; refer to PDF]

Algorithm 5.

For any _w0 ∈BB(S) , compute {_wn}n≥0 by [figure omitted; refer to PDF]

Algorithm 6.

For any _w0 ∈BB(S) , compute {_wn}n≥0 by [figure omitted; refer to PDF]

Algorithm 7.

For any _w0 ∈BB(S) , compute {_wn}n≥0 by [figure omitted; refer to PDF]

Algorithm 8.

For any _w0 ∈BB(S) , compute {_wn}n≥0 by [figure omitted; refer to PDF]

Algorithm 9.

For any _w0 ∈BB(S) , compute {_wn}n≥0 by [figure omitted; refer to PDF]

Algorithm 10.

For any _w0 ∈BB(S) , compute {_wn}n≥0 by [figure omitted; refer to PDF]

3. The Properties of Solutions and Convergence of Algorithms

Now we prove the existence, uniqueness, and iterative approximations of solutions for the functional equation (1.3) in BC(S) and B(S) , respectively, by using the Banach fixed-point theorem.

Theorem 3.1.

Let S be compact. Let p,q,r,s:S×D[arrow right]... and a,b,c:S×D[arrow right]S satisfy the following conditions:

(C1) p is bounded in S×D ;

(C2) _{sup (x,y)∈S×D} max {|q(x,y)|,|r(x,y)|,|s(x,y)|}≤α for some constant α∈(0,1) ;

(C3) for each fixed _x0 ∈S , [figure omitted; refer to PDF] uniformly for y∈D , respectively.

Then the functional equation (1.3) possesses a unique solution f∈BC(S) , and the sequence {_fn}n≥0 generated by Algorithm 1 converges to f and has the error estimate [figure omitted; refer to PDF]

Proof.

Define a mapping H:BC(S)[arrow right]BC(S) by [figure omitted; refer to PDF] Let h∈BC(S) and _x0 ∈S and [straight epsilon]>0 . It follows from (C1), (C3), and the compactness of S that there exist constants M>0 , δ>0 , and _δ1 >0 satisfying [figure omitted; refer to PDF] [figure omitted; refer to PDF] [figure omitted; refer to PDF] [figure omitted; refer to PDF] [figure omitted; refer to PDF] [figure omitted; refer to PDF] Using (3.3)-(3.5), (C2), and Lemmas 2.1 and 2.4, we get that [figure omitted; refer to PDF] In light of (C2), (3.3), (3.5)-(3.9), and Lemmas 2.1 and 2.4, we deduce that for all (x,y)∈S×D with ||x-_x0 ||<δ [figure omitted; refer to PDF] Thus (3.10), (3.11), and (2.17) ensure that the mapping H:BC(S)[arrow right]BC(S) and Algorithm 1 are well defined.

Next we assert that the mapping H:BC(S)[arrow right]BC(S) is a contraction. Let [straight epsilon]>0 , x∈S , and g,h∈BC(S) . Suppose that _opty∈D =_{inf y∈D} . Choose u,v∈D such that [figure omitted; refer to PDF] Lemma 2.1 and (3.12) lead to [figure omitted; refer to PDF] which implies that [figure omitted; refer to PDF] Letting [straight epsilon][arrow right]⁰⁺ in the above inequality, we know that [figure omitted; refer to PDF] Similarly we conclude that (3.15) holds for _opty∈D =_{sup y∈D} . The Banach fixed-point theorem yields that the contraction mapping H has a unique fixed point f∈BC(S) . It is easy to verify that f is also a unique solution of the functional equation (1.3) in BC(S) . By means of (2.17), (2.18), (3.15), and [figure omitted; refer to PDF] we infer that [figure omitted; refer to PDF] which yields that [figure omitted; refer to PDF] and the sequence {_fn}n≥0 converges to f by (2.18). This completes the proof.

Dropping the compactness of S and (C3) in Theorem 3.1, we conclude immediately the following result.

Theorem 3.2.

Let p,q,r,s:S×D[arrow right]... and a,b,c:S×D[arrow right]S satisfy conditions (C1) and (C2). Then the functional equation (1.3) possesses a unique solution f∈B(S) and the sequence {_fn}n≥0 generated by Algorithm 2 converges to f and satisfies (3.2).

Next we prove the existence, uniqueness, and iterative approximations of solution for the functional equation (1.3) in BB(S) .

Theorem 3.3.

Let p,q,r,s:S×D[arrow right]... and a,b,c:S×D[arrow right]S satisfy condition (C2) and the following two conditions:

(C4) p is bounded on B...(0,k)×D for each k∈... ;

(C5) _{sup (x,y)∈B...(0,k)×D} {||a(x,y)||,||b(x,y)||,||c(x,y)||}≤k for all k∈... .

Then the functional equation (1.3) possesses a unique solution w∈BB(S) , and the sequences {_fn}n≥0 and {_wn}n≥0 generated by Algorithms 3 and 4, respectively, converge to f and have the error estimates [figure omitted; refer to PDF]

Proof.

Define a mapping H:BB(S)[arrow right]BB(S) by (3.3). Let k∈... and h∈BB(S) . Thus (C4) and (C5) guarantee that there exist M(k)>0 and G(k,h)>0 satisfying [figure omitted; refer to PDF] Using (3.3), (3.20), (C2), (C5), and Lemmas 2.1 and 2.4, we infer that [figure omitted; refer to PDF] which means that H is a self-mapping in BB(S) . Consequently, Algorithms 3 and 4 are well defined.

Now we claim that [figure omitted; refer to PDF] Let k∈... , x∈B...(0,k) , g,h∈BB(S) , and [straight epsilon]>0 . Suppose that _opty∈D =_{inf y∈D} . Select u,v∈D such that (3.12) holds. Thus (3.3), (3.12), (C2), (C5), and Lemma 2.1 ensure that [figure omitted; refer to PDF] which implies that [figure omitted; refer to PDF] Similarly we conclude that (3.24) holds for _opty∈D =_{sup y∈D} . As [straight epsilon][arrow right]⁰⁺ in (3.24), we get that (3.22) holds.

Let _w0 ∈BB(S) . It follows from Algorithm 4 that [figure omitted; refer to PDF] and (3.22) leads to [figure omitted; refer to PDF] which yields that {_wn}n≥0 is a Cauchy sequence in the complete metric space (BB(S),d) , and hence {_wn}n≥0 converges to some w∈BB(S) . In light of (3.22) and (C2), we know that [figure omitted; refer to PDF] That is, the mapping H is nonexpansive. It follows from (3.27) and Algorithm 4 that [figure omitted; refer to PDF] that is, w=Hw . Suppose that there exists u∈BB(S)\{w} with u=Hu . Consequently there exists some _k0 ∈... satisfying _dk0 (w,u)>0 . It follows from (3.22) and (C2) that [figure omitted; refer to PDF] which is a contradiction. Hence the mapping H:BB(S)[arrow right]BB(S) has a unique fixed point w∈BB(S) , which is a unique solution of the functional equation (1.3) in BB(S) . Letting m[arrow right]∞ in (3.26), we infer that [figure omitted; refer to PDF] It follows from Algorithm 3, (2.18), and (3.22) that [figure omitted; refer to PDF] which gives that _fn [arrow right]w as n[arrow right]∞ . This completes the proof.

Next we investigate the behaviors of solutions for the functional equations (1.3)-(1.5) and discuss the convergence of Algorithms 4-6 in BB(S) , respectively.

Theorem 3.4.

Let ([straight phi],ψ)∈_Φ2 , p,q,r,s:S×D[arrow right]... and a,b,c:S×D[arrow right]S satisfy the following conditions:

(C6) _{sup y∈D} |p(x,y)|≤ψ(||x||) for all x∈S ;

(C7) _{sup y∈D} max {||a(x,y)||,||b(x,y)||,||c(x,y)||}≤[straight phi](||x||) for all x∈S ;

(C8) _{sup (x,y)∈S×D} max {|q(x,y)|,|r(x,y)|,|s(x,y)|}≤1 .

Then the functional equation (1.3) possesses a solution w∈BB(S) satisfying conditions (C9)-(C12) below:

(C9) the sequence {_wn}n≥0 generated by Algorithm 4 converges to w , where _w0 ∈BB(S) with |_w0 (x)|≤ψ(||x||) for all (x,k)∈B...(0,k)×... ;

(C10): |w(x)|≤ψ(||x||) for all x∈S ;

(C11): _{lim n[arrow right]∞} w(_xn )=0 for any _x0 ∈S , {_yn}n∈... ⊂D and _xn ∈{a(_xn-1 ,_yn ) , b(_xn-1 ,_yn ) , c(_xn-1 ,_yn )} for all n∈... ;

(C12): w is unique relative to condition (C11).

Proof.

First of all we assert that [figure omitted; refer to PDF] Suppose that there exists some _t0 >0 with [straight phi](_t0 )≥_t0 . It follows from ([straight phi],ψ)∈_Φ2 that [figure omitted; refer to PDF] That is, [figure omitted; refer to PDF] which is impossible. That is, (3.32) holds. Let the mapping H be defined by (3.3) in BB(S) . Note that (C6) and (C7) imply (C4) and (C5) by (3.32) and ([straight phi],ψ)∈_Φ2 , respectively. As in the proof of Theorem 3.3, by (C8) we conclude that the mapping H maps BB(S) into BB(S) and satisfies [figure omitted; refer to PDF] [figure omitted; refer to PDF] That is, the mapping H is nonexpansive.

Let the sequence {_wn}n≥0 be generated by Algorithm 4 and _w0 ∈BB(S) with |_w0 (x)|≤ψ(||x||) for all (x,k)∈B...(0,k)×... . We now claim that for each n≥0 [figure omitted; refer to PDF] Clearly (3.37) holds for n=0 . Assume that (3.37) is true for some n≥0 . It follows from (C6)-(C8), (3.32), Algorithm 4, and Lemmas 2.1 and 2.4 that [figure omitted; refer to PDF] That is, (3.37) is true for n+1 . Hence (3.37) holds for each n≥0 .

Next we claim that {_wn}n≥0 is a Cauchy sequence in (BB(S),d) . Let k,n,m∈... , _x0 ∈B...(0,k) , and [straight epsilon]>0 . Suppose that _opty∈D =_{inf y∈D} . Choose y,z∈D with [figure omitted; refer to PDF] It follows from (3.39), (C8), and Lemmas 2.2 and 2.3 that [figure omitted; refer to PDF] Therefore there exist _y1 ∈{y,z}⊂D and _x1 ∈{a(_x0 ,_y1 ),b(_x0 ,_y1 ),c(_x0 ,_y1 )} satisfying [figure omitted; refer to PDF] In a similar method, we can derive that (3.41) holds also for _opty∈D =_{sup y∈D} . Proceeding in this way, we choose _yi ∈D and _xi ∈{a(_xi-1 ,_yi ),b(_xi-1 ,_yi ),c(_xi-1 ,_yi )} for i∈{2,3,...,n} such that [figure omitted; refer to PDF] On account of ([straight phi],ψ)∈_Φ2 , (C7), (3.37), (3.41), and (3.42), we gain that [figure omitted; refer to PDF] which yields that [figure omitted; refer to PDF] Letting [straight epsilon][arrow right]⁰⁺ in the above inequality, we infer that [figure omitted; refer to PDF] It follows from ([straight phi],ψ)∈_Φ2 and (3.45) that {_wn}n≥0 is a Cauchy sequence in (BB(S),d) and it converges to some w∈BB(S) . Algorithm 4 and (3.36) lead to [figure omitted; refer to PDF] which yields that Hw=w . That is, the functional equation (1.3) possesses a solution w∈BB(S) .

Now we show (C10). Let x∈S . Put k=1+[||x||] . It follows from (3.37), (C7), and ([straight phi],ψ)∈_Φ2 that [figure omitted; refer to PDF] that is, (C10) holds.

Next we prove (C11). Given _x0 ∈S , {_yn}n∈... ⊂D , and _xn ∈{a(_xn-1 ,_yn ) , b(_xn-1 ,_yn ) , c(_xn-1 ,_yn )} for n∈... . Put k=[||_x0 ||]+1 . Note that (C7) implies that [figure omitted; refer to PDF] In view of (3.32), (3.37), (3.48), and ([straight phi],ψ)∈_Φ2 , we know that [figure omitted; refer to PDF] which means that _{lim n[arrow right]∞wn} (_xn )=0 .

Finally we prove (C12). Assume that the functional equation (1.3) has another solution h∈BB(S) that satisfies (C11). Let [straight epsilon]>0 and _x0 ∈S . Suppose that _opty∈D =_{inf y∈D} . Select y,z∈D with [figure omitted; refer to PDF] On account of (3.50), (C8), and Lemma 2.1, we conclude that there exist _y1 ∈{y,z} and _x1 ∈{a(_x0 ,_y1 ) , b(_x0 ,_y1 ),c(_x0 ,_y1 )} satisfying [figure omitted; refer to PDF] that is, [figure omitted; refer to PDF] Similarly we can prove that (3.52) holds for _opty∈D =_{sup y∈D} . Proceeding in this way, we select _yi ∈D and _xi ∈{a(_xi-1 ,_yi ),b(_xi-1 ,_yi ),c(_xi-1 ,_yi )} for i∈{2,3,...,n} and n∈... such that [figure omitted; refer to PDF] It follows from (3.52) and (3.53) that [figure omitted; refer to PDF] Since [straight epsilon] is arbitrary, we conclude immediately that w(_x0 )=h(_x0 ) . This completes the proof.

Theorem 3.5.

Let ([straight phi],ψ)∈_Φ2 , p,q,r,s:S×D[arrow right]... and a,b,c:S×D[arrow right]S satisfy conditions (C6)-(C8). Then the functional equation (1.4) possesses a solution w∈BB(S) satisfying conditions (C10)-(C12) and the following two conditions:

(C13): the sequence {_wn}n≥0 generated by Algorithm 5 converges to w , where _w0 ∈BB(S) with |_w0 (x)|≤ψ(||x||) for all (x,k)∈B...(0,k)×... ;

(C14): if q,r , and s are nonnegative and there exists a constant β∈(0,1] such that [figure omitted; refer to PDF] then w is nonnegative.

Proof.

It follows from Theorem 3.4 that the functional equation (1.4) has a solution w∈BB(S) that satisfies (C10)-(C13). Now we show (C14). Given [straight epsilon]>0 , _x0 ∈S and n∈... . It follows from Lemma 2.2, (3.55), and (1.4) that there exist _y1 ∈D and _x1 ∈{a(_x0 ,_y1 ),b(_x0 ,_y1 ),c(_x0 ,_y1 )} such that [figure omitted; refer to PDF] That is, [figure omitted; refer to PDF] Proceeding in this way, we choose _yi ∈D and _xi ∈{a(_xi-1 ,_yi ),b(_xi-1 ,_yi ),c(_xi-1 ,_yi )} for i∈{2,3,...,n} and n∈... such that [figure omitted; refer to PDF] It follows from (3.57) and (3.58) that [figure omitted; refer to PDF] In terms of (C8), (C11), and (3.55), we see that |^βn w(_xn )|[arrow right]0 as n[arrow right]∞ . Letting n[arrow right]∞ in (3.59), we get that w(_x0 )≥-[straight epsilon] . Since [straight epsilon]>0 is arbitrary, we infer immediately that w(_x0 )≥0 . This completes the proof.

Theorem 3.6.

Let ([straight phi],ψ)∈_Φ3 , p,q,r,s:S×D[arrow right]... and a,b,c:S×D[arrow right]S satisfy conditions (C6), (C7), and the following condition:

(C15): q,r , and s are nonnegative and _{sup (x,y)∈S×D} max {q(x,y),r(x,y),s(x,y)}≤1 .

Then the functional equation (1.6) possesses a solution w∈BB(S) satisfying _{lim n[arrow right]∞ wn} (x)=w(x) for any x∈S , where the sequence {_wn}n≥0 is generated by Algorithm 7 with _w0 ∈BB(S),_w0 (x)≤_{sup y∈D} p(x,y) , and |_w0 (x)|≤_{sup y∈D} |p(x,y)| for all x∈S .

Proof.

We are going to prove that, for any n∈... , [figure omitted; refer to PDF] Using ([straight phi],ψ)∈_Φ3 and Algorithm 7, we gain that [figure omitted; refer to PDF] that is, (3.60) holds for n=1 . Assume that (3.60) holds for some n∈... . Lemma 2.1 and (C15) lead to [figure omitted; refer to PDF] which implies that [figure omitted; refer to PDF] and hence (3.60) holds for n+1 . That is, (3.60) holds for any n∈... .

Now we claim that, for any n≥0 , [figure omitted; refer to PDF] In fact, (C6) ensures that [figure omitted; refer to PDF] that is, (3.64) is true for n=0 . Assume that (3.64) is true for some n≥0 . In view of Lemmas 2.1 and 2.4, Algorithm 7, (C6), (C7), and C(15), we gain that [figure omitted; refer to PDF] which yields that (3.64) is true for n+1 . Therefore (3.64) holds for each n≥0 . Given k∈... , note that _{lim n[arrow right]∞} ψ(^{[straight phi]n} (k)) exists. It follows that there exist constants M>0 and _n0 ∈... satisfying ψ(^{[straight phi]n} (k))<M for any n≥_n0 . Thus (3.64) leads to [figure omitted; refer to PDF] On account of (3.60), (3.67), and Algorithm 7, we deduce that {_wn (x)_}n≥0 is convergent for each x∈S and {_wn}n≥0 ∈BB(S) . Put [figure omitted; refer to PDF] Obviously (3.67) ensures that w∈BB(S) . Notice that [figure omitted; refer to PDF] Letting n[arrow right]∞ in the above inequality, by Lemmas 2.1 and 2.3 and the convergence of {_wn (x)_}n≥0 we infer that [figure omitted; refer to PDF] which yields that [figure omitted; refer to PDF] It follows from (3.60), (C15), and Lemma 2.1 that [figure omitted; refer to PDF] which implies that [figure omitted; refer to PDF] Letting n[arrow right]∞ , we gain that [figure omitted; refer to PDF] It follows from (3.71) and (3.74) that w is a solution of the functional equation (1.6). This completes the proof.

Following similar arguments as in the proof of Theorems 3.5 and 3.6, we have the following results.

Theorem 3.7.

Let ([straight phi],ψ)∈_Φ2 , p,q,r,s:S×D[arrow right]... and a,b,c:S×D[arrow right]S satisfy conditions (C6)-(C8). Then the functional equation (1.5) possesses a solution w∈BB(S) satisfying conditions (C10)-(C12) and the two following conditions:

(C16): the sequence {_wn}n≥0 generated by Algorithm 6 converges to w , where _w0 ∈BB(S) with |_w0 (x)|≤ψ(||x||) for all (x,k)∈B...(0,k)×... ;

(C17): if q,r , and s are nonnegative and there exists a constant β∈(0,1] such that [figure omitted; refer to PDF] then w is nonpositive.

Theorem 3.8.

Let ([straight phi],ψ)∈_Φ3 , p,q,r,s:S×D[arrow right]... and a,b,c:S×D[arrow right]S satisfy conditions (C6), (C7), and (C15). Then the functional equation (1.7) possesses a solution w∈BB(S) satisfying _{lim n[arrow right]∞wn} (x)=w(x) for any x∈S , where the sequence {_wn}n≥0 is generated by Algorithm 8 with _w0 ∈BB(S) , _w0 (x)≥_{inf y∈D} p(x,y) and |_w0 (x)|≤_{sup y∈D} |p(x,y)| for all x∈S .

4. Applications

In this section we use these results in Section 3 to establish the existence of solutions, nonnegative solutions, and nonpositive solutions and iterative approximations for several functional equations, respectively.

Example 4.1.

Let X=Y=... , S=[1,2] , D=^...+ , and α=2/3 . It follows from Theorem 3.1 that the functional equation [figure omitted; refer to PDF] possesses a unique solution f∈BC(S) and the sequence {_fn}n≥0 generated by Algorithm 1 converges to f and satisfies (3.2).

Example 4.2.

Let X=Y=... , S=^...+ , D=^...- , and α=2/3 . It is clear that Theorem 3.2 ensures that the functional equation [figure omitted; refer to PDF] possesses a unique solution f∈B(S) and the sequence {_fn}n≥0 generated by Algorithm 2 converges to f and satisfies (3.2).

Remark 4.3.

If q(x,y)=r(x,y)=s(x,y) , a(x,y)=b(x,y)=c(x,y) for all (x,y)∈S×D , then Theorem 3.3 reduces to a result which generalizes the result in [3, page 149] and Theorem 3.4 in [7]. The following example demonstrates that Theorem 3.3 generalizes properly the corresponding results in [3, 7].

Example 4.4.

Let X=Y=... , S=D=^...+ , and α=5/6 . It is easy to verify that Theorem 3.3 guarantees that the functional equation [figure omitted; refer to PDF] has a unique solution in BB(S) . However, the results in [3, page 149] and Theorem 3.4 in [7] are valid for the functional equation (4.3).

Remark 4.5.

(1) If a(x,y)=b(x,y)=c(x,y) , q(x,y)=r(x,y)=s(x,y) for all (x,y)∈S×D , then Theorems 3.4, 3.5, and 3.7 reduce to three results which generalize and unify the result in [3, page 149], Theorem 3.5 in [7], Theorem 3.5 in [12], Corollaries 2.2 and 2.3 in [14], Corollaries 3.3 and 3.4 in [17], and Theorems 2.3 and 2.4 in [18], respectively.

(2) The results in [3, page 149], Theorem 3.5 in [7], Theorem 3.5 in [12], and Theorem 3.4 in [15] are special cases of Theorem 3.5 with q(x,y)=1 , r(x,y)=s(x,y)=0 for all (x,y)∈S×D .

The examples below show that Theorems 3.4, 3.5, and 3.7 are indeed generalizations of the corresponding results in [3, 7, 12, 14, 15, 17, 18].

Example 4.6.

Let X=Y=... , S=D=^...+ . Define two functions ψ,[straight phi]:^...+ [arrow right]^...+ by ψ(t)=^t2 , [straight phi](t)=t/2 for all t∈^...+ . It is easy to see that Theorem 3.4 guarantees that the functional equation [figure omitted; refer to PDF] possesses a solution w∈BB(S) that satisfies (C9)-(C12). However, the corresponding results in [3, 7, 12, 14, 17, 18] are not applicable for the functional equation (4.4).

Example 4.7.

Let X=Y=...=S=D . Put β=1 , ψ(t)=^t2 , and [straight phi](t)=t/3 for all t∈^...+ . It is easy to verify that Theorem 3.5 guarantees that the functional equation [figure omitted; refer to PDF] has a solution w∈BB(S) satisfying (C10)-(C14). But the corresponding results in [3, 7, 12, 14, 15, 17, 18] are not valid for the functional equation (4.5).

Example 4.8.

Let X=Y=... , S=D=^...+ . Put ψ(t)=^t2 and [straight phi](t)=t for all t∈^...+ . It is easy to verify that Theorem 3.6 guarantees that the functional equation [figure omitted; refer to PDF] has a solution w∈BB(S) and the sequence {_wn}n≥0 generated by Algorithm 7 satisfies that _{lim n[arrow right]∞wn} (x)=w(x) for each x∈S , where _w0 ∈BB(S) with [figure omitted; refer to PDF]

Example 4.9.

Let X=Y=...=S=D . Put β=1/3 , ψ(t)=2^t4 and [straight phi](t)=t/3 for all t∈^...+ . It is easy to verify that Theorem 3.7 guarantees that the functional equation [figure omitted; refer to PDF] has a solution w∈BB(S) satisfying (C10)-(C12), (C16), and (C17). But the corresponding results in [3, 7, 12, 14, 17, 18] are not valid for the functional equation (4.8).

Example 4.10.

Let X=Y=S=... , D=^...+ . Put ψ(t)=t/(1+t) and [straight phi](t)=2t for all t∈^...+ . It is easy to verify that Theorem 3.8 guarantees that the functional equation [figure omitted; refer to PDF] possesses a solution w∈BB(S) and the sequence {_wn}n≥0 generated by Algorithm 8 satisfies that _{lim n[arrow right]∞wn} (x)=w(x) for each x∈S , where _w0 ∈BB(S) with [figure omitted; refer to PDF]

Acknowledgments

The authors wish to thank the referees for pointing out some printing errors. This study was supported by research funds from Dong-A University.

References

[1] S. A. Belbas, "Dynamic programming and maximum principle for discrete Goursat systems," Journal of Mathematical Analysis and Applications , vol. 161, no. 1, pp. 57-77, 1991.

[2] R. Bellman, "Some functional equations in the theory of dynamic programming. I. Functions of points and point transformations," Transactions of the American Mathematical Society , vol. 80, pp. 51-71, 1955.

[3] R. Bellman Dynamic Programming , pp. xxv+342, Princeton University Press, Princeton, NJ, USA, 1957.

[4] R. Bellman Methods of Nonlinear Analysis, Vol. II , pp. xvii+261, Academic Press, New York, NY, USA, 1973.

[5] R. Bellman, E. S. Lee, "Functional equations in dynamic programming," Aequationes Mathematicae , vol. 17, no. 1, pp. 1-18, 1978.

[6] R. Bellman, M. Roosta, "A technique for the reduction of dimensionality in dynamic programming," Journal of Mathematical Analysis and Applications , vol. 88, no. 2, pp. 543-546, 1982.

[7] P. C. Bhakta, S. R. Choudhury, "Some existence theorems for functional equations arising in dynamic programming. II," Journal of Mathematical Analysis and Applications , vol. 131, no. 1, pp. 217-231, 1988.

[8] P. C. Bhakta, S. Mitra, "Some existence theorems for functional equations arising in dynamic programming," Journal of Mathematical Analysis and Applications , vol. 98, no. 2, pp. 348-346, 1984.

[9] S. Chang, 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," Journal of Mathematical Analysis and Applications , vol. 160, no. 2, pp. 468-479, 1991.

[10] Z. Liu, "Coincidence theorems for expansion mappings with applications to the solutions of functional equations arising in dynamic programming," Acta Scientiarum Mathematicarum , vol. 65, no. 1-2, pp. 359-369, 1999.

[11] Z. Liu, "Compatible mappings and fixed points," Acta Scientiarum Mathematicarum , vol. 65, no. 1-2, pp. 371-383, 1999.

[12] Z. Liu, "Existence theorems of solutions for certain classes of functional equations arising in dynamic programming," Journal of Mathematical Analysis and Applications , vol. 262, no. 2, pp. 529-553, 2001.

[13] Z. Liu, R. P. Agarwal, S. M. Kang, "On solvability of functional equations and system of functional equations arising in dynamic programming," Journal of Mathematical Analysis and Applications , vol. 297, no. 1, pp. 111-130, 2004.

[14] Z. Liu, S. M. Kang, "Properties of solutions for certain functional equations arising in dynamic programming," Journal of Global Optimization , vol. 34, no. 2, pp. 273-292, 2006.

[15] Z. Liu, S. M. Kang, "Existence and uniqueness of solutions for two classes of functional equations arising in dynamic programming," Acta Mathematicae Applicatae Sinica. English Series , vol. 23, no. 2, pp. 195-208, 2007.

[16] Z. Liu, J. K. Kim, "A common fixed point theorem with applications in dynamic programming," Nonlinear Functional Analysis and Applications , vol. 11, no. 1, pp. 11-19, 2006.

[17] Z. Liu, J. S. Ume, "On properties of solutions for a class of functional equations arising in dynamic programming," Journal of Optimization Theory and Applications , vol. 117, no. 3, pp. 533-551, 2003.

[18] Z. Liu, J. S. Ume, S. M. Kang, "Some existence theorems for functional equations arising in dynamic programming," Journal of the Korean Mathematical Society , vol. 43, no. 1, pp. 11-28, 2006.

[19] Z. Liu, Y. Xu, J. S. Ume, S. M. Kang, "Solutions to two functional equations arising in dynamic programming," Journal of Computational and Applied Mathematics , vol. 192, no. 2, pp. 251-269, 2006.

[20] S. S. Zhang, "Some existence theorems of common and coincidence solutions for a class of systems of functional equations arising in dynamic programming," Applied Mathematics and Mechanics , vol. 12, no. 1, pp. 31-37, 1991.

[21] C.-L. Wang, "The principle and models of dynamic programming. II," Journal of Mathematical Analysis and Applications , vol. 135, no. 1, pp. 268-283, 1988.

[22] C.-L. Wang, "The principle and models of dynamic programming. III," Journal of Mathematical Analysis and Applications , vol. 135, no. 1, pp. 284-296, 1988.

[23] C.-L. Wang, "The principle and models of dynamic programming. V," Journal of Mathematical Analysis and Applications , vol. 137, no. 1, pp. 161-167, 1989.