Content area
In this paper, we introduce and study properties of solutions for certain functional equations arising in dynamic programming of multistage decision processes. A sufficient condition which ensures the existence, uniqueness and iterative approximation of solution for the functional equation is provided. A few other behaviors of solutions for certain functional equations which are particular cases of the functional equation are discussed. The results presented in this paper extend, improve and unify the results due to Bellman, Bhakta and Choudhury, Bhakta and Mitra, Liu, and Liu and Ume. Several examples which dwell upon the importance of our results are also included.
Journal of Global Optimization (2006) 34: 273292 Springer 2006DOI 10.1007/s10898-005-2605-6
ZEQING LIU1 and SHIN MIN KANG21Department of Mathematics, Liaoning Normal University, P. O. Box 200, Dalian, Liaoning
116029, P. R. China (E-mail: [email protected])2Department of Mathematics and RINS, Gyeongsang National University, Chinju 660-701,
Korea (E-mail: [email protected])(Received 6 January 2004; accepted in revised form 15 February 2005)Abstract. In this paper, we introduce and study properties of solutions for the following
functional equation arising in dynamic programming of multistage decision processesf(x) =optyD {u(x, y)Properties of Solutions for Certain Functional
Equations Arising in Dynamic Programmingmax{p(x, y), f (a(x, y))}+ v(x, y) min{q(x, y), f (b(x, y))}+w(x, y)[r(x, y) + f (c(x, y))]}, x S.
A sufcient condition which ensures the existence, uniqueness and iterative approximation
of solution for the functional equation is provided. A few other behaviors of solutions for
certain functional equations which are particular cases of the functional equation are discussed. The results presented in this paper extend, improve and unify the results due to Bellman, Bhakta and Choudhury, Bhakta and Mitra, Liu, and Liu and Ume. Several examples
which dwell upon the importance of our results are also included.Mathematics Subject Classications (1991). 49L20, 49L99, 90C39.Key words: dynamic programming, functional equation, iterative approximation, nonexpansive mapping, nonnegative solution, nonpositive solution, solution1. Introduction and PreliminariesIt is well known that the existence problems of solutions of various functional equations arising in dynamic programming are of both theoretical
and practical interest. For details, we refer to [116] and the references
therein. The paper of Bellman and Lee [5] provided also an excellent survey on the development and applications of the functional equations in
dynamic programming.Within the past 20 years or so, many authors, including Belbas [1],
Bellman [24], Bellman and Roosta [6], Bhakta and Choudhury [7], Bhakta
and Mitra [8], Chang [9], Chang and Ma [10], Huang et al. [11], Liu [1214], Liu et al. [15], Liu and Ume [16] and others, investigated the existence
or uniqueness of solutions, common solutions and coincidence solutions for
several classes of functional equations and systems of functional equations274 Z. LIU AND S. M. KANGarising in dynamic programming, by using various xed point, common
xed point and coincidence point theorems, respectively.In 1984, Bhakta and Mitra [8] studied the following functional equationf(x) =supyD{r(x, y) + f (c(x, y))}and gave an existence and uniqueness result of solution for the functional
equation. In 2001, Liu [14] obtained an existence, uniqueness and iterative
approximation of nonnegative solution for the following functional equationf(x) =[p(x, y) + f (a(x, y))] + v opt[q(x, y), f (b(x, y))]},where u and v are nonnegative constants with u + v = 1.Motivated and inspired by the research work going on in this eld, we
introduce and study the following functional equation arising in dynamic
programming of multistage decision processesf(x) =optyD{u(x, y)max{p(x, y), f (a(x, y))}.In 2003, Liu and Ume [16] provided sufcient conditions which ensure the
existence and uniqueness, and iterative approximation of solution for the
functional equationf(x) =optyD{uinfyDmax{p(x, y), f (a(x, y))}
+v(x, y) min{q(x, y), f (b(x, y))}
+w(x, y)[r(x, y) + f (c(x, y))]}, x S, (1)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.The main purpose of this paper is to discuss properties of solutions
for the functional Equation (1). A sufcient condition which ensures the
existence, uniqueness and iterative approximation of solution for the functional Equation (1) is provided. On the other hand, a few other behaviors
of solutions for certain functional equations which are particular cases of
the functional Equation (1) are established. The results presented in this
paper extend, improve and unify the results due to Bellman [3], Bhakta
and Choudhury [7], Bhakta and Mitra [8], Liu [14] and Liu and Ume [16].
Several examples which dwell upon the importance of our results are also
included.PROPERTIES OF SOLUTIONS FOR CERTAIN FUNCTIONAL EQUATIONS 275Throughout this paper, we assume that R = (, +), R+ = [0, +),
R = (, 0] and I denotes the identity mapping. Let (X, ) and
(Y, ) be real Banach spaces, let S X be the state space, let D Y
be the decision space. Let BB(S) denote the set of all real-valued functions on S that are bounded on bounded subsets of S. For any k [greaterorequalslant] 1 and
f, g BB(S), letdk(f, g) =d(f, g) =k=1sup{|f(x) g(x)| : x B(0,k)},dk(f, g)
1 + dk(f, g)12k,where B(0,k) ={x : x S and x [lessorequalslant] k}. Then {dk}k[greaterorequalslant]1 is a countable family of
pseudometrics on BB(S). A sequence {xn}n[greaterorequalslant]1 in BB(S) is said to be converge to a point x in BB(S) if for any k [greaterorequalslant] 1, dk(xn,x) 0as n , and
to be a Cauchy sequence if for any k [greaterorequalslant] 1, dk(xn,xm) 0as n, m .Itis
clear that (BB(S), d) is a complete metric space. Dene1 ={(, ): and are nondecreasing, (t) > 0 and limn (n(t)) =: and : R+ R+are nondecreasing,
n=0 (n(t)) < and0(t) > 0 for all t> 0},
2 ={(, )for all t> 0}.LEMMA 1.1. [16] Let a, b, c, d be in R. Then|
opt{a, b} opt{c, d}| [lessorequalslant] max{|a c|, |b d|}.2. Properties of Solutions for Functional EquationsIn this section, we rst of all study the existence, uniqueness and iterative
approximation of solution for the functional equation (1). Next we investigate other properties of solutions for some functional equations which are
special cases of (1). Note that the key techniques of the proof of Theorem 2.1 are to construct a nonexpansive mapping G : BB(S) BB(S) and
a Picard iteration sequence {zn}[greaterorequalslant]0 generated by (C4) such that the sequence
{zn}[greaterorequalslant]0converges to some z which is both a xed point of G and a solution
of the functional Equation (1). Our main results are as follows:THEOREM 2.1. Let u, v, w, p, q, r : S D R and a, b, c : S D S be
mappings and let (, ) be in 1 satisfying the following conditions(C1) |u(x, y)|+|v(x, y)|+|w(x, y)| [lessorequalslant] 1 for all (x, y) S D;
(C2) max{|p(x, y)|, |q(x, y)|, |r(x, y)|} [lessorequalslant] (x) for all (x, y) S D;
(C3) max{a(x, y), b(x, y), c(x, y)} [lessorequalslant] (x) for all (x, y) S D.
Then the functional equation (1) possesses a solution z BB(S) satisfying
conditions (C4)(C6)276 Z. LIU AND S. M. KANG(C4) the sequence {zn}n[greaterorequalslant]0 dened byz0(x) =opt
yD{u(x, y)p(x, y) + v(x, y)q(x, y) + w(x, y)r(x, y)}, x S,
zn(x) =optyD{u(x, y)max{p(x, y), zn1(a(x, y))}+v(x, y) min{q(x, y), zn1(b(x, y))}
+w(x, y)[r(x, y) + zn1(c(x, y))]}, x S, n [greaterorequalslant] 1converges to z;(C5) if x0 S, {yn}n[greaterorequalslant]1 D and xn {a(xn1,yn), b(xn1,yn), c(xn1,yn)}
for all n [greaterorequalslant] 1, thenlim
nz(xn) =0;(C6)z is unique relative to condition (C5).Proof. PutH (x, y, h) = u(x, y)max{p(x, y), h(a(x, y))}
+v(x, y) min{q(x, y), h(b(x, y))}
+w(x, y)[r(x, y) + h(c(x, y))],
(x,y,h) S D BB(S),andoptyDH (x, y, h), (x, h) S BB(S).First of all we show that(t)<t, t>Gh(x) =0. (2)Suppose that there exists some t> 0 with (t) [greaterorequalslant] t. Since (, ) 1, it follows that(t) [lessorequalslant] ((t)) [lessorequalslant] (2(t)) [lessorequalslant] [lessorequalslant] (n(t)) 0as n .That is, (t) [lessorequalslant] 0. But (t) > 0for t> 0. This is a contradiction.We claim that G is a nonexpansive mapping from BB(S) into itself. Letk be a positive integer and let h be in BB(S). Using (C3) and (2) we see
thatmax{a(x, y), b(x, y), c(x, y)} [lessorequalslant] (x) [lessorequalslant] x [lessorequalslant] k,PROPERTIES OF SOLUTIONS FOR CERTAIN FUNCTIONAL EQUATIONS 277(x, y) B(0,k) D,
which yields that there exists g(k) > 0 withmax{|h(a(x, y))|, |h(b(x, y))|, |h(c(x, y))|} [lessorequalslant] g(k),
(x, y) B(0,k) Dand|H (x, y, h)| [lessorequalslant] |u(x, y)| max{|p(x, y)|, |h(a(x, y))|}+|v(x, y)|max{|q(x, y)|, |h(b(x, y))|}
+|w(x, y)|[|r(x, y)|+|h(c(x, y))|]
(|u(x, y)|+|v(x, y)|+|w(x, y)|)((x) + g(k))
(k) + g(k), (x, y)
B(0,k) Dby (C1) and (C2). It follows that|Gh(x)| [lessorequalslant] supmax{|u(x,y)[max{p(x,y),h(a(x,y))}max{p(x,y),t (a(x,y))}]+v(x,y)[min{q(x,y),h(b(x,y))}min{q(x,y),t (b(x,y))}]
+w(x,y)[h(c(x,y))t (c(x,y))]|, |u(x,s)[max{p(x,s),h(a(x,s))}
(k) + g(k), x
B(0,k),which gives that Gh is bounded on bounded subsets of S. That is, G mapsBB(S) into itself. Given > 0,x B(0,k) and h, t BB(S). Suppose that
optyD = infyD . Then there exist y, s D satisfyingGh(x) > H (x, y, h) , Gt (x) > H (x, s, t) ,
Gh(x) [lessorequalslant] H (x, s, h), Gt (x) [lessorequalslant] H (x, y, t). (3)According to (C1), (C3), (2), (3) and Lemma 1.1, we arrive at|Gh(x)Gt (x)|<max{|H (x,y,h)H (x,y,t)|,|H(x,s,h)H(x,s,t)|}+
=yD |H (x, y, h)|max{p(x,s),t (a(x,s))}]+v(x,s)[min{q(x,s),h(b(x,s))}min{q(x,s),t (b(x,s))}]+w(x,s)[h(c(x,s))t (c(x,s))]|}+
[lessorequalslant]max{|u(x,y)||h(a(x,y))t (a(x,y))|+|v(x,y)||h(b(x,y))t (b(x,y))|+|w(x,y)||h(c(x,y))t (c(x,y))|,|u(x,s)||h(a(x,s))t (a(x,s))|
+|v(x,s)||h(b(x,s))t (b(x,s))|+|w(x,s)||h(c(x,s))t (c(x,s))|}+
[lessorequalslant]max{(|u(x,y)|+|v(x,y)|+|w(x,y)|)dk(h,t),(|u(x,s)|+|v(x,s)|+|w(x,s)|)dk(h,t)}+
dk(h,t)+,278 Z. LIU AND S. M. KANGwhich means thatdk(Gh, Gt) [lessorequalslant] dk(h, t) + .Letting 0 in the above inequality, we havedk(Gh, Gt) [lessorequalslant] dk(h, t),which implies thatd(Gh, Gt) =1dk(Gh, Gt)
1 + dk(Gh, Gt)[lessorequalslant]12k2kdk(h, t)
1 + dk(h, t) = d(h, t).(4)k=1k=1Similarly, if optyD = supyD, we can conclude also that (4) holds.We now assert that for each x S|zn(x)| [lessorequalslant]n(i(x)), n [greaterorequalslant] 0. (5)In fact, (C1) and (C2) ensure that|z0(x)|=|optyD{u(x, y)p(x, y) + v(x, y)q(x, y) + w(x, y)r(x, y)}|
[lessorequalslant] supyD{|u(x, y)||p(x, y)|+|v(x, y)||q(x, y)|+|w(x, y)||r(x, y)|}
[lessorequalslant] supyD{(|u(x, y)|+|v(x, y)|+|w(x, y)|)(x)}(x),that is, (5) holds for n = 0. Suppose that (5) is true for some n [greaterorequalslant] 0. It follows from (C1) to (C3) that|zn+1i=0(x)|
=|max{p(x, y), zn(a(x, y))}+v(x, y) min{q(x, y), zn(b(x, y))}+ w(x, y)[r(x, y) + zn(c(x, y))]}|
[lessorequalslant] supyD{|u(x, y)|opt
yD{u(x, y)max{|p(x, y)|, |zn(a(x, y))|}
+|v(x, y)|max{|q(x, y)|, |zn(b(x, y))|}
+|w(x, y)|[|r(x, y)|+|zn(c(x, y))|]}PROPERTIES OF SOLUTIONS FOR CERTAIN FUNCTIONAL EQUATIONS 279[lessorequalslant] supyD|u(x, y)| max (x),ni=0(i(a(x, y)))+|v(x, y)|max (x),n
i=0(i(b(x, y)))+|w(x, y)|(x) +ni=0(i(c(x, y)))[lessorequalslant] supyD|u(x, y)| max (x),ni=0(i+1(x))+|v(x, y)|max (x),n
i=0(i+1(x))n+1+|w(x, y)|(x) +ni=0(i+1(x)) [lessorequalslant]i=0(i(x)).Hence (5) holds for each n [greaterorequalslant] 0.We show that {zn}n[greaterorequalslant]0 is a Cauchy sequence in (BB(S), d). Let k be a
positive integer and x0 B(0,k). Given > 0 and positive integers n andm,ifoptyD = infyD, then there exist s, t D withzn(x0)>H(x0,s,zn1) 21, zn+m(x0)>H(x0,t,zn+m1) 21,
zn(x0) [lessorequalslant] H(x0,t,zn1), zn+m(x0) [lessorequalslant] H(x0,s,zn+m1).It follows from (C1) and Lemma 1.1 that there exist y1 {s, t}and x1
{a(x0,y1), b(x0,y1), c(x0,y1)}satisfying|zn+m(x0) zn(x0)|
< max{|H(x0,s,zn+m1) H(x0,s,zn1)|,
|H(x0,t,zn+m1) H(x0,t,zn1)|} +1
[lessorequalslant] max{|u(x0,s)|| max{p(x0, s), zn+m1(a(x0,s))}
2max{p(x0, s), zn1(a(x0,s))}|
+|v(x0,s)||min{q(x0, s), zn+m1(b(x0,s))}
min{q(x0, s), zn1(b(x0,s))}|+|w(x0,s)||zn+m1(c(x0,s)) zn1(c(x0,s))|,
|u(x0,t)||max{p(x0, t), zn+m1(a(x0,t))}
max{p(x0, t), zn1(a(x0,t))}|+|v(x0,t)||min{q(x0, t), zn+m1(b(x0,t))}
min{q(x0, t), zn1(b(x0,t))}|+|w(x0,t)||zn+m1(c(x0,t)) zn1(c(x0,t))|} +21280 Z. LIU AND S. M. KANG[lessorequalslant] max{|u(x0,s)||zn+m1(a(x0,s)) zn1(a(x0,s))|+|v(x0,s)||zn+m1(b(x0,s)) zn1(b(x0,s))|
+|w(x0,s)||zn+m1(c(x0,s)) zn1(c(x0,s))|,
|u(x0,t)||zn+m1(a(x0,t)) zn1(a(x0,t))|
+|v(x0,t)||zn+m1(b(x0,t)) zn1(b(x0,t))|
+|w(x0,t)||zn+m1(c(x0,t)) zn1(c(x0,t))|} +21[lessorequalslant] max{(|u(x0,s)|+|v(x0,s)|+|w(x0,s)|)max{|zn+m1(a(x0,s)) zn1(a(x0,s))|,
|zn+m1(b(x0,s)) zn1(b(x0,s))|,
|zn+m1(c(x0,s)) zn1(c(x0,s))|},
(|u(x0,t)|+|v(x0,t)|+|w(x0,t)|)
max{|zn+m1(a(x0,t)) zn1(a(x0,t))|,
|zn+m1(b(x0,t)) zn1(b(x0,t))|,
|zn+m1(c(x0,t)) zn1(c(x0,t))|} +21[lessorequalslant] |zn+m1(x1) zn1(x1)|+ 21,that is,|zn+m(x0) zn(x0)| < |zn+m1(x1) zn1(x1)|+21; (6)if optyD =supyD, we can similarly derive that (6) holds also. Proceeding
in this way, we know that there exist yi D and xi {a(xi1,yi), b(xi1,yi),
c(xi1,yi)}for i {2, 3,...,n} such that|zn+m1(x1) zn1(x1)| < |zn+m2(x2) zn2(x2)|+22,|zn+m2(x2) zn2(x2)| < |zn+m3(x3) zn3(x3)|+23,2n. (7)In terms of (C3), (2) and (5)(8), we deduce that|zn+m
|zm+1(xn1) z1(xn1)| < |zm(xn) z0(xn)|+(x0) zn(x0)| < |zm(xn) z0(xn)|+ ,[lessorequalslant] |zm(xn)|+|z0(xn)|+
[lessorequalslant]mi=0(i(xn)) + (xn) + [lessorequalslant]mi=0(i+1(xn1)) + ((xn1)) + PROPERTIES OF SOLUTIONS FOR CERTAIN FUNCTIONAL EQUATIONS 281mi=0[lessorequalslant](i+n(x0)) + (n(x0)) + [lessorequalslant]i=n1(i(x0)) + [lessorequalslant]i=n1(i(k)) + ,which yields that(i(k)) + .Letting 0 in the above inequality, we get thatdk(zn+m,zn) [lessorequalslant]dk(zn+m,zn) [lessorequalslant]i=n1i=n1(i(k)). (8)for each t> 0. Thus (8) ensures that {zn}n[greaterorequalslant]0is a Cauchy sequence in (BB(S), d) and it converges to some z BB(S).It
follows from (4) thatd(Gz, z) [lessorequalslant] d(Gz, Gzn) + d(zn+1,z)d(z, zn) + d(zn+1,z) Notice that
n=0 (n(t)) < 0as n ,which yields that Gz = z. That is, the functional equation (1) possesses a
solution z.Given x0 S, {yn}n[greaterorequalslant]1 D and xn {a(xn1,yn), b(xn1,yn), c(xn1,yn)} for
n [greaterorequalslant] 1. Put k = [x0] + 1, where [t] denotes the largest integer not exceeding
t. For each > 0, there exists a positive integer m withdk(z, zn) +
(9)i=n(i(k)) < , n>m.It follows from (C3) thatxn [lessorequalslant] (xn1) [lessorequalslant] [lessorequalslant] n(x0) [lessorequalslant] n(k) [lessorequalslant] k, n [greaterorequalslant] 1. (10)282 Z. LIU AND S. M. KANGOn account of (5), (9) and (10), we obtain that for n>m|z(xn)| [lessorequalslant] |z(xn) zn(xn)|+|zn(xn)|dk(z, zn) +ni=0(i(xn))
dk(z, zn) +n<,i=0(i(k))0.Assume that g is another solution of the functional equation (1) relative
to condition (C5). For any > 0 and x0 S,ifoptyD = infyD, then there
exist s, t D satisfyingz(x0)>H(x0,s,z) which gives that limn z(xn) =1, g(x0)>H(x0,t,g) 21,
z(x0) [lessorequalslant] H(x0,t,z), g(x0) [lessorequalslant] H(x0,s,g). (11)In view of Lemma 1.1, (C1) and (11), we can select y1 {s, t} Dand x1
{a(x0,y1), b(x0,y1), c(x0,y1)}2such that|z(x0)g(x0)|<max{|H(x0,s,z)H(x0,s,g)|,|H(x0,t,z)H(x0,t,g)|}+21
[lessorequalslant]max{|u(x0,s)||max{p(x0,s),z(a(x0,s))}max{p(x0,s),g(a(x0,s))}|+|v(x0,s)||min{q(x0,s),z(b(x0,s))}min{q(x0,s),g(b(x0,s))}|
+|w(x0,s)||z(c(x0,s))g(c(x0,s))|,|u(x0,t)||max{p(x0,t),z(a(x0,t))}max{p(x0,t),g(a(x0,t))}|+|v(x0,t)||min{q(x0,t),z(b(x0,t))}
min{q(x0,t),g(b(x0,t))}|+|w(x0,t)||z(c(x0,t))g(c(x0,t))|}+21
[lessorequalslant]max{(|u(x0,s)|+|v(x0,s)|+|w(x0,s)|)max{|z(a(x0,s))g(a(x0,s))|,|z(b(x0,s))g(b(x0,s))|,|z(c(x0,s))g(c(x0,s))|},
(|u(x0,t)|+|v(x0,t)|+|w(x0,t)|)max{|z(a(x0,t))g(a(x0,t))|,
|z(b(x0,t))g(b(x0,t))|,|z(c(x0,t))g(c(x0,s))|}+21[lessorequalslant]|z(x1)g(x1)|+21,that is,|z(x0) g(x0)| < |z(x1) g(x1)|+21; (12)
if optyD =supyD, we similarly conclude that (12) holds. Proceeding in
this way, we know that there exist yi D and xi {a(xi1,yi), b(xi1,yi),
c(xi1,yi)}for i {2, 3,...,n} such thatPROPERTIES OF SOLUTIONS FOR CERTAIN FUNCTIONAL EQUATIONS 283|z(x1) g(x1)| < |z(x2) g(x2)|+22,|z(x2) g(x2)| < |z(x3) g(x3)|+23,
|z(xn1) g(xn1)| < |z(xn) g(xn)|+2n. (13)It follows from (C5), (12) and (13) that|z(x0) g(x0)| < |z(xn) g(xn)|+ as n .Since is arbitrary, we immediately conclude that z(x0) = g(x0). This com-pletes the proof.Remark 2.1. (a) If u(x, y)=v(x, y)=0, w(x, y)=1 for each (x, y) S D,
= MI, where M is a constant, and optyD = supyD, then Theorem 2.1
reduces to Theorem 2.4 of Bhakta and Mitra [8].(b) In case v(x, y) = w(x, y) = 0, u(x, y) = 1 for each (x, y) S D, = I ,
and optyD = infyD, then Theorem 2.1 reduces to Theorem 3.5 of Bhakta
and Choudhury [7] and a result of Bellman [3, p. 149].The example below reveals that Theorem 2.1 extends substantially the
results due to Bellman [3], Bhakta and Choudhury [7] and Bhakta and
Mitra [8].EXAMPLE 2.1. Let X = Y = R and S = D = R+. Dene u, v, w, p, q, r : S
D R, a, b, c: S D S, and , : R+ R+ byu(x, y) =1
2+xy, if x [greaterorequalslant] y,1
4 , if x [greaterorequalslant] y,1
8+x1
8+x+y, if x<y,v(x, y) =, if x<y,2+y , if x [greaterorequalslant] y,3
5+sin(xy)w(x, y) = 14+x, if x<y,
p(x, y) = x2 cos(x2 y2),q(x, y) =x3y1 + x2y2, r(x, y) =x sin x1 + ln(1 +|x y|),a(x, y) =x1 + x2+y2
, b(x, y) =x2 + xy
, c(x, y) =x3 + sin(x y)for all (x, y) S D and(t) = t2 and (t) =t, t R+.It is easy to verify that the assumptions of Theorem 2.1 are fullled. Hence
the functional equation(1) possesses a solution z BB(S) satisfying conditions12284 Z. LIU AND S. M. KANG(C4)(C6). However, the results of Bellman[3], Bhakta and Cholldhury [7] and
Bhakta and Mitra [8] are not valid for the functional equation (1).Taking v(x, y) = 0 for all (x, y) S D in Theorem 2.1, we haveTHEOREM 2.2. Let u, w, p, r : S D R and a, c : S D S be mappings
and let (, ) be in 1 satisfying conditions(C7) |u(x, y)|+|w(x, y)| [lessorequalslant] 1 for all (x, y) S D;
(C8) max{|p(x, y)|, |r(x, y)|} [lessorequalslant] (x) for all (x, y) S D;
(C9) max{a(x, y), c(x, y)} [lessorequalslant] (x) for all (x, y) S D.
Then the functional equationf(x) =(C10) the sequence {zn}n[greaterorequalslant]0 dened byz0(x) =max{p(x, y), zn1(a(x, y))}+w(x, y)[r(x, y) + zn1(c(x, y))]}, x S, n [greaterorequalslant] 1
converges to z;(C11) if x0 S, {yn}n[greaterorequalslant]1 D and xn {a(xn1,yn), c(xn1,yn)} for each
n [greaterorequalslant] 1, thenlim
nmax{p(x, y), f (a(x, y))}+w(x, y)[r(x, y) + f (c(x, y))]}, x S (14)
possesses a solution z BB(S) satisfying conditions (C10)(C14)optyD{u(x, y)opt
yD{u(x, y)p(x, y) + w(x, y)r(x, y)}, x S,
zn(x) =optyD{u(x, y)z(xn) =0,(C12)z is a unique solution of the functional equation (14) relative to condition (C11);(C13) if u and w are nonnegative and u(x, y) + w(x, y) = 1 for all (x, y)
S D, then for any > 0 and x0 S, there exist {yn}n[greaterorequalslant]1 D and xn
{a(xn1,yn), c(xn1,yn)}w(xn,yn+1)r(xn,yn+1) .Moreover, if r is nonnegative, then z is also nonnegative.Proof. It follows from Theorem 2.1 that the functional equation (14)
possesses a solution z BB(S) satisfying (C10)(C12). Now we show that
(C13) holds. Let be any positive number and x0 S. If optyD = infyD,
then there exist y1 D and x1 {a(x0,y1), c(x0,y1)} withfor all n [greaterorequalslant] 1 such thatz(x0) [greaterorequalslant]PROPERTIES OF SOLUTIONS FOR CERTAIN FUNCTIONAL EQUATIONS 285z(x0) > u(x0,y1) max{p(x0,y1), z(a(x0,y1))}+w(x0,y1)[r(x0,y1) + z(c(x0,y1))] 21
w(x0,y1)r(x0,y1) + u(x0,y1)z(a(x0,y1))+w(x0,y1)z(c(x0,y1)) 21
w(x0,y1)r(x0,y1) +[u(x0,y1) + w(x0,y1)]min{z(a(x0,y1)), z(c(x0,y1))} 21=w(x0,y1)r(x0,y1) + z(x1) 21. (15)Similarly we can select yi Dand xi {a(xi1,yi), c(xi1,yi)}for i {2, 3,...,n} such thatz(x1)>w(x1,y2)r(x1,y2) + z(x2) 22,z(x2)>w(x2,y3)r(x2,y3) + z(x3) 23,
z(xn1)>w(xn1,yn)r(xn1,yn) + z(xn) 2n. (16)Combining (15) and (16) we derive thatz(x0)>
n(17)i=1w(xi1,yi)r(xi1,yi) + z(xn) .Using the same argument as above, we also conclude that (17) holds for
optyD = supyD. Note that (C8) and (C9) ensure that|w(xn1,yn)r(xn1,yn)|= w(xn1,yn)|r(xn1,yn)|(xn1) [lessorequalslant] ((xn2)) [lessorequalslant]
(n1(x0))and
n=1 (n1(x0)) is convergent. It follows that the series|w(xn1,yn)r(xn1,yn)|is convergent. Letting n in (17), by (C11) we know thatz(x0) [greaterorequalslant]n=1w(xn1,yn)r(xn1,yn) .Suppose that r is nonnegative. It follows from (17) that for given > 0
and x0 S, there exist yi D and xi {a(xi1,yi), c(xi1,yi)} for i
{1, 2,...,n} such thatn=1286 Z. LIU AND S. M. KANGz(x0)>z(xn) .(18)Letting n in (18), by (C11) we obtain thatz(x0) [greaterorequalslant] ,which gives that z(x0) [greaterorequalslant] 0 since is arbitrary. This completes the proof.A proof similar to that of Theorem 2.2 yields the following result and is
thus omitted.THEOREM 2.3. Let u, w, p, r : S D R and a, c : S D S be
mappings and (, ) be in 1 satisfying conditions (C7)(C9). Then the
functional equationf(x) = optyD{u(x, y)min{p(x, y), f (a(x, y))}
+w(x, y)[r(x, y) + f (c(x, y))]}, x S (19)possesses a solution z BB(S) satisfying conditions (C11) and(C14) the sequence {zn}n[greaterorequalslant]0 dened byz0(x) =optyD{u(x, y)opt
yD{u(x, y)p(x, y) + w(x, y)r(x, y)}, x S,min{p(x, y), zn1(a(x, y))}+w(x, y)[r(x, y) + zn1(c(x, y))]}, x S, n [greaterorequalslant] 1converges to z;(C15)z is a unique solution of the functional equation (19) relative to condition (C11);(C16) if u and w are nonnegative, then for any > 0 and x0 S, there exist
{zn}n[greaterorequalslant]1 D
z(x0) [lessorequalslant]zn(x) =and xn {a(xn1,yn), c(xn1,yn)} for all n [greaterorequalslant] 1 such thatw(xn,yn+1)r(xn,yn+1) + .Moreover, if r is nonpositive, then z is also nonpositive.Remark 2.2. (a) Taking = I , u(x, y) = , w(x, y) = 1 and a(x, y) =
c(x, y) for any (x, y) S D, where is a constant in [0, 1], then Theorem2.2 reduces to a result which improves Theorem 3.2 of Liu and Ume [16],
which, in turn, is a generalization of a result of Bellman [3, p. 149], Theorem 3.5 of Bhakta and Choudhury [7] and Theorem 2.4 of Bhakta and
Mitra [8].PROPERTIES OF SOLUTIONS FOR CERTAIN FUNCTIONAL EQUATIONS 287(b) If = I , u(x, y) = , w(x, y) = 1 and a(x, y) = c(x, y) for any
(x, y) S D,where is a constant in [0, 1], then Theorem 2.3 reduces to
a result which improves Theorem 3.3 of Liu and Ume [16].The following examples show that Theorems 2.2 and 2.3 are indeed
extensions of the results due to Bellman [3], Bhakta and Choudhury [7],
Bhakta and Mitra [8] and Liu and Ume [16].EXAMPLE 2.2. Let X = Y = S = R and D = R+. Dene u, w, p, r : S D
R, a, c : S D S and , : R+ R+ byp(x, y) = x2 sin x, r(x, y) =2|x|3y1 + y2 ,a(x, y) =x3 +|x|y
, c(x, y) =x3 , if |x| < 3,sin x
|x|+y, if |x| [greaterorequalslant] 3,, for x2 + y2 > 1,1xu(x, y) = |xy|
x2+y22y2 , for x2+y2 [lessorequalslant] 1,2y21+xw(x, y) =x2+y2|xy|
x2+y2, for x2 + y2 > 1,x2y2
1+x2y2 , for x2+y2 [lessorequalslant] 1for all (x, y) S D,(t) = t3 and (t) =t, t R+.Then the conditions of Theorem 2.2 are fullled and consequently the
functional equation (14) possesses a solution z BB(S) satisfying conditions (C10)(C13). But the results of Bellman [3], Bhakta and Choudhury[7], Bhakta and Mitra [8] and Liu and Ume [16] are not valid for the functional equation (14).EXAMPLE 2.3. Let X, Y, S, T , u, w, p, a, c, and be as in Example 2.2.
Dene r : S D R byr(x, y) = x2 sin x +1131 +|x|y
, (x, y) S D.
It is easily veried that the assumptions of Theorem 2.3 are satised. Thus
the functional equation (19) possesses a solution in BB(S) satisfying conditions (C14)(C16). However, the result of Liu and Ume [16] is not applicable because|r(x, y)| [lessorequalslant] M|x|288 Z. LIU AND S. M. KANGdoes not hold for (xM,yM) = (M +1, 1) S D, where M is a positive con-stant.As consequences of Theorems 2.12.3, we have the followingCOROLLARY 2.1. Let u, p : S D R and a : S D S be mappings and
let (, ) be in 1 satisfying the following conditions:(C17) |u(x, y)| [lessorequalslant] 1 for all (x, y) S D;
(C18) |p(x, y)| [lessorequalslant] (x) for all (x, y) S D;
(C19) a(x, y) [lessorequalslant] (x) for all (x, y) SD.
Then the functional equationf(x) =opt
yD{u(x, y)p(x, y)}, x S,[p(x, y) + zn1(a(x, y))]}, x S, n [greaterorequalslant] 1converges to z;(C21) if x0 S, {yn}n[greaterorequalslant]1 D and xn = a(xn1,yn) for each n [greaterorequalslant] 1, thenlim
n[p(x, y) + f (a(x, y))], x S (20)possesses a solution z BB(S) satisfying(C20) the sequence {zn}n[greaterorequalslant]0 dened byz0(x) =optyD{u(x, y)zn(x) =optyD{u(x, y)z(xn) =0;(C22)z is a unique solution of the functional equation (20) relative to(C21);(C23) if u(x, y) = 1 for each (x, y) S D, then for any > 0 and x0 S,
there exist {yn}n[greaterorequalslant]1 D and xn = a(xn1,yn) for all n [greaterorequalslant] 1 such that
z(x0)
[lessorequalslant] .Furthermore, if p is nonnegative, then z is nonnegative; and if p is nonpositive,
then z is nonpositive.Proof. In order to show Corollary 2.1, by Theorems 2.2 and 2.3 it is
sufcient to show that (C23) holds. Given > 0 and x0 S. If optyD =
infyD, then there exist {yn}n[greaterorequalslant]1 D and xn = a(xn1,yn) for all n [greaterorequalslant] 1 such
thatp(xn1,yn) + z(xn) 2n<z(xn1) [lessorequalslant] p(xn,yn) + z(xn),PROPERTIES OF SOLUTIONS FOR CERTAIN FUNCTIONAL EQUATIONS 289which yields thatn1(21)i=0p(xi,yi+1) + z(xn) <z(x0) [lessorequalslant]n1i=0p(xi,yi+1) + z(xn).Letting n in (21), by (C21) we know that
z(x0)
[lessorequalslant] .n=0p(xn,yn+1)Similarly we conclude that the above inequality holds for optyD = supyD.
This completes the proof.The proofs of Corollaries 2.2 and 2.3 are quite similar to those of
Theorems 2.1 and 2.2 and Corollary 2.1, and therefore are omitted.COROLLARY 2.2. Let u, p : S D R and a : S D S be mappings and
let (, ) be in 2 satisfying conditions (C17)(C19). Then the functional
equationf(x) =max{p(x, y), f (a(x, y))}}, x S (22)possesses a solution z BB(S) satisfying conditions (C21) andoptyD{u(x, y)(C24) the sequence {zn}n[greaterorequalslant]0 dened byz0(x) =opt
yD{u(x, y)p(x, y)}, x S,
zn(x) =optyD{u(x, y)max{p(x, y), zn1(a(x, y))}}, x S, n [greaterorequalslant] 1converges to z;(C25)z is a unique solution of the functional equation (22) relative to condition (C21);(C26) if u(x, y) = 1 for each (x, y) S D, then z is nonnegative.COROLLARY 2.3. Let u, p : S D R and a : S D S be mappings and
let (, ) be in 2 satisfying conditions (C17)(C19). Then the functional
equationf(x) =min{p(x, y), f (a(x, y))}}, x S (23)possesses a solution z BB(S) satisfying condition (C21) andoptyD{u(x, y)290 Z. LIU AND S. M. KANG(C27) the sequence {zn}n[greaterorequalslant]0 dened by
z0(x) =optyD{u(x, y)p(x, y)}, x S,min{p(x, y), zn1(a(x, y))}}, x S, n [greaterorequalslant] 1converges to z;(C28)z is a unique solution of the functional equation (23) relative to condition (C21);(C29) if u(x, y) = 1 for each (x, y) S D, then z is nonpositive.Remark 2.3. In case u(x, y) = 1 for all (x, y) S D, = MI , where M
is a positive constant, then Corollaries 2.1-2.3 reduce to three results which
include Theorem 2.4 of Bkakta and Choudhury [7], Theorem 3.5 of Bhakta
and Mitra [8], Theorem 3.5 of Liu [14] and Corollaries 3.23.4 of Liu and
Ume [16] as special cases.The following simple example demonstrates that Corollaries 2.12.3 generalize properly the results due to Bhakta and Choudhury [7], Bhakta and
Mitra [8], Liu [14] and Liu and Ume [16].EXAMPLE 2.4. Let X = Y = R, S = R+ and D = R. Dene u : S D R
and , : R+ R+ byu(x, y) =1, (x, y) S D, (t) = t2 and (t) =
, x S, (24)
, x S (25)
andf(x) =zn(x) =optyD{u(x, y), t R+.According to Corollaries 2.12.3, we immediately conclude that the functional equationsf(x) =optyDx2 sin y + f x2 xy
, x S (26)possess, respectively, a solution in BB(S) satisfying conditions (C20)(C23), conditions (C21) and (C24)(C26), and conditions (C21) and(C27)(C29), respectively. But the results of Bhakta and Choudhury [7],
Bhakta and Mitra [8], Liu [14] and Liu and Ume [16] are not valid for the
functional equations (24)(26).t2f(x) =optyDmax x2 sin y, f x2 xyoptyDmin x2 sin y, f x2 xyPROPERTIES OF SOLUTIONS FOR CERTAIN FUNCTIONAL EQUATIONS 291f and g are called coincidence solutions of the following system of
functional equations
optyD{u(x, y) max{p(x, y), g(a(x, y))}
+v(x, y) min{q(x, y), g(b(x, y))}
+w(x, y)[r(x, y) + g(c(x, y))]},optyD{u(x, y) max{p(x, y), f (a(x, y))}+v(x, y) min{q(x, y), f (b(x, y))}
+w(x, y)[r(x, y) + f (c(x, y))]}, x S, x S.f(x) =g(x) =if condition (28) below is fullled :f (x) = optyD{u(x, y) max{p(x, y), g(a(x, y))}+v(x, y) min{q(x, y), g(b(x, y))}
+w(x, y)[r(x, y) + g(c(x, y))]},
g(x) = optyD{u(x, y) max{p(x, y), f (a(x, y))}+v(x, y) min{q(x, y), f (b(x, y))}
+w(x, y)[r(x, y) + f (c(x, y))]}(27)(28)Before concluding this paper, we would like to point out directions for
further work in the form of open problems.Problem 2.1. Is there a contraction mapping G : BB(S) BB(S) such that
the Picard iteration sequence {zn}n[greaterorequalslant]0 dened by (C4) converges to the
unique xed point of G under the conditions of Theorem 2.1 ?Problem 2.2. Is there a nonnegative or nonpositive solution for the functional equation (1) under the conditions of Theorem 2.1 ?Problem 2.3. If the answer to Problem 2.2 is no, then what additional
hypotheses are needed in Theorem 2.1 to guarantee the existence of nonnegative or nonpositive solutions for the functional equation (1) ?Problem 2.4. Does the system of functional equations (27) possess coincidence solutions in BB(S) ?AcknowledgementThe authors are indebted to the referees for their helpful comments. This
work was supported by the Science Research Foundation of Educational
Department of Liaoning Province (2004C063) and Korea Research Foundation Grant (KRF-2003-005-C00013).292 Z. LIU AND S. M. KANGReferences1. Belbas, S.A. (1991), Dynamic programming and maximum principle for discrete goursat
systems, Journal of Mathematical Analysis and Applications 161, 5777.2. Bellman, R. (1955), Some functional equations in the theory of dynamic programming.I. functions of points and point transformations, Transaction American Mathematical
Socilisam 80, 5571.3. Bellman, R. (1957), Dynamic Programming, Princeton University Press, Princeton, New
Jersey.4. Bellman, R. (1973), Methods of Nonlinear Analysis, Vol. 2, Academic Press, New York.5. Bellman, R. and Lee, E. S. (1978), Functional equations arising in dynamic programming, Aequationes Math. 17, 118.6. Bellman, R. and Roosta, M. (1982), A technique for the reduction of dimensionality in
dynamic programming, Journal of Mathematical Analysis and Applications 88, 543546.7. Bhakta, P.C. and Choudhury, S.R. (1988), Some existence theorems for functional equations arising in dynamic programming II, Journal of Mathematical Analysis and Applications 131, 217231.8. Bhakta, P.C. and Mitra, S. (1984), Some existence theorems for functional equations
arising in dynamic programming, Journal of Mathematical Analysis and Applications 98,
348346.9. Chang, S.S. (1991), Some existence theorems of common and coincidence solutions for
a class of functional equations arising in dynamic programming, Applied Mathematical
Mechancial 12, 3137.10. Chang, S.S. and Ma (1991), Coupled xed 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 160,
468479.11. Huang, N.J. Lee, B.S. and Kang, M.K. (1997), Fixed point theorems for compatible
mappings with applications to the solutions of functional equations arising in dynamic
programmings, IJMMS 20, 673680.12. Liu, Z. (1999), Coincidence theorems for expansion mappings with applications to the
solutions of functional equations arising in dynamic programming, Acta Science Mathematical (Szeged) 65, 359369.13. Liu, Z. (1999), Compatible mappings and xed points, Acta Science Mathematical
(Szeged) 65, 371383.14. Liu, Z. (2001), Existence theorems of solutions for certain classes of functional equations arising in dynamic programming, Journal Mathematical Analytical Application 262,
529553.15. Liu, Z. Agarwal, R.P. and Kang, S.M. (2004), On solvability of functional equations and
system of functional equations arising in dynamic programming, Journal Mathematical
Analytical Application 297, 111130.16. Liu, Z. and Ume, J.S. (2003), On properties of solutions for a class of functional
equations arising in dynamic programming, Journal Optimization Theory Applied 117,
533551.
Springer 2006