Hindawi Publishing Corporation
Fixed Point Theory and Applications
Volume 2010, Article ID 905858, 19 pages
doi:10.1155/2010/905858
Research Article
On Properties of Solutions for Two Functional
Equations Arising in Dynamic Programming
Zeqing Liu,
1
Jeong Sheok Ume,
2
and Shin Min Kang
3
1
Department of Mathematics, Liaoning Normal University, Dalian, Liaoning 116029, China
2
Department of Applied Mathematics, Changwon National University,
Changwon 641-773, Republic of Korea
3
Department of Mathematics and Research Institute of Natural Science, Gyeongsang National University,
Chinju 660-701, Republic of Korea
Correspondence should be addressed to Jeong Sheok Ume,
Received 12 July 2010; Accepted 26 October 2010
Academic Editor: Manuel De la Sen
Copyright q 2010 Zeqing Liu et al. This is an open access article distributed under the Creative
Commons Attribution License, which permits unrestricted use, distribution, and reproduction in
any medium, provided the original work is properly cited.
We introduce and study two new functional equations, which contain a lot of known functional
equations as special cases, arising in dynamic programming of multistage decision processes. By
applying a new fixed point theorem, we obtain the existence, uniqueness, iterative approximation,
and error estimate of solutions for these functional equations. Under certain conditions, we also
x
max
y∈D
p
x, y
f
a
x, y
, ∀x ∈ S,
f
x
min
y∈D
max
p
x, y
,f
f
x
sup
y∈D
p
x, y
m
i1
q
i
x, y
f
a
i
x, y
, ∀x ∈ S,
1.1
q
i
x, y
opt
v
i
x, y
,f
a
i
x, y
, ∀x ∈ S
f
x
opt
y∈D
t
processes:
f
x
opt
y∈D
p
x, y
H
x, y, f
, ∀x ∈ S, 1.3
f
x
opt
y∈D
r
x, y
m
x, y
f
b
i
x, y
, ∀x ∈ S,
1.4
where X and Y are real Banach spaces, S ⊆ X is the state space, D ⊆ Y is the decision space,
opt denotes the sup or inf, x and y stand for the state and decision vectors, respectively,
a
1
,a
2
, ,a
m
, b
1
,b
2
, ,b
m
represent the transformations of the processes, and fx denotes
the optimal return function with initial state x. The rest of the paper is organized as follows.
In Section 2, we state the definitions, notions, and a lemma and establish a new fixed point
theorem, which will be used in the rest of the paper. The main results are presented in
ϕ : ϕ : R
−→ R
and ϕ
t
<t for t>0
,
Φ
3
ϕ : ϕ : R
−→ R
is nondecreasing
,
Φ
4
ϕ, ψ
: ϕ, ψ ∈ Φ
d
x, y
∞
k1
1
2
k
·
d
k
x, y
1 d
k
x, y
, 2.1
then d is a metric on X. A sequence {x
n
}
n≥1
in X is said to converge to a point x ∈ X if
d
k
i f has a unique fixed point w ∈ X and lim
n →∞
f
n
x w for any x ∈ X,
ii if, in addition, ϕ ∈ Φ
3
,then
d
k
f
n
x, w
≤ ϕ
n
d
k
x, w
, ∀x ∈ X, n ≥ 1,k≥ 1. 2.3
Proof. Given x ∈ X and k ≥ 1, define c
n
d
k
f
n
, ∀n ≥ 1. 2.4
Since ϕ ∈ Φ
1
∩ Φ
2
,by2.4 we easily conclude that {c
n
}
n≥1
is nonincreasing. It follows that
{c
n
}
n≥1
has a limit c ≥ 0. We claim that c 0. Otherwise, c>0. On account of 2.4 and
ϕ ∈ Φ
1
∩ Φ
2
, we deduce that
c ≤ lim sup
n →∞
ϕ
c
n
≤ ϕ
≥ ε, d
k
f
mi−1
x, f
ni
x
<ε, ∀i ≥ 1, 2.6
which yields that
ε ≤ a
i
≤ d
k
f
mi
x, f
mi−1
x
d
k
f
mi−1
x, f
ni
x
k
f
ni1
x, f
ni
x
≤ c
mi1
ϕ
a
i
c
ni1
,
2.8
for any i ≥ 1. Letting i →∞in 2.8,weseethat
ε ≤ ϕ
ε
<ε. 2.9
This is a contradiction. By completeness of X, d, there exists a point w ∈ X, such that
lim
n →∞
f
n
k1
1
2
k
·
ϕ
d
k
x, y
1 ϕ
d
k
x, y
≤
∞
k1
1
2
k
·
d
k
≤ d
w, f
n
x
d
f
n−1
x, w
−→ 0, as n −→ ∞ ,
2.11
that is, w is a fixed point of f. If f has a fixed point v different from w, then there exists k ≥ 1
such that d
k
w, v > 0. By 2.2, we have
d
k
w, v
d
k
fw,fv
≤ ϕ
w
≤ ϕ
d
k
f
n−1
x, f
n−1
w
≤···≤ϕ
n
d
k
x, w
. 2.13
This completes the proof.
Remark 2.2. Theorem 2.1 extends Theorem 2.1 of Bhakta and Choudhury 6 andTheorem1
of Boyd and Wong 12.
Lemma 2.3 see 11. Let a, b, c, and d be in R,then
opt
{
. 3.1
For any positive integer k and f, g ∈ BBS,let
d
k
f, g
sup
f
x
− g
x
: x ∈
B
0,k
,
d
Φ
1
∩ Φ
2
, such that
C1 for any k ≥ 1 and x, y, u, v ∈
B0,k × D × BBS × BBS,
H
x, y, u
− H
x, y, v
≤ ϕ
d
k
u, v
, 3.3
C2 for any k ≥ 1 and u ∈ BBS,thereexistsαk, u > 0 satisfying
then the functional equation 1.3 possesses a unique solution w ∈ BBS, and {G
n
g}
n≥1
converges
to w for each g ∈ BBS,whereG is defined by
Gg
x
opt
y∈D
p
x, y
H
x, y, g
, ∀
x, g
∈ S × BB
S
. 3.5
x
<p
x, y
H
x, y, h
ε, Gg
x
<p
x, z
H
x, z, g
ε,
Gh
x
≥ p
< max
H
x, y, h
− H
x, y, g
,
H
x, z, h
− H
x, z, g
: x ∈
B
0,k
≤ ϕ
d
k
h, g
ε. 3.9
Similarly, we can show that 3.9 holds for opt
y∈D
inf
y∈D
.Asε → 0
in 3.9,wegetthat
d
k
Gh, Gg
≤ ϕ
d
m
i1
max
p
i
x, y
,
u
i
x, y
≤ A
x, y
,
v
i
x, y
≤ β, ∀
x, y
∈ S × D, 3.12
then the functional equation 1.4 possesses a unique solution w ∈ BBS, and {w
n
}
n≥1
converges to
w for each w
0
∈ BBS,where{w
n
}
w
n−1
a
i
x, y
,
u
i
x, y
v
i
x, y
w
n−1
b
i
x, y
, ∀x ∈ S, n ≥ 1.
3.13
m
i1
opt
p
i
x, y
q
i
x, y
h
a
i
x, y
,u
i
x, y
v
, ∀
x, h
∈ S × BB
S
. 3.16
It follows from C3–C5 and 3.15 that
H
x, y, h
≤
r
x, y
m
x, y
,
u
i
x, y
v
i
x, y
h
b
i
,
u
i
x, y
m
i1
max
q
i
x, y
,
v
≤ A
k
m
i1
max
q
i
x, y
,
v
i
x, y
|
: t ∈
B
0,k
,
3.17
8 Fixed Point Theory and Applications
for any k ≥ 1andx, y, h ∈
B0,k × D × BBS. Consequently, G is a self mapping on BBS.
By Lemma 2.3, C4,andC5, we obtain that for any k ≥ 1andx, y, g, h ∈
B0,k × D ×
BBS × BBS,
H
x, y, g
− H
x, y, h
v
i
x, y
g
b
i
x, y
−
m
i1
opt
p
i
x, y
q
i
x, y
h
i1
max
q
i
x, y
g
a
i
x, y
− h
a
i
x, y
m
i1
max
q
i
x, y
,
v
i
x, y
× max
g
x, y
≤ ϕ
d
k
g,h
,
3.18
where ϕtβt for t ∈ R
.Thus,Theorem 3.3 follows from Theorem 3.1. This completes the
proof.
Remark 3.4. Theorem 2 of Bellman 1, page 121, the result of Bellman and Roosta 5, page
545, Theorem 3.3 of Bhakta and Choudhury 6, and Theorems 3.3 and 3.4 of Liu 8 are
special cases of Theorem 3.3. The example below shows that Theorem 3.3 extends properly
the results in 1, 5, 6, 8.
Example 3.5. Let X Y S R and D R
−
.Putm 2, β 2/3, and Ak3k
3
for any
k ≥ 1. It follows from Theorem 3.3 that the functional equation
f
2
sin
2
x − y x
2
3 x
2
y
2
f
x cos
x
2
y
2
,
x
2
ln
1
y
2
x − y
2
opt
x
3
y
1
|
x
|
y
cos
2
xy − x
2
xy
4 x
2
y
2
f
x
1 2
x
2
y
, ∀x ∈ S
3.19
possesses a unique solution w ∈ BBS. However, the results in 1, 5, 6, 8 are not applicable.
Fixed Point Theory and Applications 9
Theorem 3.6. Let r, p
i
,q
i
,u
i
,v
i
: S×D → R and a
i
,b
i
C9 the sequence {w
n
}
n≥1
defined by
w
0
x
opt
y∈D
r
x, y
m
i1
opt
p
i
x, y
,u
i
x, y
w
n−1
a
i
x, y
,
u
i
x, y
v
i
x, y
w
n−1
b
i
x, y
C11 w is unique with respect to condition (C10).
Proof. Let H and G be defined by 3.15 and 3.16, respectively. We now claim that
ϕ
t
<t, ∀t>0. 3.21
If not, then there exists some t>0 such that ϕt ≥ t. On account of ϕ, ψ ∈ Φ
4
,weknowthat
for any n ≥ 1,
ψ
ϕ
n
t
≥ ψ
ϕ
n−1
t
≥···≥ψ
t
a
i
x, y
,
b
i
x, y
: i ∈
{
1, 2, ,m
}
≤ ϕ
x
i
x, y
: i ∈
{
1, 2, ,m
}
≤ C
k, h
, ∀
x, y
∈
B
0,k
× D.
3.25
In view of C6, 3.16,and3.25, we derive that for any x ∈
B0,k,
|
Gh
≤ sup
y∈D
r
x, y
m
i1
max
p
i
x, y
v
i
x, y
h
b
i
x, y
≤ sup
y∈D
r
x, y
i1
max
q
i
x, y
,
v
i
x, y
max
h
3.26
which yields that G maps BBS into itself. Given ε>0, k ≥ 1, x ∈
B0,k,andh, g ∈ BBS,
suppose that opt
y∈D
sup
y∈D
, then there exist y, z ∈ D such that
Gh
x
<H
x, y, h
ε, Gg
x
<H
x, z, g
ε,
Gh
x
≥ H
H
x, y, h
− H
x, y, g
,
H
x, z, h
− H
x, z, g
ε
≤ max
m
,
v
i
x, y
h
b
i
x, y
− g
b
i
x, y
,
,
|
v
i
x, z
|
h
b
i
x, z
− g
b
i
x, z
i1
max
q
i
x, z
,
|
v
i
x, z
|
d
k
h, g
ε
≤ d
≤ d
k
h, g
, 3.30
which implies that
d
Gh, Gg
∞
k1
1
2
k
·
d
k
Gh, Gg
1 d
k
Gh, Gg
|
≤
n
j0
ψ
ϕ
j
x
, ∀x ∈ S. 3.32
12 Fixed Point Theory and Applications
In terms of C6 and C9,weobtainthat
|
w
0
x
|
≤ sup
y∈D
≤ ψ
x
, ∀x ∈ S, 3.33
which means that 3.32 holds for n 0. Suppose that 3.32 holds for some n ≥ 0. It follows
from C6–C8 and 3.25 that
|
w
n1
x
|
opt
y∈D
r
x, y
v
i
x, y
w
n
b
i
x, y
≤ sup
y∈D
r
x, y
w
n
a
i
x, y
,
u
i
x, y
v
i
x, y
p
i
x, y
,
u
i
x, y
m
i1
max
q
,
w
n
b
i
x, y
≤ ψ
x
sup
y∈D
max
w
n
sup
y∈D
max
⎧
⎨
⎩
n
j0
ψ
ϕ
j
a
i
x, y
,
n
ϕ
j
x
.
3.34
Therefore, 3.32 holds for any n ≥ 0.
Fixed Point Theory and Applications 13
Next, we prove that {w
n
}
n≥0
is a Cauchy sequence in BBS.Givenε>0, k ≥ 1, n ≥ 1,
j ≥ 1, and x
0
∈ B0,k, suppose that opt
y∈D
sup
y∈D
. We select that y, z ∈ D with
w
n
x
0
i
x
0
,y
,
u
i
x
0
,y
v
i
x
0
,y
w
n−1
b
i
x
0
,y
i
x
0
,z
w
nj−1
a
i
x
0
,z
,
u
i
x
0
,z
v
i
x
0
,z
i1
opt
p
i
x
0
,z
q
i
x
0
,z
w
n−1
a
i
x
0
,z
,
u
i
≥ r
x
0
,y
m
i1
opt
p
i
x
0
,y
q
i
x
0
,y
w
nj−1
a
.
3.35
According to C6–C8 and 3.35, we have
w
nj
x
0
− w
n
x
0
< max
m
i1
x
0
,z
v
i
x
0
,z
w
nj−1
b
i
x
0
,z
−
m
i1
opt
p
i
v
i
x
0
,z
w
n−1
b
i
x
0
,z
}
,
m
i
x
0
,y
v
i
x
0
,y
w
nj−1
b
i
x
0
,y
−
m
i1
opt
p
v
i
x
0
,y
w
n−1
b
i
x
0
,y
2
−1
ε
14 Fixed Point Theory and Applications
≤ max
a
i
x
0
,z
,
|
v
i
x
0
,z
|
w
nj−1
b
i
x
0
w
nj−1
a
i
x
0
,y
− w
n−1
a
i
x
0
,y
,
v
2
−1
ε
≤ max
m
i1
max
q
i
x
0
,z
,
|
v
i
,
w
nj−1
b
i
x
0
,z
− w
n−1
b
i
x
0
,z
,
m
w
nj−1
a
i
x
0
,y
− w
n−1
a
i
x
0
,y
,
w
nj−1
w
nj−1
a
i
x
0
,z
− w
n−1
a
i
x
0
,z
,
w
nj−1
b
i
a
i
x
0
,y
− w
n−1
a
i
x
0
,y
,
w
nj−1
b
i
x
0
− w
n−1
x
1
2
−1
ε,
3.36
for some x
1
∈{a
i
x
0
,y
1
,b
i
x
0
,y
1
: i ∈{1, 2, ,m}} and y
1
∈{y, z}. In a similar way, we
− w
n−1
x
1
<
w
nj−2
x
2
− w
n−2
x
2
2
−2
ε,
2
−3
ε,
.
.
.
w
j1
x
n−1
− w
1
x
n−1
<
w
j
x
<
w
j
x
n
− w
0
x
n
n
i1
2
−i
ε
<
w
ψ
x
n
ε
≤
∞
in−1
ψ
ϕ
i
k
ε,
3.38
which implies that
d
k
w
nj
in−1
ψ
ϕ
i
k
, 3.40
which means that {w
n
}
n≥0
is a Cauchy sequence in BBS,d because
∞
n0
ψϕ
n
t < ∞ for
each t>0. Let lim
n →∞
w
n
w ∈ BBS. By the nonexpansivity of G,wegetthat
d
w, Gw
n≥1
⊂ D,andx
n
∈
{a
i
x
n−1
,y
n
,b
i
x
n−1
,y
n
: i ∈{1, 2, ,m}} for n ≥ 1, set k 1 x
0
. It is easy to verify that
there exists a positive integer m satisfying
d
k
w, w
n
∞
in
b
i
x
n−1
,y
n
: i ∈
{
1, 2, ,m
}
≤ ϕ
x
n−1
≤···≤ϕ
n
x
0
|
|
w
n
x
n
|
≤ d
k
w, w
n
n
i0
ψ
ϕ
i
x
n
opt
y∈D
sup
y∈D
, then there are y, z ∈ S satisfying
w
x
0
<r
x
0
,y
m
i1
opt
p
i
x
0
,y
q
w
b
i
x
0
,y
2
−1
ε,
h
x
0
<r
x
0
,z
m
i1
opt
p
v
i
x
0
,z
h
b
i
x
0
,z
}
2
−1
ε,
w
x
0
≥ r
x
0
,z
,
u
i
x
0
,z
v
i
x
0
,z
w
b
i
x
0
,z
}
,
h
x
0
i
x
0
,y
,
u
i
x
0
,y
v
i
x
0
,y
h
b
i
x
0
,y
m
i1
opt
p
i
x
0
,y
q
i
x
0
,y
w
a
i
x
0
,y
,y
q
i
x
0
,y
h
a
i
x
0
,y
,u
i
x
0
,y
v
i
x
0
x
0
,z
w
a
i
x
0
,z
,u
i
x
0
,z
v
i
x
0
,z
w
0
,z
,
u
i
x
0
,z
v
i
x
0
,z
h
b
i
x
0
,z
}|
2
− h
a
i
x
0
,y
,
v
i
x
0
,y
w
b
i
,z
|
w
a
i
x
0
,z
− h
a
i
x
0
,z
|
,
|
v
i
x
i1
max
q
i
x
0
,y
,
v
i
x
0
,y
,
m
w
a
i
x
0
,y
−h
a
i
x
0
,y
,
w
b
i
x
x
0
,z
|
,
|
w
b
i
x
0
,z
− h
b
i
x
0
,z
|
: i ∈
{
1, 2, ,m
}}
,b
i
x
j−1
,y
j
: i ∈
{1, 2, ,m}} for j ∈{2, 3, ,n} satisfying
|
w
x
1
− h
x
1
|
<
|
w
x
2
− h
x
|
2
−3
ε,
.
.
.
|
w
x
n−1
− h
x
n−1
|
<
|
w
x
n
− h
x
n
n
|
ε, 3.48
which yields that
|
w
x
0
− h
x
0
|
≤ ε, 3.49
by letting n →∞. Similarly, 3.49 also holds for opt
y∈D
inf
y∈D
.Asε → 0
, we know that
wx
0
hx
0
. This completes the proof.
opt
y∈D
x
4
2 sin
1 x
2
y
2
max
x
4
1 xy
x sin
x y
2 4x y
f
x
2
2 2x y
x − y
1 x 4y
f
x
3
1 2x
2
sin
x
2
y
2
,
x
5
y
1 xy
cos
xy 2x − y
4 x
y
4 R. Bellman and E. S. Lee, “Functional equations in dynamic programming,” Aequationes Mathematicae,
vol. 17, no. 1, pp. 1–18, 1978.
5 R. Bellman and 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.
6 P. C. Bhakta and 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.
7 P. C. Bhakta and S. Mitra, “Some existence theorems for functional equations arising in dynamic
programming,” Journal of Mathematical Analysis and Applications, vol. 98, no. 2, pp. 348–362, 1984.
8 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.
9 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.
10 Z. Liu, “Compatible mappings and fixed points,” Acta Scientiarum Mathematicarum, vol. 65, no. 1-2,
pp. 371–383, 1999.
11 Z. Liu and 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.
12 D. W. Boyd and J. S. W. Wong, “On nonlinear contractions,” Proceedings of the American Mathematical
Society, vol. 20, pp. 458–464, 1969.
Copyright: Tài liệu đại học ©