We propose synchronal algorithm and cyclic algorithm based on the general iterative method for solving a hierarchical fixed point problem. Under suitable parameters, the iterative sequence converges strongly to a common fixed point of N nonexpansive mappings and also the unique solution of a variational inequality. The results presented in this paper improve and extend the corresponding results reported recently by some authors. Furthermore, a numerical example is given to demonstrate the effectiveness of our iterative schemes.

1. Introduction

Let H be a real Hilbert space with an inner product 〈, 〉 and its induced norm ∥·∥. Let C be a nonempty, closed, and convex subset of H.

Let T : C → H be a nonlinear mapping; we denote the set of fixed points of T by Fix (T) (i.e., Fix (T) = {x ∈ C : Tx = x}). A mapping T : C → H is called k-Lipschitzian continuous if there exists a constant k > 0 such that

()

In particular, T is said to be a nonexpansive mapping if k = 1. A mapping B is called η-strongly monotone on C, if there exists a constant η > 0 such that

()

A variational inequality (short for VI) is formulated as finding a point x^* ∈ C such that

()

If B is a monotone operator, then VI (3) is known as a monotone variational inequality. If the set C is replaced by the set of Fix (T) of fixed points of a mapping T, then the VI (3) is called a hierarchical variational inequality problem.

Many practical problems in applied sciences such as signal processing [1], beamforming [2], and power control [3] are formulated as the monotone variational inequality with a fixed point constrained. In recent years, several authors paid attention toward this kind of problem. Some methods have been proposed to solve the hierarchical fixed point problems and variational inequalities; see for instance [4–10] and the references therein.

In 2010, Tian [11] proposed a general iterative method and revealed the inner contact of the Yamada’s algorithm [12] and viscosity iterative algorithm; then he obtained the following result in a real Hilbert space.

Theorem 1. Let x_n be generated by algorithm x_n+1 = α_nγf(x_n)+(I − α_nμA)Tx_n with the sequence {α_n} of parameters satisfying conditions (C1)–(C3):

(C1)
α_n → 0,
(C2)
,
(C3)
either or lim _n→∞(α_n+1/α_n) = 1.

Then x_n converges strongly to a fixed point

of T which solves the variational inequality

()

Recently, Yao et al. [10] investigated an iterative method for solving a hierarchical fixed point problem by

()

where S, T are nonexpansive mapping with Fix (T) ≠ ∅ and f is a contraction; the sequence converges strongly to the unique solution of the variational inequality

()

Very recently, on this basis, Wang and Xu [8] introduced a new modified iterative method for solving a hierarchical fixed point problem. To be more precise, they proposed the following algorithm:

()

where S, T are nonexpansive mappings with Fix (T) ≠ ∅, U is a Lipschitzian mapping, and F is a Lipschitzian and strongly monotone operator. They proved the sequence generated by the above algorithm converges strongly to the unique solution of the variational inequality

()

On the other hand, Tian and Di [13] established a synchronal algorithm and a cyclic algorithm for fixed point problems and variational inequalities. In 2012, Ceng et al. [4] proposed an iterative method to solve a special form of VI (3), where the constraint set is the set of common fixed points of N nonexpansive mappings T₁, T₂, …, T_N.

Motivated and inspired by the above works, in this paper, we combine the hybrid steepest descent algorithm and hierarchical variational inequalities to propose a synchronal algorithm and a cyclic algorithm involving finite family of nonexpansive mappings. Under certain assumptions, we will prove that the sequences converge strongly. Further an example will be given to demonstrate the effectiveness of our iterative schemes.

2. Preliminaries

Recall that given a nonempty, closed and convex subset C of a real Hilbert space H, for any x ∈ H, there exists a unique nearest point in C, denoted by P_Cx, such that

()

for all y ∈ C. Such a P_C is called the metric (or the nearest point) projection of H onto C. As we all know, y = P_Cx if and only if there holds the relation

()

In the sequel, we will make use of the following lemmas in a real Hilbert space H.

Lemma 2. Let H be a real Hilbert space; the following inequalities hold:

(i)
∥x+y∥² ≤ ∥x∥² + 2〈y, x + y〉, ∀x, y ∈ H,
(ii)
∥tx+(1−t)y∥² ≤ t∥x∥² + (1 − t)∥y∥², ∀t ∈ [0,1], ∀x, y ∈ H.

Lemma 3 (see [13].)Let B : H → H be a k-Lipschitzian and η-strongly monotone operator on a Hilbert space H with k > 0, η > 0, 0 < μ < 2η/k², and 0 < t < 1. Then S = (I − tμB) : H → H is a contraction with contractive coefficient 1 − tτ and τ = (1/2)μ(2η − μk²).

Lemma 4 (see [5].)Let V : C → H be an l-Lipschitz mapping with coefficient l ≥ 0 and B : C → H a k-Lipschitzian continuous operator and η-strongly monotone operator with k > 0, η > 0. Then for 0 < γ < μη/l,

()

That is, μB − γV is strongly monotone with coefficient μη − γl.

Lemma 5 (see [9].)Assume that {a_n} is a sequence of nonnegative real numbers such that

()

where {γ_n} is a sequence in (0,1) and {δ_n} is a sequence such that

(i)
,
(ii)
limsup _n→∞(δ_n/γ_n) ≤ 0 or .

Then, lim _n→∞a_n = 0.

Lemma 6 (see [14].)Let H be a real Hilbert, and let T_i : H → H (i = 1,2, …) be all nonexpansive mappings with . Let , where {ω_i}⊂(0,1) such that . Then T is a nonexpansive mapping with .

Lemma 7 (see [13].)Let H be a Hilbert space, and let C be a nonempty closed convex subset of H and T : C → C a nonexpansive mapping with Fix (T) ≠ ∅. If {x_n} is a sequence in C weakly converging to x and if {(I − T)x_n} converges strongly to y, then (I − T)x = y.

We adopt the following notations:

(1)
x_n⇀x stands for the weak convergence of {x_n} to x,
(2)
x_n → x stands for the strong convergence of {x_n} to x.

3. Synchronal Algorithm

Throughout the rest of this paper, we always assume that V : C → H is an l-Lipschitzian mapping with coefficient l ≥ 0 and B : C → H is a k-Lipschitzian continuous operator and η-strongly monotone with k > 0, η > 0. Let N ≥ 1 be an integer. Let, for each 1 ≤ i ≤ N, T_i : C → C be a nonexpansive mapping and S : C → C also nonexpansive. Assume that 0 < μ < 2η/k² and 0 < γ < μ(η − μk²/2)/α = τ/l.

Define a mapping U_n = β_nS + (1 − β_n)I. Since S is nonexpansive, it is easy to get that U_n is also nonexpansive. Consider the following mapping G_n on C defined by

()

where α_n ∈ (0,1),

with ω_i > 0, and

. By Lemmas 2 and 3, we obtain

()

Since 0 < 1 − α_n(τ − γl) < 1, it follows that G_n is a contraction. Therefore, by the Banach contraction principle, G_n has a unique fixed point

such that

()

For simplicity, we will write x_n for

provided that no confusion occurs. Next we prove that the sequence {x_n} converges strongly to a point

which solves the variational inequality

()

By the property of the projection, we can get x^* = P_Ω(I − μB + γV)x^* equivalently.

Theorem 8. Let C be a nonempty, closed, and convex subset of a real Hilbert space H and V : C → H an l-Lipschitzian mapping with l ≥ 0. Let N ≥ 1 be an integer. Let, for each 1 ≤ i ≤ N, T_i : C → C be a nonexpansive mapping and let S : C → C be also nonexpansive. Assume the set . Let B : C → H be a k-Lipschitzian continuous operator and η-strongly monotone with k > 0, η > 0, 0 < μ < 2η/k² and 0 < γ < μ(η − μk²/2)/l = τ/l. Given x₁ ∈ C, let {x_n} be the sequence generated by the following algorithm:

()

If {α_n} and {β_n} satisfy the following properties:

(i)
{α_n}⊂(0,1), lim _n→∞α_n = 0 and ,
(ii)
{β_n}⊂[0,1), lim _n→∞(β_n/α_n) = 0,
(iii)
and .

Then, {x_n} converges strongly to x^* ∈ Ω, which solves the variational inequality (16).

Proof. The proof is divided into several steps.

Step 1. Show first that {x_n} is bounded.

Take any p ∈ Ω; we have

()

Further we get

()

By induction, we obtain ∥x_n − p∥ ≤ max {∥x₁ − p∥, (∥γVp − μBp∥ + ∥Sp − p∥)/(τ − lγ)}, n ≥ 1. Hence, {x_n} is bounded, so is {y_n}. It follows from the Lipschitz continuity of B and V that {Bx_n}, {Bu_n}, and {Vx_n} are also bounded. From the nonexpansivity of T and S, it follows that {Tx_n}, {Sx_n}, and {BTy_n} are also bounded.

Step 2. Show that

()

By (17), we have

()

Observe that

()

Together with (21) and (22), we get

()

where M₁ = sup _n{∥γlVx_n−1∥ + μ∥BTy_n−1∥ + ∥Sx_n−1∥ + ∥x_n−1∥}.

By Lemma 5, we obtain

()

Step 3. Show that

()

Observe that

()

From condition (i) and (ii), we obtain

()

Step 4. Show that

()

where x^* = P_Ω(I − μB + γV)x^* is a unique solution of the variational inequality (16).

Indeed, take a subsequence of {x_n} such that

()

Since is bounded, there exists a subsequence of which converges weakly to . Without loss of generality, we can assume and

()

By Lemma 7, we have . From Lemma 6, we get

()

Since x^* = P_Ω(I − μB + γV)x^*, it follows that

()

Step 5. Show that

()

Denote z_n = α_nγVx_n + (I − μα_nB)Ty_n, then x_n+1 = P_Cz_n. From (17), we have

()

This implies that

()

where M₂ = sup _n∥x_n+1 − x^*∥∥Sx^* − x^*∥, n ≥ 1. Put γ_n = α_n(τ − lγ), δ_n = 2β_nM₂ +2α_n〈γVx^* − μBx^*, x_n+1 − x^*〉. It is easy to see that limsup _n→∞δ_n/γ_n ≤ 0. Hence by Lemma 5, the sequence {x_n} converges strongly to x^*.

Remark 9. Let N = 1 in Theorem 8; we can get Theorem 3.1 of [8].

Remark 10. Let N = 1, γ = 1, μ = 1, B = I and V, be a contraction in Theorem 8; it is easy to get the theorem of [10].

4. Cyclic Algorithm

In this section, we consider the cyclic algorithm of N nonexpansive mappings T₁, T₂, …, T_N. Similarly, we can get that the mapping G_n on C defined by

()

is a contraction, where T_[n] = T_i with i = n(mod )N taking values in {1,2, …, N}.

Theorem 11. Let C be a nonempty, closed, and convex subset of a real Hilbert space H, and let V : C → H be an l-Lipschitzian mapping with l ≥ 0. Let N ≥ 1 be an integer. Let, for each 1 ≤ i ≤ N, T_i : C → C be a nonexpansive mapping and let S : C → C be also nonexpansive. Assume the set . Let B : C → H be a k-Lipschitzian continuous operator and η-strongly monotone with k > 0, η > 0, 0 < μ < 2η/k², and 0 < γ < μ(η − μk²/2)/l = τ/l. Given x₁ ∈ C, let {x_n} be the sequence generated by the following algorithm:

()

If {α_n} and {β_n} satisfy the following properties:

(i)
{α_n}⊂(0,1), lim _n→∞α_n = 0 and ,
(ii)
{β_n}⊂[0,1), lim _n→∞(β_n/α_n) = 0,
(iii)
and .

Assume in addition that

()

Then, {x_n} converges strongly to x^* ∈ Ω, which solves the variational inequality (16).

Proof. The proof is divided into several steps.

Step 1. Show first that {x_n} is bounded.

The proof of Step 1 is similar to that of Theorem 8.

Step 2. Show that

()

By (37), we have

()

Observe that

()

Together with (40) and (41), we have

()

where M₃ = sup _n{∥γlVx_n∥ + μ∥BT_[n]y_n∥ + ∥Sx_n∥ + ∥x_n∥}.

By Lemma 5, we get

()

Step 3. Show that

()

Observe that

()

From conditions (i) and (ii) of Theorem 11, we obtain

()

Recursively,

()

Since every T_[n] is nonexpansive, it is easy to get

()

Similarly, we obtain

()

Thus we get

()

Since

()

we obtain (44).

Step 4. Show that

()

where x^* = P_Ω(I − μB + γV)x^* is a unique solution of the variational inequality (16).

Indeed, take a subsequence of {x_n} such that

()

Since is bounded, there exists a subsequence of which converges weakly to . Without loss of generality, we can assume and

()

Notice that, for each n_j, is some permutation of the mappings T₁T₂ ⋯ T_N. Since T₁T₂ ⋯ T_N are finite, all the finite permutations are N!; there must be some permutation that appears infinite times. Without loss of generality, we can assume this permutation is T_NT_N−1 ⋯ T₁. We obtain

()

Obviously, T_NT_N−1 ⋯ T₁ is nonexpansive. By Lemma 7, we have . Further by the assumption in Theorem 11, we get

()

Since x^* = P_Ω(I − μB + γV)x^*, it follows that

()

Step 5. Show that

()

Denote z_n = α_nγVx_n + (I − μα_nB)T_[n]y_n; then x_n+1 = P_Cz_n. From (37), we have

()

This implies that

()

where M₁ = sup _n∥x_n − x^*∥∥Sx^* − x^*∥, n ≥ 1. Put γ_n = α_n(τ − lγ), δ_n = 2β_nM₁ +2α_n〈γVx^* − μBx^*, x_n+1 − x^*〉. It is easy to see that limsup _n→∞δ_n/γ_n ≤ 0. Hence, by Lemma 6, the sequence {x_n} converges strongly to x^*.

5. Numerical Result

In this section, we consider the following simple example to demonstrate the effectiveness, realization, and convergence of the algorithms in Theorems 8 and 11.

Example 12. Let H = ℝ, C = [1/4, +∞). Define , T₂ : x ↦ x + π/4 − arctanx, S : x ↦ sinx. Take B = I with Lipschitz constant k = 1 and strongly monotone constant η = 1, Vx = 2x, ∀x ∈ H, with Lipschitz coefficient l = 2. Give the parameters α_n = 1/2n; β_n = 1/n² for every n ≥ 1; fix μ = 1 and γ = 1/4. Then by Theorems 8 and 11, respectively, the sequence {x_n} is generated by

()

As n → ∞, we have {x_n} → x^* = 1.

Let ω_i = 1/2, i = 1,2; then we have

if n is odd and T_[n]x = x + π/4 − arctanx if n is even. Put z_n = (1/4n)x_n + (1 − 1/2n)Ty_n; then (61) is equivalent to

()

Using the same method to treat (62), we can get similar equation as the above formula.

Now we turn to numerical simulation using the algorithms (17) and (37), respectively. Take the initial guess x₁ = 2; using software Matlab R2012, we obtain the numerical experiment results in Tables 1 and 2.

Table 1. x₁ = 2.

n (iterative number)	x_n (iterative point)	Errors (n)
50	0.9901	9.9 × 10⁻³
500	0.9990	9.9852 × 10⁻⁴
2000	0.9999	9.9985 × 10⁻⁵

Table 2. x₁ = 2.

n (iterative number)	x_n (iterative point)	Errors (n)
50	0.9902	9.8 × 10⁻³
500	0.9990	9.9814 × 10⁻⁴
2000	0.9999	9.9981 × 10⁻⁵

From the computer programming point of view, the algorithms are easier to implement in this paper.

Acknowledgments

The authors would like to thank the referee for valuable suggestions to improve the manuscript and the Fundamental Research Funds for the Central Universities (Grant 3122013k004).

References

1 Combettes P. L., A block-iterative surrogate constraint splitting method for quadratic signal recovery, IEEE Transactions on Signal Processing. (2003) 51, no. 7, 1771–1782, https://doi.org/10.1109/TSP.2003.812846, MR1996963.
10.1109/TSP.2003.812846
Web of Science® Google Scholar
2 Iiduka H. and Yamada I., A use of conjugate gradient direction for the convex optimization problem over the fixed point set of a nonexpansive mapping, SIAM Journal on Optimization. (2008) 19, no. 4, 1881–1893, https://doi.org/10.1137/070702497, MR2486054.
10.1137/070702497
Web of Science® Google Scholar
3 Iiduka H., Fixed point optimization algorithm and its application to power control in CDMA data networks, Mathematical Programming. (2012) 133, no. 1-2, 227–242, https://doi.org/10.1007/s10107-010-0427-x, MR2921098.
10.1007/s10107-010-0427-x
Web of Science® Google Scholar
4 Ceng L. C., Ansari Q. H., Wong N. C., and Yao J. C., Implicit iterative method for hierarchical variational inequalities, Journal of Applied Mathematics. (2012) 2012, 14, 472935, https://doi.org/10.1155/2012/472935, MR2910907.
10.1155/2012/472935
Google Scholar
5 Ceng L. C., Ansari Q. H., and Yao J. C., Some iterative methods for finding fixed points and for solving constrained convex minimization problems, Nonlinear Analysis. (2011) 74, no. 16, 5286–5302, https://doi.org/10.1016/j.na.2011.05.005, MR2819274.
10.1016/j.na.2011.05.005
Web of Science® Google Scholar
6 Iiduka H., Iterative algorithm for solving triple-hierarchical constrained optimization problem, Journal of Optimization Theory and Applications. (2011) 148, no. 3, 580–592, https://doi.org/10.1007/s10957-010-9769-z, MR2769880.
10.1007/s10957-010-9769-z
Web of Science® Google Scholar
7 Marino G. and Xu H. K., Explicit hierarchical fixed point approach to variational inequalities, Journal of Optimization Theory and Applications. (2011) 149, no. 1, 61–78, https://doi.org/10.1007/s10957-010-9775-1, MR2774147.
10.1007/s10957-010-9775-1
Web of Science® Google Scholar
8 Wang Y. H. and Xu W., Strong covergence of a modified iterative algorithm for hierarchical fixed point problems and variational inequalities, Fixed Point Theory and Applications. (2013) 2013, no. article 121, https://doi.org/10.1186/1687-1812-2013-121.
10.1186/1687-1812-2013-121
Google Scholar
9 Xu H. K., Viscosity method for hierarchical fixed point approach to variational inequalities, Taiwanese Journal of Mathematics. (2010) 14, no. 2, 463–478, MR2655782.
10.11650/twjm/1500405802
Web of Science® Google Scholar
10 Yao Y., Cho Y. J., and Liou Y. C., Iterative algorithms for hierarchical fixed points problems and variational inequalities, Mathematical and Computer Modelling. (2010) 52, no. 9-10, 1697–1705, https://doi.org/10.1016/j.mcm.2010.06.038, MR2719584.
10.1016/j.mcm.2010.06.038
Google Scholar
11 Tian M., A general iterative algorithm for nonexpansive mappings in Hilbert spaces, Nonlinear Analysis. (2010) 73, no. 3, 689–694, https://doi.org/10.1016/j.na.2010.03.058, MR2653741.
10.1016/j.na.2010.03.058
Web of Science® Google Scholar
12 Yamada I., The hybrid steepest-descent method for variational inequality problems over the intersection of the fixed-point sets of nonexpansive mappings, Studies in Computational Mathematics. (2001) 8, 473–504, https://doi.org/10.1016/S1570-579X(01)80028-8, MR1853237.
10.1016/S1570-579X(01)80028-8
Google Scholar
13 Tian M. and Di L. Y., Synchronal algorithm and cyclic algorithm for fixed point problems and variational inequality problems in Hilbert spaces, Fixed Point Theory and Applications. (2011) 2011, no. article 21, https://doi.org/10.1186/1687-1812-2011-21.
10.1186/1687-1812-2011-21
Google Scholar
14 He S. N. and Sun W. W., New hybrid steepest descent algorithms for variational inequalities over the common fixed points set of infinite nonexpansive mappings, WSEAS Transactions on Mathematics. (2012) 11, no. 2, 83–92.
Google Scholar

All articles

Synchronal Algorithm and Cyclic Algorithm for Hierarchical Fixed Point Problems and Variational Inequalities

Abstract

1. Introduction

2. Preliminaries

3. Synchronal Algorithm

4. Cyclic Algorithm

5. Numerical Result

Acknowledgments

References

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

Synchronal Algorithm and Cyclic Algorithm for Hierarchical Fixed Point Problems and Variational Inequalities

Abstract

1. Introduction

2. Preliminaries

3. Synchronal Algorithm

4. Cyclic Algorithm

5. Numerical Result

Acknowledgments

References

References

Related

Information