# An Iterative Algorithm for a Hierarchical Problem

Authors: Yonghong Yao; Yeol Je Cho; Pei-Xia Yang
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

A general hierarchical problem has been considered, and an explicit algorithm has been presented for solving this hierarchical problem. Also, it is shown that the suggested algorithm converges strongly to a solution of the hierarchical problem.


---

## Body

## 1. Introduction

LetH be a real Hilbert space with inner product 〈·,·〉 and norm ∥·∥, respectively. Let C be a nonempty closed convex subset of H. The hierarchical problem is of finding x̃∈Fix(T) such that(1.1)〈Sx̃-x̃,x-x̃〉≤0,∀x∈Fix⁡(T),
where S,T are two nonexpansive mappings and Fix(T) is the set of fixed points of T. Recently, this problem has been studied by many authors (see, e.g., [1–15]). The main reason is that this problem is closely associated with some monotone variational inequalities and convex programming problems (see [16–19]).Now, we briefly recall some historic results which relate to the problem (1.1).For solving the problem (1.1), in 2006, Moudafi and Mainge [1] first introduced an implicit iterative algorithm:(1.2)xt,s=sQ(xt,s)+(1-s)[tS(xt,s)+(1-t)T(xt,s)]
and proved that the net {xt,s} defined by (1.2) strongly converges to xt as s→0, where xt satisfies xt=projFix(Pt)Q(xt), where Pt:C→C is a mapping defined by (1.3)Pt(x)=tS(x)+(1-t)T(x),∀x∈C,t∈(0,1),
or, equivalently, xt is the unique solution of the quasivariational inequality (1.4)0∈(I-Q)xt+NFix⁡(Pt)(xt),
where the normal cone to Fix(Pt), NFix(Pt), is defined as follows: (1.5)NFix⁡(Pt):x⟶{{u∈H:〈y-x,u〉≤0},ifx∈Fix⁡(Pt),∅,otherwise.Moreover, ast→0, the net {xt} in turn weakly converges to the unique solution x∞ of the fixed point equation x∞=projΩQ(x∞) or, equivalently, x∞ is the unique solution of the variational inequality (1.6)0∈(I-Q)x∞+NΩ(x∞).Recently, Moudafi [2] constructed an explicit iterative algorithm:(1.7)xn+1=(1-δn)xn+δn(σnSxn+(1-σn)Txn),∀n≥0,
where {δn} and {σn} are two real numbers in (0,1). By using this iterative algorithm, Moudafi [2] only proved a weak convergence theorem for solving the problem (1.1).In order to obtain a strong convergence result, Mainge and Moudafi [3] further introduced the following iterative algorithm:(1.8)xn+1=(1-δn)Qxn+δn[σnSxn+(1-σn)Txn],∀n≥0,
where {δn} and {σn} are two real numbers in (0,1), and proved that, under appropriate conditions, the iterative sequence {xn} generated by (1.8) has strong convergence.Subsequently, some authors have studied some algorithms on hierarchical fixed problems (see, e.g., [4–15]).Motivated and inspired by the results in the literature, in this paper, we consider a general hierarchical problem of findingx̃∈Fix(T) such that, for any n≥1,(1.9)〈Wnx̃-x̃,x-x̃〉≤0,∀x∈Fix⁡(T),
where Wn is the W-mapping defined by (2.3) below and T is a nonexpansive mapping, and introduce an explicit iterative algorithm which converges strongly to a solution x̃ of the hierarchical problem (1.9).


## 2. Preliminaries

LetC a nonempty closed convex subset of a real Hilbert space H. Recall that a mapping Q:C→C is said to be contractive if there exists a constant γ∈(0,1) such that (2.1)‖Qx-Qy‖≤γ‖x-y‖,∀x,y∈C.A mappingT:C→C is called nonexpansive if(2.2)‖Tx-Ty‖≤‖x-y‖,∀x,y∈C.Forward, we useFix(T) to denote the fixed points set of T.Let{Ti}i=1∞:C→C be an infinite family of nonexpansive mappings and {ξi}i=1∞ a real number sequence such that 0≤ξi≤1 for each i≥1.For eachn≥1, define a mapping Wn:C→C as follows:(2.3)Un,n+1=I,Un,n=ξnTnUn,n+1+(1-ξn)I,Un,n-1=ξn-1Tn-1Un,n+(1-ξn-1)I,⋯Un,k=ξkTkUn,k+1+(1-ξk)I,Un,k-1=ξk-1Tk-1Un,k+(1-ξk-1)I,⋯Un,2=ξ2T2Un,3+(1-ξ2)I,Wn=Un,1=ξ1T1Un,2+(1-ξ1)I.SuchWn is called the W-mapping generated by {Ti}i=1∞ and {ξi}i=1∞.Lemma 2.1 (see [20]).
LetC be a nonempty closed convex subset of a real Hilbert space H. Let {Ti}i=1∞ be an infinite family of nonexpansive mappings of C into itself with ⋂n=1∞Fix(Tn)≠∅. Let ξ1,ξ2,… be real numbers such that 0<ξi≤b<1 for each i≥1. Then one has the following results: (1)
for anyx∈C and k≥1, the limit limn→∞Un,kx exists;(2)
Fix(W)=⋂n=1∞Fix(Tn).Using Lemma  3.1 in [21], we can define a mapping W of C into itself by Wx=limn→∞Wnx=limn→∞Un,1x for all x∈C. Thus we have the following.Lemma 2.2 (see [21]).
If{xn} is a bounded sequence in C, then one has
(2.4)lim⁡n→∞‖Wxn-Wnxn‖=0.Lemma 2.3 (see [22]).
LetC be a nonempty closed convex of a real Hilbert space H and T:C→C be nonexpansive mapping. Then T is demiclosed on C, that is, if xn⇀x∈C and xn-Txn→0, then x=Tx.Lemma 2.4 (see [23]).
Assume{an} is a sequence of nonnegative real numbers such that
(2.5)an+1≤(1-γn)an+δnγn+ηn,∀n≥1,
where {γn} is a sequence in (0,1) and {δn},{ηn} are two sequences such that  (i)
∑n=1∞γn=∞;(ii)
limsupn→∞δn≤0 or ∑n=1∞|δnγn|<∞;(iii)
∑n=1∞|ηn|<∞.
Thenlimn→∞an=0.


## 3. Main Results

In this section, we introduce our algorithm and give its convergence analysis.Algorithm 3.1.
LetC be a nonempty closed convex subset of a real Hilbert space H and {Tn}n=1∞ be infinite family of nonexpansive mappings of C into itself. Let Q:C→C be a contraction with coefficient γ∈[0,1). For any x0∈C, let {xn} the sequence generated iteratively by
(3.1)xn+1=αnWnxn+(1-αn)T(βnQxn+(1-βn)xn),∀n≥0,
where {αn},{βn} are two real numbers in (0,1) and Wn is the W-mapping defined by (2.3).Now, we give the convergence analysis of the algorithm.Theorem 3.2.
LetC be a nonempty closed convex subset of a real Hilbert space H and {Tn}n=1∞ be an infinite family of nonexpansive mappings of C into itself. Let Q:C→C be a contraction with coefficient γ∈[0,1). Assume that the set Ω of solutions of the hierarchical problem (1.9) is nonempty. Let {αn},{βn} be two real numbers in (0,1) and {xn} the sequence generated by (3.1). Assume that the sequence {xn} is bounded and (i)
limn→∞αn=0 and limn→∞(βn/αn)=0;(ii)
∑n=0∞βn=∞;(iii)
limn→∞(1/βn)|(1/αn)-(1/αn-1)|=0 and limn→∞(∏i=1n-1ξi/αnβn)=limn→∞(1/αn)|1-(βn-1/βn)|=0.
Thenlimn→∞(∥xn+1-xn∥/αn)=0 and every weak cluster point of the sequence {xn} solves the following variational inequality(3.2)x̃∈Ω,〈(I-Q)x̃,x-x̃〉≥0,∀x∈Ω.Proof.
Setyn=βnQxn+(1-βn)xn for each n≥0. Then we have
(3.3)yn-yn-1=βnQxn+(1-βn)xn-βn-1Qxn-1-(1-βn-1)xn-1=βn(Qxn-Qxn-1)+(βn-βn-1)Qxn-1+(1-βn)(xn-xn-1)+(βn-1-βn)xn-1.
It follows that
(3.4)‖yn-yn-1‖≤γβn‖xn-xn-1‖+(1-βn)‖xn-xn-1‖+|βn-βn-1|(‖Qxn-1‖+‖xn-1‖)=[1-(1-γ)βn]‖xn-xn-1‖+|βn-βn-1|(‖Qxn-1‖+‖xn-1‖).
From (3.1), we have
(3.5)xn+1-xn=αnWnxn+(1-αn)Tyn-αn-1Wn-1xn-1-(1-αn-1)Tyn-1=αn(Wnxn-Wnxn-1)+(αn-αn-1)Wnxn-1+αn-1(Wnxn-1-Wn-1xn-1)+(1-αn)(Tyn-Tyn-1)+(αn-1-αn)Tyn-1.
Then we obtain
(3.6)‖xn+1-xn‖≤αn‖Wnxn-Wnxn-1‖+(1-αn)‖Tyn-Tyn-1‖+|αn-αn-1|(‖Wnxn-1‖+‖Tyn-1‖)+αn-1‖Wnxn-1-Wn-1xn-1‖≤αn‖xn-xn-1‖+(1-αn)‖yn-yn-1‖+|αn-αn-1|(‖Wnxn-1‖+‖Tyn-1‖)+αn-1‖Wnxn-1-Wn-1xn-1‖.
From (2.3), since Ti and Un,i are nonexpansive, we have
(3.7)‖Wnxn-1-Wn-1xn-1‖=‖ξ1T1Un,2xn-1-ξ1T1Un-1,2xn-1‖≤ξ1‖Un,2xn-1-Un-1,2xn-1‖=ξ1‖ξ2T2Un,3xn-1-ξ2T2Un-1,3xn-1‖≤ξ1ξ2‖Un,3xn-1-Un-1,3xn-1‖≤⋯≤ξ1ξ2⋯ξn-1‖Un,nxn-1-Un-1,nxn-1‖≤M1∏i=1n-1ξi,
where M1 is a constant such that supn≥1{∥Un,nxn-1-Un-1,nxn-1∥}≤M1. Substituting (3.4) and (3.7) into (3.6), we get
(3.8)‖xn+1-xn‖≤αn‖xn-xn-1‖+(1-αn)[1-(1-γ)βn]‖xn-xn-1‖+|βn-βn-1|(‖Qxn-1‖+‖xn-1‖)+|αn-αn-1|(‖Wnxn-1‖+‖Tyn-1‖)+αn-1M1∏i=1n-1ξi=[1-(1-γ)βn(1-αn)]‖xn-xn-1‖+|βn-βn-1|(‖Qxn-1‖+‖xn-1‖)+|αn-αn-1|(‖Wnxn-1‖+‖Tyn-1‖)+αn-1M1∏i=1n-1ξi.
Therefore, it follows that
(3.9)‖xn+1-xn‖αn≤[1-(1-γ)βn(1-αn)]‖xn-xn-1‖αn+|βn-βn-1|αn(‖Qxn-1‖+‖xn-1‖)+|αn-αn-1|αn(‖Wnxn-1‖+‖Tyn-1‖)+αn-1M1∏i=1n-1ξiαn=[1-(1-γ)βn(1-αn)]‖xn-xn-1‖αn-1+[1-(1-γ)βn(1-αn)](‖xn-xn-1‖αn-‖xn-xn-1‖αn-1)+|βn-βn-1|αn(‖Qxn-1‖+‖xn-1‖)+|αn-αn-1|αn(‖Wnxn-1‖+‖Tyn-1‖)+αn-1M1∏i=1n-1ξiαn≤[1-(1-γ)βn(1-αn)]‖xn-xn-1‖αn-1+(|1αn-1αn-1|+|αn-αn-1|αn+|βn-βn-1|αn+∏i=1n-1ξiαn)M=[1-(1-γ)βn(1-αn)]‖xn-xn-1‖αn-1+(1-γ)βn(1-αn)×{M(1-γ)(1-αn)(1βn|1αn-1αn-1|+1βn|αn-αn-1|αn+1βn|βn-βn-1|αn+∏i=1n-1ξiαnβn)},
where M is a constant such that
(3.10)sup⁡n≥1{M1,‖xn-xn-1‖,(‖Wnxn-1‖+‖Tyn-1‖),(‖Qxn-1‖+‖xn-1‖)}≤M.
From (iii), we note that limn→∞(1/αn-1)|αn-αn-1/βnαn|=0, which implies that
(3.11)lim⁡n→∞1βn|αn-αn-1|αn=0.
Thus it follows from (iii) and (3.11) that
(3.12)lim⁡n→∞(1βn|1αn-1αn-1|+1βn|αn-αn-1|αn+1βn|βn-βn-1|αn+∏i=1n-1ξiαnβn)=0.
Hence, applying Lemma 2.4 to (3.9), we immediately conclude that
(3.13)lim⁡n→∞‖xn+1-xn‖αn=0.
This implies that
(3.14)lim⁡n→∞‖xn+1-xn‖=0.
Thus, from (3.1) and (3.14), we have
(3.15)lim⁡n→∞‖xn-Tyn‖=0.
At the same time, we note that
(3.16)yn-xn=βn(Qxn-xn)⟶0.
Hence we get
(3.17)lim⁡n→∞‖yn-Tyn‖=0.
Since the sequence {xn} is bounded, {yn} is also bounded. Thus there exists a subsequence of {yn}, which is still denoted by {yn} which converges weakly to a point x̃∈H. Therefore, x̃∈Fix(T) by (3.17) and Lemma 2.3. By (3.1), we observe that
(3.18)xn+1-xn=αn(Wnxn-xn)+(1-αn)(Tyn-yn)+(1-αn)βn(Qxn-xn),
that is,
(3.19)xn-xn+1αn=(I-Wn)xn+1-αnαn(I-T)yn+βn(1-αn)αn(I-Q)xn.
Set zn=(xn-xn+1)/αn for each n≥1, that is,
(3.20)zn=(I-Wn)xn+1-αnαn(I-T)yn+βn(1-αn)αn(I-Q)xn.
Using monotonicity of I-T and I-Wn, we derive that, for all u∈Fix(T),
(3.21)〈zn,xn-u〉=〈(I-Wn)xn,xn-u〉+1-αnαn〈(I-T)yn-(I-T)u,yn-u〉+1-αnαn〈(I-T)yn,xn-yn〉+βn(1-αn)αn〈(I-Q)xn,xn-u〉≥〈(I-Wn)u,xn-u〉+βn(1-αn)αn〈(I-Q)xn,xn-u〉+(1-αn)βnαn〈(I-T)yn,xn-Qxn〉=〈(I-W)u,xn-u〉+〈(W-Wn)u,xn-u〉+βn(1-αn)αn〈(I-Q)xn,xn-u〉+(1-αn)βnαn〈(I-T)yn,xn-Qxn〉.
But, since zn→0,βn/αn→0 and limn→∞∥Wnu-Wu∥=0 (by Lemma 2.2), it follows from the above inequality that
(3.22)limsup⁡n→∞〈(I-W)u,xn-u〉≤0,∀u∈Fix⁡(T).
This suffices to guarantee that ωw(xn)⊂Ω. As a matter of fact, if we take any x*∈ωw(xn), then there exists a subsequence {xnj} of {xn} such that xnj⇀x*. Therefore, we have
(3.23)〈(I-W)u,x*-u〉=lim⁡j→∞〈(I-W)u,xnj-u〉≤0,∀u∈Fix⁡(T).
Note that x*∈Fix(T). Hence x* solves the following problem:
(3.24)x*∈Fix⁡(T),〈(I-W)u,x*-u〉≤0,∀u∈Fix⁡(T).
It is obvious that this is equivalent to the problem (1.9) since Wn→W uniformly in any bounded set (by Lemma 2.2). Thus x*∈Ω.
Letx̃ be the unique solution of the variational inequality (3.2). Now, take a subsequence {xni} of {xn} such that(3.25)limsup⁡n→∞〈(I-Q)x̃,xn-x̃〉=lim⁡i→∞〈(I-Q)x̃,xni-x̃〉.
Without loss of generality, we may further assume that xni⇀x¯. Then x¯∈Ω. Therefore, we have
(3.26)limsup⁡n→∞〈(I-Q)x̃,xn-x̃〉=〈(I-Q)x̃,x¯-x̃〉≥0.
This completes the proof.Theorem 3.3.
LetC be a nonempty closed convex subset of a real Hilbert space H. Let {Tn}n=1∞ be infinite family of nonexpansive mappings of C into itself. Let Q:C→C be a contraction with coefficient γ∈[0,1). Assume that the set Ω of solutions of the hierarchical problem (1.9) is nonempty. Let {αn},{βn} be two real numbers in (0,1) and {xn} the sequence generated by (3.1). Assume that the sequence {xn} is bounded and  (i)
limn→∞αn=0, limn→∞βn/αn=0 and limn→∞αn2/βn=0;(ii)
∑n=0∞βn=∞;(iii)
limn→∞(1/βn)|(1/αn)-(1/αn-1)|=0 and limn→∞∏i=1n-1ξi/αnβn = limn→∞(1/αn)|1-(βn-1/βn)| = 0;(iv)
there exists a constantk>0 such that ∥x-Tx∥≥kDist(x,Fix(T)), where(3.27)Dist(x,Fix⁡(T))=inf⁡y∈Fix⁡(T)‖x-y‖.
Then the sequence {xn} defined by (3.1) converges strongly to a point x̃∈Fix(T), which solves the variational inequality problem (3.2).Proof.
From (3.1), we have
(3.28)xn+1-x̃=αn(Wnxn-Wnx̃)+αn(Wnx̃-x̃)+(1-αn)(Tyn-x̃).
Thus we have
(3.29)‖xn+1-x̃‖2≤‖αn(Wnxn-Wnx̃)+(1-αn)(Tyn-x̃)‖2+2αn〈Wnx̃-x̃,xn+1-x̃〉≤(1-αn)‖Tyn-x̃‖2+αn‖Wnxn-Wnx̃‖2+2αn〈Wnx̃-x̃,xn+1-x̃〉≤(1-αn)‖yn-x̃‖2+αn‖xn-x̃‖2+2αn〈Wnx̃-x̃,xn+1-x̃〉.
At the same time, we observe that
(3.30)‖yn-x̃‖2=‖(1-βn)(xn-x̃)+βn(Qxn-Qx̃)+βn(Qx̃-x̃)‖2≤‖(1-βn)(xn-x̃)+βn(Qxn-Qx̃)‖2+2βn〈Qx̃-x̃,yn-x̃〉≤(1-βn)‖xn-x̃‖2+βn‖Qxn-Qx̃‖2+2βn〈Qx̃-x̃,yn-x̃〉≤(1-βn)‖xn-x̃‖2+βnγ2‖xn-x̃‖2+2βn〈Qx̃-x̃,yn-x̃〉=[1-(1-γ2)βn]‖xn-x̃‖2+2βn〈Qx̃-x̃,yn-x̃〉.
Substituting (3.30) into (3.29), we get
(3.31)‖xn+1-x̃‖2≤αn‖xn-x̃‖2+(1-αn)[1-(1-γ2)βn]‖xn-x̃‖2+2βn(1-αn)〈Qx̃-x̃,yn-x̃〉+2αn〈Wnx̃-x̃,xn+1-x̃〉=[1-(1-γ2)βn(1-αn)]‖xn-x̃‖2+2βn(1-αn)〈Qx̃-x̃,yn-x̃〉+2αn〈Wnx̃-x̃,xn+1-x̃〉=[1-(1-γ2)βn(1-αn)]‖xn-x̃‖2+(1-γ2)βn(1-αn)×{21-γ2〈Qx̃-x̃,yn-x̃〉+2(1-γ2)(1-αn)×αnβn〈Wnx̃-x̃,xn+1-x̃〉}.
By Theorem 3.2, we note that every weak cluster point of the sequence {xn} is in Ω. Since yn-xn→0, then every weak cluster point of {yn} is also in Ω. Consequently, since x̃=projΩ(Qx̃), we easily have
(3.32)limsup⁡n→∞〈Qx̃-x̃,yn-x̃〉≤0.
On the other hand, we observe that(3.33)〈Wnx̃-x̃,xn+1-x̃〉=〈Wnx̃-x̃,projFix⁡(T)xn+1-x̃〉+〈Wnx̃-x̃,xn+1-projFix⁡(T)xn+1〉.
Since x̃ is a solution of the problem (1.9) and projFix(T)xn+1∈Fix(T), we have
(3.34)〈Wnx̃-x̃,projFix⁡(T)xn+1-x̃〉≤0.
Thus it follows that
(3.35)〈Wnx̃-x̃,xn+1-x̃〉≤〈Wnx̃-x̃,xn+1-projFix⁡(T)xn+1〉≤‖Wnx̃-x̃‖‖xn+1-projFix⁡(T)xn+1‖=‖Wnx̃-x̃‖×Dist(xn+1,Fix⁡(T))≤1k‖Wnx̃-x̃‖‖xn+1-Txn+1‖.
We note that
(3.36)‖xn+1-Txn+1‖≤‖xn+1-Txn‖+‖Txn-Txn+1‖≤αn‖Wnxn-Txn‖+(1-αn)‖Tyn-Txn‖+‖xn+1-xn‖≤αn‖Wnxn-Txn‖+‖yn-xn‖+‖xn+1-xn‖≤αn‖Wnxn-Txn‖+βn‖Qxn-xn‖+‖xn+1-xn‖.
Hence we have
(3.37)αnβn〈Wnx̃-x̃,xn+1-x̃〉≤αn2βn(1k‖Wnx̃-x̃‖‖Wnxn-Txn‖)+αn(1k‖Wnx̃-x̃‖‖Qxn-xn‖)+αn2βn‖xn+1-xn‖αn(1k‖Wnx̃-x̃‖).
From Theorem 3.2, we have limn→∞∥xn+1-xn∥/αn=0. At the same time, we note that {(1/k)∥Wnx̃-x̃∥∥Wnxn-Txn∥}, {(1/k)∥Wnx̃-x̃∥∥Qxn-xn∥}, and {(1/k)∥Wnx̃-x̃∥} are all bounded. Hence it follows from (i) and the above inequality that
(3.38)limsup⁡n→∞αnβn〈Wnx̃-x̃,xn+1-x̃〉≤0.
Finally, by (3.31)–(3.38) and Lemma 2.4, we conclude that the sequence {xn} converges strongly to a point x̃∈Fix(T). This completes the proof.Remark 3.4.
In the present paper, we consider the hierarchical problem (1.9) which includes the hierarchical problem (1.1) as a special case.
From the above discussion, we can easily deduce the following result.Algorithm 3.5.
LetC be a nonempty closed convex subset of a real Hilbert space H and S a nonexpansive mapping of C into itself. Let Q:C→C be a contraction with coefficient γ∈[0,1). For any x0∈C, let{xn} the sequence generated iteratively by
(3.39)xn+1=αnSxn+(1-αn)T(βnQxn+(1-βn)xn),∀n≥0,
where {αn},{βn} are two real numbers in (0,1).Corollary 3.6.
LetC be a nonempty closed convex subset of a real Hilbert space H. Let S:C→C be a nonexpansive mapping. Let Q:C→C be a contraction with coefficient γ∈[0,1). Assume that the set Ω′ of solutions of the hierarchical problem (1.1) is nonempty. Let {αn},{βn} be two real numbers in (0,1) and {xn} the sequence generated by (3.1). Assume that the sequence {xn} is bounded and  (i)
limn→∞αn=0, limn→∞βn/αn=0 and limn→∞αn2/βn=0;(ii)
∑n=0∞βn=∞;(iii)
limn→∞(1/βn)|(1/αn)-(1/αn-1)|=0 and limn→∞(1/αn)|1-(βn-1/βn)|=0;(iv)
there exists a constantk>0 such that ∥x-Tx∥≥kDist(x,Fix(T)), where(3.40)Dist(x,Fix⁡(T))=inf⁡y∈Fix⁡(T)‖x-y‖.
Then the sequence {xn} defined by (3.39) converges strongly to a point x̃∈Fix(T), which solves the hierarchical problem (1.1).



---

*Source: 320421-2011-12-29.xml*