Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

New hybrid inertial CQ projection algorithms with line-search process for the split feasibility problem

New hybrid inertial CQ projection algorithms with line-search process for the split feasibility... Appl. Math. J. Chinese Univ. 2023, 38(1): 144-158 New hybrid inertial CQ projection algorithms with line-search process for the split feasibility problem DANG Ya-zheng WANG Long YANG Yao-heng Abstract. In this paper, we propose two hybrid inertial CQ projection algorithms with line- search process for the split feasibility problem. Based on the hybrid CQ projection algorithm, we rstly add the inertial term into the iteration to accelerate the convergence of the algorithm, and adopt exible rules for selecting the stepsize and the shrinking projection region, which makes an optimal stepsize available at each iteration. The shrinking projection region is the intersection of three sets, which are the set C and two hyperplanes. Furthermore, we modify the Armijo-type line-search step in the presented algorithm to get a new algorithm.The algorithms are shown to be convergent under certain mild assumptions. Besides, numerical examples are given to show that the proposed algorithms have better performance than the general CQ algorithm. x1 Introduction Split Feasibility Problem (SFP) was firstly introduced by Censor and Elfving [4] in 1994, which is to find a point x satisfying ∗ ∗ x ∈ C ; Ax ∈ Q; (1) N M where C and Q are nonempty convex sets in ℜ and ℜ , respectively, and A is an M by N real matrix. Problem (1) together with many variants of it has received much attention from opti- mization community due to its broad applications to many disciplines, such as signal processing, image reconstruction, intensity-modulated radiation therapy, etc. [1,2,3,7]. Therefore, many ef- fective methods have been proposed to solve the problem (1), see [5,6,8,16,17,22,23]. A very suc- cessful algorithm that solves the SFP seems to be the CQ algorithm of Byrne [2] which is defined as follows: Denote P by the orthogonal projection onto C, that is, P (y) = argmin ||x−y||, c C x∈C for y ∈ C; then take an initial point arbitrarily and define the iterative step by Received: 2021-05-26. Revised: 2022-03-17. MR Subject Classi cation: 47J05, 47J25. Keywords: split feasible problem, inertial, Armijo-type line-search technique, projection algorithm, conver- gence. Digital Object Identi er(DOI): https://doi.org/10.1007/s11766-023-4464-7. Supported by the National Natural Science Foundation of China(72071130). *Corresponding author. ⃝The Author(s) 2023. DANG Ya-zheng, et al. New hybrid inertial CQ projection algorithms with... 145 k+1 T k x = P (I − A (I − P )A)(x ); (2) C Q where 0 < < 2=∥A∥ . The CQ algorithm (2) can be regarded as a special case of the gradient projection method if we consider the convex minimization problem min ∥(I − P ) Ax∥ : x∈C Observe that, the choice of stepsize in CQ algorithm depends on the norm of the operator, which is not a simple work. To avoid this computation, some modifications of the CQ algorithm and the self-adaptive method have been developed for solving the SFP. L pez et al. [12] introduced a new way of selecting the stepsizes for solving SFP (1) such that the information of operator norm is not necessary. Motivated and inspired by the work of [12,20,24,27], the authors of [14] introduced a self-adaptive CQ-type algorithm for solving the SFP in the setting of infinite dimensional real Hilbert spaces. Inspired by the projection and contraction method and the hybrid descent approximation method, Gibali et al. [11] investigated the problem of finding a common solution to a fixed point problem involving demi-contractive operator and a variational inequality with monotone and Lipschitz continuous mapping in real Hilbert spaces. Shehu et al. [19] introduced iterative algorithms and proved their strong convergence for solving proximal split feasibility problems and fixed point problems for k-strictly pseudocontractive mappings in Hilbert spaces. Dang et al. [9] proposed a hybrid CQ projection algorithm with Armijo-type line-search step, which is different from the general self-adaptive Armijo-type procedure [25,26]. On the other hand, in [15], Polyak firstly proposed the inertial term as an acceleration process to solve the smooth convex minimization problem. In recent years, scholars have proposed some inertial iterative algorithms for solving the SFP. Based on [12], Taddele et al. [21] proposed an iterative algorithm with inertial extrapolation to approximate the solution of multiple-set SFP. Shehu et al. [18] introduced new CQ methods with alternated inertial procedure and self- adaptive stepsize for solving SFP. Li et al. [13] proposed two inertial relaxed CQ algorithms for solving the SFP in real Hilbert spaces according to the previous experience of applying inertial technology to the algorithm. Godwin et al [10] introduced a new inertial extrapolation method for solving a certain class of generalized SFP without the prior knowledge of the operator norm or the coefficient of an underlying operator. Inspired by the works mentioned above, we propose two hybrid inertial CQ projection algorithms with line-search process for the split feasibility problem. The main features of the proposed algorithms as follows: 1. Based on [9], we incorporate the inertial term into the iteration to construct Algorithm 3.1, which improves the efficiency of convergence. Furthermore, we adjust the Armijo-type line-search step in Algorithm 3.1 to get Algorithm 3.2. 2. Algorithms perform a computationally inexpensive Armijo-type linear search along the search direction to generate a hyperplane. 3. The next iteration is generated by the projection of the initial point on the intersection of the set C with the hyperplanes, which makes an optimal stepsize available at each iteration. 146 Appl. Math. J. Chinese Univ. Vol. 38, No. 1 Different from the algorithms in [11,19], two hyperplanes are constructed in our algorithms to generate the shrinking projection region. The paper is organized as follows. In section 2, Some useful definitions and results are collected for the convergence analysis of the proposed algorithms. In Section 3, we propose two hybrid inertial CQ projection algorithms for the split feasibility problem and show their convergence. In Section 4, numerical experiments are reported to conclude the effectiveness of our algorithms. Finally, some conclusions are given in Section 5. x2 Preliminaries We denote by I the identity operator and by Fix(T ) the set of fixed points of an operator T , that is, Fix(T ) := {x|x = Tx}: Recall that a mapping T : ℜ → ℜ is said to be monotone if ⟨T (x) − T (y); x − y⟩ ≥ 0; ∀x; y ∈ ℜ : For a monotone mapping T , ⟨T (x) − T (y); x − y⟩ =0 iff x = y, then it is said to be strictly monotone. n n A mapping T : ℜ → ℜ is called non-expansive if ∥T (x) − T(y)∥ ≤ ∥x − y∥ ; ∀x; y ∈ ℜ : Lemma 2.1 [9,13] Let Ω be a nonempty closed and convex subset in H. Then, for any x; y ∈ H and z ∈ Ω, the following hold: (1) ⟨x − P (x); z − P (x)⟩ ≤ 0. Ω Ω (2) ∥P (x) − P (y)∥ ≤ ⟨P (x) − P (y); x − y⟩. Ω Ω Ω Ω (3) ∥P (x) − P (y)∥ ≤ ∥x − y∥ ; ∀x; y ∈ ℜ , or more precisely, Ω Ω 2 2 2 ∥P (x) − P (y)∥ ≤ ∥x − y∥ − ∥P (x) − x + y − P (y)∥ : Ω Ω Ω Ω 2 2 2 (4) ∥P (x) − z∥ ≤ ∥x − z∥ − ∥P (x) − x∥ . Ω Ω Remark 2.1 In fact, the projection property (1) also provides a sufficient and necessary con- dition for a vector u ∈ K to be the projection of the vector x; that is,u = P (x) if and only if ⟨u − z; x − u⟩ ≥ 0; ∀z ∈ K: Lemma 2.2 [18] The following statements hold in ℜ : 2 2 2 (1) ∥x + y∥ = ∥x∥ + 2 ⟨x; y⟩ + ∥y∥ , for all x; y ∈ ℜ . DANG Ya-zheng, et al. New hybrid inertial CQ projection algorithms with... 147 2 2 (2) ∥x + y∥ ≤ ∥x∥ + 2 ⟨y; x + y⟩, for all x; y ∈ ℜ . Lemma 2.3 [3] Let f(x) := ∥(I − P )Ax∥ , x ∈ C. Then (1) f is convex and differentiable. T N (2) ∇f(x) = A (I − P )Ax, x ∈ ℜ . (3) f is lower semicontinuous on ℜ . (4) ∇f Lipschitz continuous with Lipschitz constant ∥A∥ . Throughout the paper, the solution set of split feasibility problem is denoted by Γ, that is ∗ ∗ Γ := {x ∈ C|Ax ∈ Q}: (3) x3 Algorithms and their convergence analysis Let F(x) := (A (I − P )A)(x): Then we know that F is Lipschitz-continuous with constant ∥A∥ . We first note that the solution set coincides with zeros of the following projected residual function: e(x) := x − P (x − F(x)); e(x; ) := x − P (x − F (x)); C C with this definition, we have e(x; 1) = e(x), and x ∈ Γ if and only if e(x; ) = 0. For any x ∈ ℜ and ≥ 0, define x( ) = P (x − F (x)); e(x; ) = x − x( ): The following lemma is useful for the convergence analysis in the next section. N N N Lemma 3.1 [25] Let F be a mapping from ℜ into ℜ . For any x ∈ ℜ and ≥ 0, we have min{1; } ∥e(x; 1)∥ ≤ ∥e(x; )∥ ≤ max{1; } ∥e(x; 1)∥ : Now, we describe our first algorithm as follows: Algorithm 3.1 0 1 N Step 0. Choose arbitrary initial points x ; x ∈ ℜ , and parameters  > 0, t ∈ (0; 1), 0 k ∈ (0; 1),  ∈ (0; 1), " ∈ (0; 1) and  > 1, and set k = 0. k−1 k Step 1. Assuming x , x have been constructed, compute k k k k−1 w = P [x + t (x − x )]; (4) C k k k k z = P [w −  F(w )]; (5) C k 148 Appl. Math. J. Chinese Univ. Vol. 38, No. 1 { } where  is a positive number satisfying " <  ≤ min − "; 1 . Obviously, e(w ;  ) = k k T k (A A) k k k w − z . If e(w ;  ) = 0, then stop; Step 2. Compute k k k y = w −  e(w ;  ); (6) k k where  =  , with m being the smallest nonnegative integer m satisfying k k k ⟨ ⟩ k m k k k F(w −  e(w ;  )); e(w ;  ) ≥ e(w ;  ) : (7) k k k k Step 3. Compute k+1 0 x = P 1 2(x ); (8) C∩H ∩H k k where { } 2 2 1 N k k H = x ∈ ℜ | y − x ≤ w − x ; { ⟨ ⟩ } 2 N k 0 k H = x ∈ ℜ | x − x ; x − x ≤ 0 : Set k = k + 1 and go to Step 1. Before establishing the global convergence of Algorithm 3.1, we first give the following lemmas. Lemma 3.2 There exists a nonnegative number m satisfying (7), for all k ≥ 0. proof. Suppose that, for some k, (7) is not satisfied for any integer m , that is, ⟨ ⟩ k m k k k F(w −  e(w ;  )); e(w ;  ) ≤ e(w ;  ) : (9) k k k k By the definition of e(w ;  ), and Lemma 2.1 we know that ⟨ ⟩ k k k k k k k P (w −  F(w )) − (w −  F(w )); w − P (w −  F(w )) ≥ 0: C k k C k Then ⟨ ⟩ 1 2 k k k F(w ); e(w ;  ) ≥ e(w ;  ) > 0: (10) k k { } Since ∈ (0; 1) and " <  ≤ min − "; 1 , from (9) we get k T (A A) k m k k lim (w −  e(w ;  )) = w : k k m→∞ Hence, ⟨ ⟩ 2 2 k k k k F(w ); e(w ;  ) ≤ e(w ;  ) < e(w ;  ) : (11) k k k k k But (11) contradicts (10) because e(w ;  ) ≥ 0. Hence, (7) is satisfied for some integer m. Lemma 3.3 If the solution set Γ ̸= ∅, then Γ ⊂ H ∩ C for all k ≥ 0. k DANG Ya-zheng, et al. New hybrid inertial CQ projection algorithms with... 149 proof. Let x ∈ Γ, then 2 2 k ∗ k T k ∗ z − x = P (w −  A (I − P )Aw ) − x C k Q k ∗ T k ≤ w − x −  A (I − P )Aw k Q ⟨ ⟩ 2 2 k ∗ k ∗ T k 2 T k = w − x − 2 w − x ; A (I − P )Aw + A (I−P )Aw k Q k Q ⟨ ⟩ 2 2 k ∗ k ∗ k 2 T k = w − x − 2 A(w − x ); (I − P )Aw + A (I−P )Aw k Q k Q ⟨ ⟩ k ∗ k k k ∗ k = w − x − 2 Aw − P Aw + P Aw − Ax ; (I − P )Aw k Q Q Q 2 T k +  A (I − P )Aw k Q 2 2 k ∗ k = w − x − 2 (I − P )Aw k Q ⟨ ⟩ k ∗ k 2 T k − 2 P Aw − Ax ; (I − P )Aw +  A (I − P )Aw : k Q Q k Q From Lemma 2.1, we obtain { } 2 2 2 2 k ∗ k ∗ k T k z − x ≤ w − x −  2 (I − P )Aw −  A (I − P )Aw k Q k Q ( ) 2 2 2 k ∗ T k ≤ w − x −  −  A (I − P )Aw (12) k k Q (A A) k ∗ ≤ w − x : (13) Also, it follows from the definition of y that 2 2 k ∗ k ∗ k k y − x = w − x −  (w − z ) ⟨ ⟩ 2 2 k ∗ k ∗ k k 2 k k = w − x − 2 w − x ; w − z +  w − z ; k k which can be rewritten as { } ⟨ ⟩ 1 2 2 2 k ∗ k k k ∗ k ∗ 2 k k w − x ; w − z = − y − x − w − x − w − z : (14) On the other hand, by the definition of y , we have 2 2 k ∗ k ∗ k k y − x = w − x −  (w − z ) k ∗ k k = z − x + (1 −  )(w − z ) ⟨ ⟩ 2 2 k ∗ k ∗ k k 2 k k = z −x +2(1− ) z − x ; w − z + (1 −  ) w − z k k ⟨ ⟩ 2 2 k ∗ k k k ∗ k k 2 k k = z −x +2(1− ) z −w +w −x ; w −z +(1− ) w −z k k ⟨ ⟩ 2 2 k ∗ k ∗ k k 2 k k = z −x +2(1− ) w − x ; w − z +( − 1) w − z : (15) k k 2 2 k ∗ k ∗ Since z − x ≤ w − x , then by (14) and (15) we get 1 2 2 1 2 2 k ∗ k ∗ k ∗ k k y − x = z − x +( − 1) w − x + ( − 1) w − z k k 1 1 2 2 2 k ∗ k ∗ k ∗ ≤ w − x + ( − 1) w − x = w − x : k k Hence 2 2 k ∗ k ∗ y − x ≤ w − x ; ∗ 1 1 which implies x ∈ H . Moreover, it is easy to see that Γ ⊂ H ∩ C, ∀k ≥ 0. k k 1 2 The following lemma says that if the solution set is nonempty, then Γ ⊂ H ∩ H ∩ C and k k 150 Appl. Math. J. Chinese Univ. Vol. 38, No. 1 1 2 thus H ∩ H ∩ Cis a nonempty set. k k 1 2 Lemma 3.4 [9, Lemma 3.4] If the solution set Γ ̸= ∅, then Γ ⊂ H ∩ H ∩ C for all k ≥ 0. k k 1 2 For the case that the solution set is empty, we have that H ∩H ∩C is also nonempty from k k the following lemma, which implies the feasibility of Algorithm 3.1. 1 2 Lemma 3.5 Suppose that Γ = ∅, then H ∩ H ∩ C ̸= ∅ for all k ≥ 0. k k { } Lemma 3.6 Let x be a sequence generated by algorithm 3.1. Then k k (i) lim x − w = 0; k→∞ k k (ii) lim x − y = 0; k→∞ k k (iii) lim x − z = 0; k→∞ T k (iv) lim A (I − P )Aw = 0. k→∞ { } proof. (i) From [9, theorem 3.1], we know that x is a bounded sequence and convergent, which implies that k+1 k lim x − x = 0: (16) k→∞ By the definition of w , it follows that , k k k k k k−1 x − w = x − P [x + t (x − x )] C k k k k k−1 ≤ x − [x + t (x − x )] k k−1 = |t | · x − x : Therefore, from the selection of parameter t and (16), we have k k lim x − w = 0: (17) k→∞ (ii) From (16) and (17), we obtain k+1 k k+1 k k k x − w = x − x + x − w k+1 k k k ≤ x − x + x − w → 0 as k → ∞; k+1 1 which with x ∈ H implies that k+1 k lim x − y = 0: k→∞ k k k k+1 k+1 k Again, since x − y ≤ x − x + x − y , it then follows that k k lim x − y = 0: (18) k→∞ k k k k k k (iii) Since w − y ≤ w − x + x − y , then form (17) and (18) we have k k lim w − y = 0: (19) k→∞ From the definition of y , we get ( ) k k k k k w − y = e(w ;  )= w − z : k k k DANG Ya-zheng, et al. New hybrid inertial CQ projection algorithms with... 151 Then, note that from the construction of  and (19), we have k k k k w − z = w − y → 0 as k → ∞: (20) | | Hence, from (17) and (20), we get k k k k k k x − z ≤ x − w + w − z → 0 as k → ∞: (iv) Observe that by (12) ( ) 2 2 2 2 T k k ∗ k ∗ −  A (I − P )Aw ≤ w − x − z − x k k Q (A A) ⟨ ⟩ k k k ∗ k k = w − z + 2 z − x ; w − z ⟨ ⟩ k ∗ k k ≤ 2 z − x ; w − z : { } k k From (i), we know that x is a convergent and bounded sequence. By the definition of w , { } 2 2 k ∗ ∗ k ∗ k ∗ the sequence w − x is bounded, for ∀x ∈ Γ. And since z − x ≤ w − x , we { } k ∗ conclude that z − x is bounded. Then, from (20), it follows that ( ) T k lim  −  A (I − P )Aw = 0: (21) k k Q k→∞  (A A) ( ) This together with the fact that lim  −  ̸= 0 further implies k T k (A A) k→∞ T k lim A (I − P )Aw = 0: (22) k→∞ We now prove our main convergence result. { } Theorem 3.1 Suppose the solution set Γ is nonempty, then the sequence x generated by Algorithm 3.1 is bounded, and all its cluster points belong to the solution set. Moreover, the { } k ∗ ∗ 0 sequence x globally converges to a solution x such that x = P (x ). k 0 proof. We have already kown in (i) that lim x − x exists. k→∞ Now, we show that x → x¯ ∈ Γ: Let m; n ∈ N, since n 0 x = P 1 2 (x ); H ∩H ∩C n−1 n−1 then 2 2 m n m 0 n 0 ∥x − x ∥ ≤ x − x − x − x : m n k Hence lim ∥x − x ∥ =0. Thus x is a Cauchy sequence in C. Since C is nonempty k≥2 m;n→∞ N k convex sets in ℜ , it implies that there exists x¯ ∈ C such that x → x¯ as k → ∞: More so, k k k k since x − w → 0, then w → x¯ and by the linearity of A, we have Aw → Ax¯. Also from (22), we have 2 2 T k T lim A (I − P )Aw = A (I − P )Ax =0: Q Q k→∞ Since the projected residual function k k k T k e(x ) = x − P (x − A (I − P )Ax ); C Q then, we have k T e(x¯) = lim e(x ) = x¯ − P (x¯ − A (I − P )Ax¯)=x¯ − P (x¯)=0: C Q C k→∞ 152 Appl. Math. J. Chinese Univ. Vol. 38, No. 1 Thus x¯ is a solution of problem (1). { } Now, we prove that the sequence x converges to a point contained in Γ. ( ) ∗ 0 ∗ Let x = P x . Since x ∈ Γ, by Lemma 3.4 we have ∗ 1 2 x ∈ H ∩ H ∩ C; ∀j: k −1 k −1 j j So, by the iterative sequence of Algorithm 3.1 we have k 0 ∗ 0 x − x ≤ x − x : Thus 2 2 k ∗ k 0 0 ∗ j j x − x + x − x x − x = ⟨ ⟩ k 0 0 ∗ k 0 0 ∗ j j = x − x + x − x + 2 x − x ; x − x ⟨ ⟩ 2 2 ∗ 0 0 ∗ k 0 0 ∗ ≤ x − x + x − x + 2 x − x ; x − x : Letting j → ∞ , we have ⟨ ⟩ ∗ 0 ∗ 0 0 ∗ ∥x¯ − x ∥ ≤ 2 x − x + 2 x¯ − x ; x − x ⟨ ⟩ ∗ 0 ∗ = 2 x¯ − x ; x − x ≤ 0; ∗ 0 where the last inequality is due to Lemma 2.1 and the fact that x = P (x ) and x¯ ∈ Γ. So, ( ) ∗ 0 x¯ = x = P x : { } ( ) k 0 Thus, the sequence x has a unique cluster point P x , which shows the global convergence { } of x . Now, we put another line search method in the Algorithm 3.1 to get a new algorithm. Algorithm 3.2 0 1 N Step 0. Choose arbitrary initial points x ; x ∈ ℜ , and parameters  > 0, t ∈ (0; 1), 0 k ∈ (0; 1),  ∈ (0; 1), " ∈ (0; 1), and  > 1, and set k = 0. k−1 k Step 1. Assuming x , x have been constructed, compute k k k k−1 w = P [x + t (x − x )]; C k k k k z = P [w −  F(w )]; C k { } 2 k where  is a positive number satisfying " <  ≤ min − "; 1 . We have e(w ;  ) = k k T k (A A) k k k w − z . If e(w ;  ) = 0, then stop; Step 2. Compute k k k k y = (1 −  )w +  (z −  e(w ;  )); (23) k k k k 1 m where " < < and  =  with m being the smallest nonnegative integer m satis- k k k k (1+ ) fying ⟨ ⟩ k m k k k F(w −  e(w ;  )); e(w ;  ) ≥ e(w ;  ) : k k k k Step 3. Compute k+1 0 x = P 1 2(x ); C∩H ∩H k k where { } 2 2 1 N k k H = x ∈ ℜ | y − x ≤ w − x ; k DANG Ya-zheng, et al. New hybrid inertial CQ projection algorithms with... 153 { ⟨ ⟩ } 2 N k 0 k H = x ∈ ℜ | x − x ; x − x ≤ 0 : Set k = k + 1 and go to Step 1. k k Theorem 3.2 Let {x } be a sequence generated by Algorithm 3.2, If Γ ̸= ∅, then {x } ∗ ∗ 0 globally converges to a solution x such that x = P (x ). proof. The proof of Theorem 3.2 is similar to that of Theorem 3.1, so we provide only a sketch. ∗ k Let x ∈ Γ, from the definition of y , we obtain 2 2 k ∗ k k k ∗ y − x = (1 −  )w +  (z −  e(w ;  )) − x k k k k k ∗ k k = w − x − (1 +  ) (w − z ) k k ⟨ ⟩ 2 2 k ∗ k ∗ k k 2 2 k k = w − x −2(1+ ) w −x ; w −z +(1+ )  w −z ; (24) k k k k which can be written as { } ⟨ ⟩ 2 2 2 k ∗ k k k ∗ k ∗ 2 k k w −x ;w −z =− y −x − w −x −(1+ )  w −z : (25) k k 2(1+ ) k k On the other hand, by the definition of y , we can get 2 2 k ∗ k ∗ k k y −x = z −x − ((1 +  ) − 1)(w − z ) k k ⟨ ⟩ k ∗ k ∗ k k = z − x − 2((1 +  ) − 1) z − x ; w − z k k 2 k k + ((1 +  ) − 1) w − z k k ⟨ ⟩ k ∗ k ∗ k k = z − x − 2((1 +  ) − 1) w − x ; w − z k k 2 2 k k + ((1 +  )  − 1) w − z : (26) k k 2 2 k ∗ k ∗ Since z − x ≤ w − x and the choice of  , then from (25) and (26) we have 1 2 1 2 2 k ∗ k ∗ k k y −x ≤ w − x + ((1 +  ) − 1) w − z k k (1 +  ) (1 +  ) k k k k 1 2 k ∗ ≤ w − x : (27) (1 +  ) k k This implies that 2 2 k ∗ k ∗ y − x ≤ w − x : ∗ 1 1 Then we have x ∈ H , therefore Γ ⊂ H ∩ C. k k { } 2 2 k ∗ ∗ k ∗ k ∗ We know that the sequence w − x is bounded, for ∀x ∈ Γ. Since z − x ≤ w − x , we have k k k ∗ k ∗ w − z ≤ w − x + z − x ; k ∗ ≤ 2 w − x ; (28) { } k k which implies that w − z is a bounded sequence. Then using similar arguments in obtaining (24), one can show that ⟨ ⟩ 2 2 2 k k k k k k k k 2 k k x − y = x −w + 2(1+ ) x − w ; w − z +(1 +  )  w − z ; k k k k which can be written as { } ⟨ ⟩ 2 2 2 k k k k k k k k k k w −z = − x −y − x −w −2(1+ ) x −w ; w −z : k k 2 2 (1 +  ) k k 154 Appl. Math. J. Chinese Univ. Vol. 38, No. 1 From (17) and (18), we have k k lim w − z = 0: (29) k→∞ Note also that 2 2 2 k k k k k k x − z ≤ x − w + w − z : k k Therefore by (17) and (28), we get lim x − z = 0. k→∞ The rest of the convergence proof is identical to that of Theorem 3.1. N 1 2 Remark 3.1 In the two algorithms, a projection from ℜ onto the intersection C ∩ H ∩ H k k k+1 0 needs to be computed, that is, procedure x = P 1 2(x ) at each iteration. Surely, C∩H ∩H k k if the domain set C has a special structure such as a box or a ball, then the next iteration k+1 x can easily be computed. If the domain set C is defined by a set of linear (in) equalities, then computing the projection is equivalent to solving a strictly convex quadratic optimization problem. x4 Numerical experiments In this section, we present two numerical examples to compare the performance of our algorithms with the genaral CQ algorithm. Throughout the computational experiments, the parameters are set as = 0:7,  = 0:6,  = 1:5,  = 0:3, = 1. We define the error as 2 2 ∥x −x ∥ ∥x −x ∥ k+1 k k+1 k −5 2 2 , and use < 10 as the stopping criterion. The implementations are 2 2 ∥x −x ∥ ∥x −x ∥ 2 1 2 1 2 2 done in MATLAB to solve the following examples. { } { } 3 2 3 2 Example 4.1 Let C= x ∈ ℜ x + x + 2x ≤ 0 , Q = x ∈ ℜ x + x −x ≤ 0 . A = 1 3 1 2 3 ones(3). Find x ∈ C with Ax ∈ Q. The numerical results are given in Table 1. To make it explicit, we also measure the performance of the algorithms by plotting the curve of error. The corresponding results are reported in Figure 1 and Figure 2. In the table, k denotes the number of iterations, s denotes the computing time, and x denotes the approximate solution. Table 1. Results for Example 4.1 (Case t = 0:5). 0 ′ 0 ′ 0 ′ x = (0; 1; 2) x = (−2;−1; 3) x = (−3; 1; 2) Algorithm k = 13; s = 0:0156; k = 24; s = 0:0156; k = 12; s = 0:0156; ∗ ′ ∗ ′ ∗ ′ 3.1 x = (−2:9164;−0:5533;−3:2353) x = (−4:0049;−0:7343;−4:9438) x = (−2:8158;−1:0362;−4:9884) Algorithm k = 14; s = 0:0156; k = 13; s = 0:0156; k = 21; s = 0:0156; ∗ ′ ∗ ′ ∗ ′ 3.2 x = (0:5817; 0:2605;−2:4136) x = (3:6451;−1:2376;−8:0093) x = (3:6838;−1:8361;−6:6465) CQ k = 211; s = 0:0313; k = 170; s = 0:0313; k = 208; s = 0:0625; ∗ ′ ∗ ′ ∗ ′ Algorithm x = (−0:0023; 0:0015; 0:0011) x = (−0:0056; 0:0033; 0:0027) x = (−0:0065; 0:0035; 0:0032) DANG Ya-zheng, et al. New hybrid inertial CQ projection algorithms with... 155 0 ′ Figure 1. The performance of our algorithms and the CQ algorithm (Case x = (−1; 2; 4) and t = 0:5 ). 0 ′ Figure 2. The performance of Algorithms 3.1 (Case x = (−5; 2; −3) ). In the view of Table 1 and Figure 1, it is easy to observe that our algorithms have better performance than the general CQ Algorithm. It appears that our algorithms need fewer iter- ations and converge more quickly than the general CQ Algorithm. In addition, by observing Figure 2, we find that the magnitude of inertial term has a certain effect on the number of iterations. Example 4.2 Let A = (a ) , a ∈ (0; 1) be a random matrix, M,N be two positive ij M×N ij N 2 2 M integers. C = {x ∈ ℜ | x ≤ r }, Q = {x ∈ ℜ |x ≤ b}. To ensure the existence of the l=1 solution of the problem, the vector b is generated by using the following way: Given a random N-dimensional negative vector (each component is negative) z ∈ C, r = ∥z∥, taking b = Az. Find x ∈ C with Ax ∈ Q. 156 Appl. Math. J. Chinese Univ. Vol. 38, No. 1 The numerical results of Example 4.2 can be seen from Table 2. In the table, k denotes the number of iterations, s denotes the computing time. Table 2. Results for Example 4.2. M; N t Algorithm 3.1 Algorithm 3.2 CQ Algorithm 0.2 k = 63; s = 0:0938 k = 67; s = 0:0938 M=20, N=10 0.4 k = 61; s = 0:0625 k = 47; s = 0:0625 k = 308; s = 0:1250 0 ′ x = (1; 1; 1; 0; 0; · · · ; 0) 0.6 k = 59; s = 0:0625 k = 30; s = 0:0625 0.1 k = 44; s = 0:1875 k = 23; s = 0:1250 M=100, N=90 0.2 k = 43; s = 0:1875 k = 19; s = 0:1250 k = 167; s = 0:3438 0 ′ x = (1; 1; 1; 1; 1; 0; · · · ; 0) 0.4 k = 42; s = 0:1875 k = 16; s = 0:0938 As can be seen from the numerical results in Table 2, in the case of higher dimensions, our algorithms are still effective, and they still converge faster than the general CQ algorithm. x5 Some concluding remarks This paper presentes two hybrid inertial CQ projection algorithms with different rules of stepsize selection for solving SFP. Based on the hybrid CQ projection algorithm, we add the inertial term in the first projection step to accelerate the convergence of the algorithm. The main difference between Algorithm 3.1 and Algorithm 3.2 is the projection region obtained by different line-search methods in the second projection step. According to our convergence theory and also confirmed by numerical simulations, we can see that our proposed algorithms have better convergence properties than the general CQ algorithm. Open Access This article is licensed under a Creative Commons Attribution 4.0 In- ternational License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the articles Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the articles Creative Commons licence and your intended use is not permitted by statutory reg- ulation or exceeds the permitted use, you will need to obtain permission directly from the copy- right holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. References [1] Q H Ansari, A Rehan. Split feasibility and fixed point problems, Nonlinear Analysis, 2014, 281-322. DANG Ya-zheng, et al. New hybrid inertial CQ projection algorithms with... 157 [2] C Byrne. Iterative oblique projection onto convex sets and the split feasibility problem, Inverse Problems, 2002, 18(2): 441-453. [3] C Byrne. A unified treatment of some iterative algorithms in signal processing and image reconstruction, Inverse Problems, 2004, 20(1): 103-120. [4] Y Censor, T Elfving. A multiprojection algorithm using Bregman projections in a product space, Numerical Algorithms, 1994, 8(2): 221-239. [5] P L Combettes, V R Wajs. Signal recovery by proximal forward-backward splitting, Multi- scale Modeling and Simulation, 2005, 4(4): 1168-1200. [6] A Cegielski, S Reich, R Zalas. Strong and linear convergence of the CQ-method via the regularity of Landweber operators, Optimization, 2020, 69(3): 605-636. [7] Y Z Dang, Y Gao. The strong convergence of a KM-CCQ-like algorithm for a split feasibility problem, Inverse Problems, 2011, 27(1): 015007. [8] Y Z Dang, Y Gao. Bi-extrapolated subgradient projection algorithm for solving multiple-sets split feasibility problem, Applied Mathematics, 2014, 29(3): 283-294. [9] Y Z Dang, Z H Xue, B Wang. Hybrid CQ projection algorithm with line-search process for the split feasibility problem, Journal of Inequalities and Applications, 2016. [10] E C Godwin, C Izuchukwu, O T Mewomo. An inertial extrapolation method for solving gen- eralized split feasibility problems in real hilbert spaces, Bollettino dell’Unione Matematica Italiana, 2021. [11] Y Shehu, F U Ogbuisi. Convergence analysis for proximal split feasibility problems and fixed point problems, J Appl Math Comput, 2015, 48: 221-239. [12] G Lopez, V Martin-Marquez, F H Wang, H K Xu. Solving the split feasibility problem without prior knowledge of matrix norms, Inverse Problems, 2012, 28(8): 374-389. [13] H Y Li, Y L Wu, F H Wang, X L Qin. New Inertial Relaxed Algorithms for Solving Split Feasibility Problems in Hilbert Spaces, Journal of Mathematics, 2021. [14] T V Nguyen, C Prasit, S Suthep. A new CQ algorithm for solving split feasibility problems in Hilbert spaces, Malaysian Mathematical Sciences Society, 2020, 42: 2517-2534. [15] B T Polyak. Some methods of speeding up the convergence of iteration methods, Mathe- matical Physics, 1964, 4(5): 1-17. [16] B Qu, N H Xiu. A note on the CQ algorithm for the split feasibility problem, Inverse Problems, 2005, 21(5): 1655-1665. [17] B Qu, N H Xiu. A new halfspace-relaxation projection method for the split feasibility prob- lem, Linear Algebra and its Applications, 2008, 428: 1218-1229. 158 Appl. Math. J. Chinese Univ. Vol. 38, No. 1 [18] Y Shehu, Q L Dong, L L Liu. Global and linear convergence of alternated inertial methods for split feasibility problems, Revista de la Real Academia de Ciencias Exactas, F´ısicas y Naturales, Serie A-Matem´aticas, 2021, 115(2): 53. [19] A Gibali, Y Shehu. An efficient iterative method for finding common fixed point and vari- ational inequalities in Hilbert spaces, Optimization, 2019, 68(1): 13-32. [20] M Tian, H F Zhang. The regularized CQ algorithm without a priori knowledge of operator norm for solving the split feasibility problem, Journal of Inequalities and Applications, [21] G H Taddele, P Kumam, A G Gebrie. An inertial extrapolation method for multiple-set split feasibility problem, Journal of Inequalities and Applications, 2020. [22] H K Xu. A variable Krasnosel’skii-Mann algorithm and the multiple-set split feasibility problem, Inverse Problems, 2006, 22(6): 2021-2034. [23] A L Yan, G Y Wang, N H Xiu. Robust solutions of split feasibility problem with uncertain linear operator, Journal of Industrial and Management Optimization, 2007, 3(4): 749-761. [24] Y H Yao, J G Wu, Y C Liou. Regularized methods for the split feasibility problem, Abstract and Applied Analysis, 2012. [25] W X Zhang, D Han, Z B Li. A self-adaptive projection method for solving the multiple-sets split feasibility problem, Inverse Problems, 2009, 25(11), DOI: 10.1088/0266- 5611/25/11/115001. [26] J L Zhao, Q Z Yang. Self-adaptive projection methods for the multiple-sets split feasibility problem, Inverse Problems, 2011, 27(3), DOI: 10.1088/0266-5611/27/3/035009. [27] Y Zhou, Z Haiyun, P Wang. Iterative methods for finding the minimum-norm solution of the standard monotone variational inequality problems with applications in Hilbert spaces, Journal of Inequalities and Applications, 2015. School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China. Email: jgdyz@163.com http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Applied Mathematics-A Journal of Chinese Universities Springer Journals

New hybrid inertial CQ projection algorithms with line-search process for the split feasibility problem

Download PDF
15 pages

Loading next page...
 
/lp/springer-journals/new-hybrid-inertial-cq-projection-algorithms-with-line-search-process-shO03kHkd3

References (28)

Publisher
Springer Journals
Copyright
Copyright © The Author(s) 2023
ISSN
1005-1031
eISSN
1993-0445
DOI
10.1007/s11766-023-4464-7
Publisher site
See Article on Publisher Site

Abstract

Appl. Math. J. Chinese Univ. 2023, 38(1): 144-158 New hybrid inertial CQ projection algorithms with line-search process for the split feasibility problem DANG Ya-zheng WANG Long YANG Yao-heng Abstract. In this paper, we propose two hybrid inertial CQ projection algorithms with line- search process for the split feasibility problem. Based on the hybrid CQ projection algorithm, we rstly add the inertial term into the iteration to accelerate the convergence of the algorithm, and adopt exible rules for selecting the stepsize and the shrinking projection region, which makes an optimal stepsize available at each iteration. The shrinking projection region is the intersection of three sets, which are the set C and two hyperplanes. Furthermore, we modify the Armijo-type line-search step in the presented algorithm to get a new algorithm.The algorithms are shown to be convergent under certain mild assumptions. Besides, numerical examples are given to show that the proposed algorithms have better performance than the general CQ algorithm. x1 Introduction Split Feasibility Problem (SFP) was firstly introduced by Censor and Elfving [4] in 1994, which is to find a point x satisfying ∗ ∗ x ∈ C ; Ax ∈ Q; (1) N M where C and Q are nonempty convex sets in ℜ and ℜ , respectively, and A is an M by N real matrix. Problem (1) together with many variants of it has received much attention from opti- mization community due to its broad applications to many disciplines, such as signal processing, image reconstruction, intensity-modulated radiation therapy, etc. [1,2,3,7]. Therefore, many ef- fective methods have been proposed to solve the problem (1), see [5,6,8,16,17,22,23]. A very suc- cessful algorithm that solves the SFP seems to be the CQ algorithm of Byrne [2] which is defined as follows: Denote P by the orthogonal projection onto C, that is, P (y) = argmin ||x−y||, c C x∈C for y ∈ C; then take an initial point arbitrarily and define the iterative step by Received: 2021-05-26. Revised: 2022-03-17. MR Subject Classi cation: 47J05, 47J25. Keywords: split feasible problem, inertial, Armijo-type line-search technique, projection algorithm, conver- gence. Digital Object Identi er(DOI): https://doi.org/10.1007/s11766-023-4464-7. Supported by the National Natural Science Foundation of China(72071130). *Corresponding author. ⃝The Author(s) 2023. DANG Ya-zheng, et al. New hybrid inertial CQ projection algorithms with... 145 k+1 T k x = P (I − A (I − P )A)(x ); (2) C Q where 0 < < 2=∥A∥ . The CQ algorithm (2) can be regarded as a special case of the gradient projection method if we consider the convex minimization problem min ∥(I − P ) Ax∥ : x∈C Observe that, the choice of stepsize in CQ algorithm depends on the norm of the operator, which is not a simple work. To avoid this computation, some modifications of the CQ algorithm and the self-adaptive method have been developed for solving the SFP. L pez et al. [12] introduced a new way of selecting the stepsizes for solving SFP (1) such that the information of operator norm is not necessary. Motivated and inspired by the work of [12,20,24,27], the authors of [14] introduced a self-adaptive CQ-type algorithm for solving the SFP in the setting of infinite dimensional real Hilbert spaces. Inspired by the projection and contraction method and the hybrid descent approximation method, Gibali et al. [11] investigated the problem of finding a common solution to a fixed point problem involving demi-contractive operator and a variational inequality with monotone and Lipschitz continuous mapping in real Hilbert spaces. Shehu et al. [19] introduced iterative algorithms and proved their strong convergence for solving proximal split feasibility problems and fixed point problems for k-strictly pseudocontractive mappings in Hilbert spaces. Dang et al. [9] proposed a hybrid CQ projection algorithm with Armijo-type line-search step, which is different from the general self-adaptive Armijo-type procedure [25,26]. On the other hand, in [15], Polyak firstly proposed the inertial term as an acceleration process to solve the smooth convex minimization problem. In recent years, scholars have proposed some inertial iterative algorithms for solving the SFP. Based on [12], Taddele et al. [21] proposed an iterative algorithm with inertial extrapolation to approximate the solution of multiple-set SFP. Shehu et al. [18] introduced new CQ methods with alternated inertial procedure and self- adaptive stepsize for solving SFP. Li et al. [13] proposed two inertial relaxed CQ algorithms for solving the SFP in real Hilbert spaces according to the previous experience of applying inertial technology to the algorithm. Godwin et al [10] introduced a new inertial extrapolation method for solving a certain class of generalized SFP without the prior knowledge of the operator norm or the coefficient of an underlying operator. Inspired by the works mentioned above, we propose two hybrid inertial CQ projection algorithms with line-search process for the split feasibility problem. The main features of the proposed algorithms as follows: 1. Based on [9], we incorporate the inertial term into the iteration to construct Algorithm 3.1, which improves the efficiency of convergence. Furthermore, we adjust the Armijo-type line-search step in Algorithm 3.1 to get Algorithm 3.2. 2. Algorithms perform a computationally inexpensive Armijo-type linear search along the search direction to generate a hyperplane. 3. The next iteration is generated by the projection of the initial point on the intersection of the set C with the hyperplanes, which makes an optimal stepsize available at each iteration. 146 Appl. Math. J. Chinese Univ. Vol. 38, No. 1 Different from the algorithms in [11,19], two hyperplanes are constructed in our algorithms to generate the shrinking projection region. The paper is organized as follows. In section 2, Some useful definitions and results are collected for the convergence analysis of the proposed algorithms. In Section 3, we propose two hybrid inertial CQ projection algorithms for the split feasibility problem and show their convergence. In Section 4, numerical experiments are reported to conclude the effectiveness of our algorithms. Finally, some conclusions are given in Section 5. x2 Preliminaries We denote by I the identity operator and by Fix(T ) the set of fixed points of an operator T , that is, Fix(T ) := {x|x = Tx}: Recall that a mapping T : ℜ → ℜ is said to be monotone if ⟨T (x) − T (y); x − y⟩ ≥ 0; ∀x; y ∈ ℜ : For a monotone mapping T , ⟨T (x) − T (y); x − y⟩ =0 iff x = y, then it is said to be strictly monotone. n n A mapping T : ℜ → ℜ is called non-expansive if ∥T (x) − T(y)∥ ≤ ∥x − y∥ ; ∀x; y ∈ ℜ : Lemma 2.1 [9,13] Let Ω be a nonempty closed and convex subset in H. Then, for any x; y ∈ H and z ∈ Ω, the following hold: (1) ⟨x − P (x); z − P (x)⟩ ≤ 0. Ω Ω (2) ∥P (x) − P (y)∥ ≤ ⟨P (x) − P (y); x − y⟩. Ω Ω Ω Ω (3) ∥P (x) − P (y)∥ ≤ ∥x − y∥ ; ∀x; y ∈ ℜ , or more precisely, Ω Ω 2 2 2 ∥P (x) − P (y)∥ ≤ ∥x − y∥ − ∥P (x) − x + y − P (y)∥ : Ω Ω Ω Ω 2 2 2 (4) ∥P (x) − z∥ ≤ ∥x − z∥ − ∥P (x) − x∥ . Ω Ω Remark 2.1 In fact, the projection property (1) also provides a sufficient and necessary con- dition for a vector u ∈ K to be the projection of the vector x; that is,u = P (x) if and only if ⟨u − z; x − u⟩ ≥ 0; ∀z ∈ K: Lemma 2.2 [18] The following statements hold in ℜ : 2 2 2 (1) ∥x + y∥ = ∥x∥ + 2 ⟨x; y⟩ + ∥y∥ , for all x; y ∈ ℜ . DANG Ya-zheng, et al. New hybrid inertial CQ projection algorithms with... 147 2 2 (2) ∥x + y∥ ≤ ∥x∥ + 2 ⟨y; x + y⟩, for all x; y ∈ ℜ . Lemma 2.3 [3] Let f(x) := ∥(I − P )Ax∥ , x ∈ C. Then (1) f is convex and differentiable. T N (2) ∇f(x) = A (I − P )Ax, x ∈ ℜ . (3) f is lower semicontinuous on ℜ . (4) ∇f Lipschitz continuous with Lipschitz constant ∥A∥ . Throughout the paper, the solution set of split feasibility problem is denoted by Γ, that is ∗ ∗ Γ := {x ∈ C|Ax ∈ Q}: (3) x3 Algorithms and their convergence analysis Let F(x) := (A (I − P )A)(x): Then we know that F is Lipschitz-continuous with constant ∥A∥ . We first note that the solution set coincides with zeros of the following projected residual function: e(x) := x − P (x − F(x)); e(x; ) := x − P (x − F (x)); C C with this definition, we have e(x; 1) = e(x), and x ∈ Γ if and only if e(x; ) = 0. For any x ∈ ℜ and ≥ 0, define x( ) = P (x − F (x)); e(x; ) = x − x( ): The following lemma is useful for the convergence analysis in the next section. N N N Lemma 3.1 [25] Let F be a mapping from ℜ into ℜ . For any x ∈ ℜ and ≥ 0, we have min{1; } ∥e(x; 1)∥ ≤ ∥e(x; )∥ ≤ max{1; } ∥e(x; 1)∥ : Now, we describe our first algorithm as follows: Algorithm 3.1 0 1 N Step 0. Choose arbitrary initial points x ; x ∈ ℜ , and parameters  > 0, t ∈ (0; 1), 0 k ∈ (0; 1),  ∈ (0; 1), " ∈ (0; 1) and  > 1, and set k = 0. k−1 k Step 1. Assuming x , x have been constructed, compute k k k k−1 w = P [x + t (x − x )]; (4) C k k k k z = P [w −  F(w )]; (5) C k 148 Appl. Math. J. Chinese Univ. Vol. 38, No. 1 { } where  is a positive number satisfying " <  ≤ min − "; 1 . Obviously, e(w ;  ) = k k T k (A A) k k k w − z . If e(w ;  ) = 0, then stop; Step 2. Compute k k k y = w −  e(w ;  ); (6) k k where  =  , with m being the smallest nonnegative integer m satisfying k k k ⟨ ⟩ k m k k k F(w −  e(w ;  )); e(w ;  ) ≥ e(w ;  ) : (7) k k k k Step 3. Compute k+1 0 x = P 1 2(x ); (8) C∩H ∩H k k where { } 2 2 1 N k k H = x ∈ ℜ | y − x ≤ w − x ; { ⟨ ⟩ } 2 N k 0 k H = x ∈ ℜ | x − x ; x − x ≤ 0 : Set k = k + 1 and go to Step 1. Before establishing the global convergence of Algorithm 3.1, we first give the following lemmas. Lemma 3.2 There exists a nonnegative number m satisfying (7), for all k ≥ 0. proof. Suppose that, for some k, (7) is not satisfied for any integer m , that is, ⟨ ⟩ k m k k k F(w −  e(w ;  )); e(w ;  ) ≤ e(w ;  ) : (9) k k k k By the definition of e(w ;  ), and Lemma 2.1 we know that ⟨ ⟩ k k k k k k k P (w −  F(w )) − (w −  F(w )); w − P (w −  F(w )) ≥ 0: C k k C k Then ⟨ ⟩ 1 2 k k k F(w ); e(w ;  ) ≥ e(w ;  ) > 0: (10) k k { } Since ∈ (0; 1) and " <  ≤ min − "; 1 , from (9) we get k T (A A) k m k k lim (w −  e(w ;  )) = w : k k m→∞ Hence, ⟨ ⟩ 2 2 k k k k F(w ); e(w ;  ) ≤ e(w ;  ) < e(w ;  ) : (11) k k k k k But (11) contradicts (10) because e(w ;  ) ≥ 0. Hence, (7) is satisfied for some integer m. Lemma 3.3 If the solution set Γ ̸= ∅, then Γ ⊂ H ∩ C for all k ≥ 0. k DANG Ya-zheng, et al. New hybrid inertial CQ projection algorithms with... 149 proof. Let x ∈ Γ, then 2 2 k ∗ k T k ∗ z − x = P (w −  A (I − P )Aw ) − x C k Q k ∗ T k ≤ w − x −  A (I − P )Aw k Q ⟨ ⟩ 2 2 k ∗ k ∗ T k 2 T k = w − x − 2 w − x ; A (I − P )Aw + A (I−P )Aw k Q k Q ⟨ ⟩ 2 2 k ∗ k ∗ k 2 T k = w − x − 2 A(w − x ); (I − P )Aw + A (I−P )Aw k Q k Q ⟨ ⟩ k ∗ k k k ∗ k = w − x − 2 Aw − P Aw + P Aw − Ax ; (I − P )Aw k Q Q Q 2 T k +  A (I − P )Aw k Q 2 2 k ∗ k = w − x − 2 (I − P )Aw k Q ⟨ ⟩ k ∗ k 2 T k − 2 P Aw − Ax ; (I − P )Aw +  A (I − P )Aw : k Q Q k Q From Lemma 2.1, we obtain { } 2 2 2 2 k ∗ k ∗ k T k z − x ≤ w − x −  2 (I − P )Aw −  A (I − P )Aw k Q k Q ( ) 2 2 2 k ∗ T k ≤ w − x −  −  A (I − P )Aw (12) k k Q (A A) k ∗ ≤ w − x : (13) Also, it follows from the definition of y that 2 2 k ∗ k ∗ k k y − x = w − x −  (w − z ) ⟨ ⟩ 2 2 k ∗ k ∗ k k 2 k k = w − x − 2 w − x ; w − z +  w − z ; k k which can be rewritten as { } ⟨ ⟩ 1 2 2 2 k ∗ k k k ∗ k ∗ 2 k k w − x ; w − z = − y − x − w − x − w − z : (14) On the other hand, by the definition of y , we have 2 2 k ∗ k ∗ k k y − x = w − x −  (w − z ) k ∗ k k = z − x + (1 −  )(w − z ) ⟨ ⟩ 2 2 k ∗ k ∗ k k 2 k k = z −x +2(1− ) z − x ; w − z + (1 −  ) w − z k k ⟨ ⟩ 2 2 k ∗ k k k ∗ k k 2 k k = z −x +2(1− ) z −w +w −x ; w −z +(1− ) w −z k k ⟨ ⟩ 2 2 k ∗ k ∗ k k 2 k k = z −x +2(1− ) w − x ; w − z +( − 1) w − z : (15) k k 2 2 k ∗ k ∗ Since z − x ≤ w − x , then by (14) and (15) we get 1 2 2 1 2 2 k ∗ k ∗ k ∗ k k y − x = z − x +( − 1) w − x + ( − 1) w − z k k 1 1 2 2 2 k ∗ k ∗ k ∗ ≤ w − x + ( − 1) w − x = w − x : k k Hence 2 2 k ∗ k ∗ y − x ≤ w − x ; ∗ 1 1 which implies x ∈ H . Moreover, it is easy to see that Γ ⊂ H ∩ C, ∀k ≥ 0. k k 1 2 The following lemma says that if the solution set is nonempty, then Γ ⊂ H ∩ H ∩ C and k k 150 Appl. Math. J. Chinese Univ. Vol. 38, No. 1 1 2 thus H ∩ H ∩ Cis a nonempty set. k k 1 2 Lemma 3.4 [9, Lemma 3.4] If the solution set Γ ̸= ∅, then Γ ⊂ H ∩ H ∩ C for all k ≥ 0. k k 1 2 For the case that the solution set is empty, we have that H ∩H ∩C is also nonempty from k k the following lemma, which implies the feasibility of Algorithm 3.1. 1 2 Lemma 3.5 Suppose that Γ = ∅, then H ∩ H ∩ C ̸= ∅ for all k ≥ 0. k k { } Lemma 3.6 Let x be a sequence generated by algorithm 3.1. Then k k (i) lim x − w = 0; k→∞ k k (ii) lim x − y = 0; k→∞ k k (iii) lim x − z = 0; k→∞ T k (iv) lim A (I − P )Aw = 0. k→∞ { } proof. (i) From [9, theorem 3.1], we know that x is a bounded sequence and convergent, which implies that k+1 k lim x − x = 0: (16) k→∞ By the definition of w , it follows that , k k k k k k−1 x − w = x − P [x + t (x − x )] C k k k k k−1 ≤ x − [x + t (x − x )] k k−1 = |t | · x − x : Therefore, from the selection of parameter t and (16), we have k k lim x − w = 0: (17) k→∞ (ii) From (16) and (17), we obtain k+1 k k+1 k k k x − w = x − x + x − w k+1 k k k ≤ x − x + x − w → 0 as k → ∞; k+1 1 which with x ∈ H implies that k+1 k lim x − y = 0: k→∞ k k k k+1 k+1 k Again, since x − y ≤ x − x + x − y , it then follows that k k lim x − y = 0: (18) k→∞ k k k k k k (iii) Since w − y ≤ w − x + x − y , then form (17) and (18) we have k k lim w − y = 0: (19) k→∞ From the definition of y , we get ( ) k k k k k w − y = e(w ;  )= w − z : k k k DANG Ya-zheng, et al. New hybrid inertial CQ projection algorithms with... 151 Then, note that from the construction of  and (19), we have k k k k w − z = w − y → 0 as k → ∞: (20) | | Hence, from (17) and (20), we get k k k k k k x − z ≤ x − w + w − z → 0 as k → ∞: (iv) Observe that by (12) ( ) 2 2 2 2 T k k ∗ k ∗ −  A (I − P )Aw ≤ w − x − z − x k k Q (A A) ⟨ ⟩ k k k ∗ k k = w − z + 2 z − x ; w − z ⟨ ⟩ k ∗ k k ≤ 2 z − x ; w − z : { } k k From (i), we know that x is a convergent and bounded sequence. By the definition of w , { } 2 2 k ∗ ∗ k ∗ k ∗ the sequence w − x is bounded, for ∀x ∈ Γ. And since z − x ≤ w − x , we { } k ∗ conclude that z − x is bounded. Then, from (20), it follows that ( ) T k lim  −  A (I − P )Aw = 0: (21) k k Q k→∞  (A A) ( ) This together with the fact that lim  −  ̸= 0 further implies k T k (A A) k→∞ T k lim A (I − P )Aw = 0: (22) k→∞ We now prove our main convergence result. { } Theorem 3.1 Suppose the solution set Γ is nonempty, then the sequence x generated by Algorithm 3.1 is bounded, and all its cluster points belong to the solution set. Moreover, the { } k ∗ ∗ 0 sequence x globally converges to a solution x such that x = P (x ). k 0 proof. We have already kown in (i) that lim x − x exists. k→∞ Now, we show that x → x¯ ∈ Γ: Let m; n ∈ N, since n 0 x = P 1 2 (x ); H ∩H ∩C n−1 n−1 then 2 2 m n m 0 n 0 ∥x − x ∥ ≤ x − x − x − x : m n k Hence lim ∥x − x ∥ =0. Thus x is a Cauchy sequence in C. Since C is nonempty k≥2 m;n→∞ N k convex sets in ℜ , it implies that there exists x¯ ∈ C such that x → x¯ as k → ∞: More so, k k k k since x − w → 0, then w → x¯ and by the linearity of A, we have Aw → Ax¯. Also from (22), we have 2 2 T k T lim A (I − P )Aw = A (I − P )Ax =0: Q Q k→∞ Since the projected residual function k k k T k e(x ) = x − P (x − A (I − P )Ax ); C Q then, we have k T e(x¯) = lim e(x ) = x¯ − P (x¯ − A (I − P )Ax¯)=x¯ − P (x¯)=0: C Q C k→∞ 152 Appl. Math. J. Chinese Univ. Vol. 38, No. 1 Thus x¯ is a solution of problem (1). { } Now, we prove that the sequence x converges to a point contained in Γ. ( ) ∗ 0 ∗ Let x = P x . Since x ∈ Γ, by Lemma 3.4 we have ∗ 1 2 x ∈ H ∩ H ∩ C; ∀j: k −1 k −1 j j So, by the iterative sequence of Algorithm 3.1 we have k 0 ∗ 0 x − x ≤ x − x : Thus 2 2 k ∗ k 0 0 ∗ j j x − x + x − x x − x = ⟨ ⟩ k 0 0 ∗ k 0 0 ∗ j j = x − x + x − x + 2 x − x ; x − x ⟨ ⟩ 2 2 ∗ 0 0 ∗ k 0 0 ∗ ≤ x − x + x − x + 2 x − x ; x − x : Letting j → ∞ , we have ⟨ ⟩ ∗ 0 ∗ 0 0 ∗ ∥x¯ − x ∥ ≤ 2 x − x + 2 x¯ − x ; x − x ⟨ ⟩ ∗ 0 ∗ = 2 x¯ − x ; x − x ≤ 0; ∗ 0 where the last inequality is due to Lemma 2.1 and the fact that x = P (x ) and x¯ ∈ Γ. So, ( ) ∗ 0 x¯ = x = P x : { } ( ) k 0 Thus, the sequence x has a unique cluster point P x , which shows the global convergence { } of x . Now, we put another line search method in the Algorithm 3.1 to get a new algorithm. Algorithm 3.2 0 1 N Step 0. Choose arbitrary initial points x ; x ∈ ℜ , and parameters  > 0, t ∈ (0; 1), 0 k ∈ (0; 1),  ∈ (0; 1), " ∈ (0; 1), and  > 1, and set k = 0. k−1 k Step 1. Assuming x , x have been constructed, compute k k k k−1 w = P [x + t (x − x )]; C k k k k z = P [w −  F(w )]; C k { } 2 k where  is a positive number satisfying " <  ≤ min − "; 1 . We have e(w ;  ) = k k T k (A A) k k k w − z . If e(w ;  ) = 0, then stop; Step 2. Compute k k k k y = (1 −  )w +  (z −  e(w ;  )); (23) k k k k 1 m where " < < and  =  with m being the smallest nonnegative integer m satis- k k k k (1+ ) fying ⟨ ⟩ k m k k k F(w −  e(w ;  )); e(w ;  ) ≥ e(w ;  ) : k k k k Step 3. Compute k+1 0 x = P 1 2(x ); C∩H ∩H k k where { } 2 2 1 N k k H = x ∈ ℜ | y − x ≤ w − x ; k DANG Ya-zheng, et al. New hybrid inertial CQ projection algorithms with... 153 { ⟨ ⟩ } 2 N k 0 k H = x ∈ ℜ | x − x ; x − x ≤ 0 : Set k = k + 1 and go to Step 1. k k Theorem 3.2 Let {x } be a sequence generated by Algorithm 3.2, If Γ ̸= ∅, then {x } ∗ ∗ 0 globally converges to a solution x such that x = P (x ). proof. The proof of Theorem 3.2 is similar to that of Theorem 3.1, so we provide only a sketch. ∗ k Let x ∈ Γ, from the definition of y , we obtain 2 2 k ∗ k k k ∗ y − x = (1 −  )w +  (z −  e(w ;  )) − x k k k k k ∗ k k = w − x − (1 +  ) (w − z ) k k ⟨ ⟩ 2 2 k ∗ k ∗ k k 2 2 k k = w − x −2(1+ ) w −x ; w −z +(1+ )  w −z ; (24) k k k k which can be written as { } ⟨ ⟩ 2 2 2 k ∗ k k k ∗ k ∗ 2 k k w −x ;w −z =− y −x − w −x −(1+ )  w −z : (25) k k 2(1+ ) k k On the other hand, by the definition of y , we can get 2 2 k ∗ k ∗ k k y −x = z −x − ((1 +  ) − 1)(w − z ) k k ⟨ ⟩ k ∗ k ∗ k k = z − x − 2((1 +  ) − 1) z − x ; w − z k k 2 k k + ((1 +  ) − 1) w − z k k ⟨ ⟩ k ∗ k ∗ k k = z − x − 2((1 +  ) − 1) w − x ; w − z k k 2 2 k k + ((1 +  )  − 1) w − z : (26) k k 2 2 k ∗ k ∗ Since z − x ≤ w − x and the choice of  , then from (25) and (26) we have 1 2 1 2 2 k ∗ k ∗ k k y −x ≤ w − x + ((1 +  ) − 1) w − z k k (1 +  ) (1 +  ) k k k k 1 2 k ∗ ≤ w − x : (27) (1 +  ) k k This implies that 2 2 k ∗ k ∗ y − x ≤ w − x : ∗ 1 1 Then we have x ∈ H , therefore Γ ⊂ H ∩ C. k k { } 2 2 k ∗ ∗ k ∗ k ∗ We know that the sequence w − x is bounded, for ∀x ∈ Γ. Since z − x ≤ w − x , we have k k k ∗ k ∗ w − z ≤ w − x + z − x ; k ∗ ≤ 2 w − x ; (28) { } k k which implies that w − z is a bounded sequence. Then using similar arguments in obtaining (24), one can show that ⟨ ⟩ 2 2 2 k k k k k k k k 2 k k x − y = x −w + 2(1+ ) x − w ; w − z +(1 +  )  w − z ; k k k k which can be written as { } ⟨ ⟩ 2 2 2 k k k k k k k k k k w −z = − x −y − x −w −2(1+ ) x −w ; w −z : k k 2 2 (1 +  ) k k 154 Appl. Math. J. Chinese Univ. Vol. 38, No. 1 From (17) and (18), we have k k lim w − z = 0: (29) k→∞ Note also that 2 2 2 k k k k k k x − z ≤ x − w + w − z : k k Therefore by (17) and (28), we get lim x − z = 0. k→∞ The rest of the convergence proof is identical to that of Theorem 3.1. N 1 2 Remark 3.1 In the two algorithms, a projection from ℜ onto the intersection C ∩ H ∩ H k k k+1 0 needs to be computed, that is, procedure x = P 1 2(x ) at each iteration. Surely, C∩H ∩H k k if the domain set C has a special structure such as a box or a ball, then the next iteration k+1 x can easily be computed. If the domain set C is defined by a set of linear (in) equalities, then computing the projection is equivalent to solving a strictly convex quadratic optimization problem. x4 Numerical experiments In this section, we present two numerical examples to compare the performance of our algorithms with the genaral CQ algorithm. Throughout the computational experiments, the parameters are set as = 0:7,  = 0:6,  = 1:5,  = 0:3, = 1. We define the error as 2 2 ∥x −x ∥ ∥x −x ∥ k+1 k k+1 k −5 2 2 , and use < 10 as the stopping criterion. The implementations are 2 2 ∥x −x ∥ ∥x −x ∥ 2 1 2 1 2 2 done in MATLAB to solve the following examples. { } { } 3 2 3 2 Example 4.1 Let C= x ∈ ℜ x + x + 2x ≤ 0 , Q = x ∈ ℜ x + x −x ≤ 0 . A = 1 3 1 2 3 ones(3). Find x ∈ C with Ax ∈ Q. The numerical results are given in Table 1. To make it explicit, we also measure the performance of the algorithms by plotting the curve of error. The corresponding results are reported in Figure 1 and Figure 2. In the table, k denotes the number of iterations, s denotes the computing time, and x denotes the approximate solution. Table 1. Results for Example 4.1 (Case t = 0:5). 0 ′ 0 ′ 0 ′ x = (0; 1; 2) x = (−2;−1; 3) x = (−3; 1; 2) Algorithm k = 13; s = 0:0156; k = 24; s = 0:0156; k = 12; s = 0:0156; ∗ ′ ∗ ′ ∗ ′ 3.1 x = (−2:9164;−0:5533;−3:2353) x = (−4:0049;−0:7343;−4:9438) x = (−2:8158;−1:0362;−4:9884) Algorithm k = 14; s = 0:0156; k = 13; s = 0:0156; k = 21; s = 0:0156; ∗ ′ ∗ ′ ∗ ′ 3.2 x = (0:5817; 0:2605;−2:4136) x = (3:6451;−1:2376;−8:0093) x = (3:6838;−1:8361;−6:6465) CQ k = 211; s = 0:0313; k = 170; s = 0:0313; k = 208; s = 0:0625; ∗ ′ ∗ ′ ∗ ′ Algorithm x = (−0:0023; 0:0015; 0:0011) x = (−0:0056; 0:0033; 0:0027) x = (−0:0065; 0:0035; 0:0032) DANG Ya-zheng, et al. New hybrid inertial CQ projection algorithms with... 155 0 ′ Figure 1. The performance of our algorithms and the CQ algorithm (Case x = (−1; 2; 4) and t = 0:5 ). 0 ′ Figure 2. The performance of Algorithms 3.1 (Case x = (−5; 2; −3) ). In the view of Table 1 and Figure 1, it is easy to observe that our algorithms have better performance than the general CQ Algorithm. It appears that our algorithms need fewer iter- ations and converge more quickly than the general CQ Algorithm. In addition, by observing Figure 2, we find that the magnitude of inertial term has a certain effect on the number of iterations. Example 4.2 Let A = (a ) , a ∈ (0; 1) be a random matrix, M,N be two positive ij M×N ij N 2 2 M integers. C = {x ∈ ℜ | x ≤ r }, Q = {x ∈ ℜ |x ≤ b}. To ensure the existence of the l=1 solution of the problem, the vector b is generated by using the following way: Given a random N-dimensional negative vector (each component is negative) z ∈ C, r = ∥z∥, taking b = Az. Find x ∈ C with Ax ∈ Q. 156 Appl. Math. J. Chinese Univ. Vol. 38, No. 1 The numerical results of Example 4.2 can be seen from Table 2. In the table, k denotes the number of iterations, s denotes the computing time. Table 2. Results for Example 4.2. M; N t Algorithm 3.1 Algorithm 3.2 CQ Algorithm 0.2 k = 63; s = 0:0938 k = 67; s = 0:0938 M=20, N=10 0.4 k = 61; s = 0:0625 k = 47; s = 0:0625 k = 308; s = 0:1250 0 ′ x = (1; 1; 1; 0; 0; · · · ; 0) 0.6 k = 59; s = 0:0625 k = 30; s = 0:0625 0.1 k = 44; s = 0:1875 k = 23; s = 0:1250 M=100, N=90 0.2 k = 43; s = 0:1875 k = 19; s = 0:1250 k = 167; s = 0:3438 0 ′ x = (1; 1; 1; 1; 1; 0; · · · ; 0) 0.4 k = 42; s = 0:1875 k = 16; s = 0:0938 As can be seen from the numerical results in Table 2, in the case of higher dimensions, our algorithms are still effective, and they still converge faster than the general CQ algorithm. x5 Some concluding remarks This paper presentes two hybrid inertial CQ projection algorithms with different rules of stepsize selection for solving SFP. Based on the hybrid CQ projection algorithm, we add the inertial term in the first projection step to accelerate the convergence of the algorithm. The main difference between Algorithm 3.1 and Algorithm 3.2 is the projection region obtained by different line-search methods in the second projection step. According to our convergence theory and also confirmed by numerical simulations, we can see that our proposed algorithms have better convergence properties than the general CQ algorithm. Open Access This article is licensed under a Creative Commons Attribution 4.0 In- ternational License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the articles Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the articles Creative Commons licence and your intended use is not permitted by statutory reg- ulation or exceeds the permitted use, you will need to obtain permission directly from the copy- right holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. References [1] Q H Ansari, A Rehan. Split feasibility and fixed point problems, Nonlinear Analysis, 2014, 281-322. DANG Ya-zheng, et al. New hybrid inertial CQ projection algorithms with... 157 [2] C Byrne. Iterative oblique projection onto convex sets and the split feasibility problem, Inverse Problems, 2002, 18(2): 441-453. [3] C Byrne. A unified treatment of some iterative algorithms in signal processing and image reconstruction, Inverse Problems, 2004, 20(1): 103-120. [4] Y Censor, T Elfving. A multiprojection algorithm using Bregman projections in a product space, Numerical Algorithms, 1994, 8(2): 221-239. [5] P L Combettes, V R Wajs. Signal recovery by proximal forward-backward splitting, Multi- scale Modeling and Simulation, 2005, 4(4): 1168-1200. [6] A Cegielski, S Reich, R Zalas. Strong and linear convergence of the CQ-method via the regularity of Landweber operators, Optimization, 2020, 69(3): 605-636. [7] Y Z Dang, Y Gao. The strong convergence of a KM-CCQ-like algorithm for a split feasibility problem, Inverse Problems, 2011, 27(1): 015007. [8] Y Z Dang, Y Gao. Bi-extrapolated subgradient projection algorithm for solving multiple-sets split feasibility problem, Applied Mathematics, 2014, 29(3): 283-294. [9] Y Z Dang, Z H Xue, B Wang. Hybrid CQ projection algorithm with line-search process for the split feasibility problem, Journal of Inequalities and Applications, 2016. [10] E C Godwin, C Izuchukwu, O T Mewomo. An inertial extrapolation method for solving gen- eralized split feasibility problems in real hilbert spaces, Bollettino dell’Unione Matematica Italiana, 2021. [11] Y Shehu, F U Ogbuisi. Convergence analysis for proximal split feasibility problems and fixed point problems, J Appl Math Comput, 2015, 48: 221-239. [12] G Lopez, V Martin-Marquez, F H Wang, H K Xu. Solving the split feasibility problem without prior knowledge of matrix norms, Inverse Problems, 2012, 28(8): 374-389. [13] H Y Li, Y L Wu, F H Wang, X L Qin. New Inertial Relaxed Algorithms for Solving Split Feasibility Problems in Hilbert Spaces, Journal of Mathematics, 2021. [14] T V Nguyen, C Prasit, S Suthep. A new CQ algorithm for solving split feasibility problems in Hilbert spaces, Malaysian Mathematical Sciences Society, 2020, 42: 2517-2534. [15] B T Polyak. Some methods of speeding up the convergence of iteration methods, Mathe- matical Physics, 1964, 4(5): 1-17. [16] B Qu, N H Xiu. A note on the CQ algorithm for the split feasibility problem, Inverse Problems, 2005, 21(5): 1655-1665. [17] B Qu, N H Xiu. A new halfspace-relaxation projection method for the split feasibility prob- lem, Linear Algebra and its Applications, 2008, 428: 1218-1229. 158 Appl. Math. J. Chinese Univ. Vol. 38, No. 1 [18] Y Shehu, Q L Dong, L L Liu. Global and linear convergence of alternated inertial methods for split feasibility problems, Revista de la Real Academia de Ciencias Exactas, F´ısicas y Naturales, Serie A-Matem´aticas, 2021, 115(2): 53. [19] A Gibali, Y Shehu. An efficient iterative method for finding common fixed point and vari- ational inequalities in Hilbert spaces, Optimization, 2019, 68(1): 13-32. [20] M Tian, H F Zhang. The regularized CQ algorithm without a priori knowledge of operator norm for solving the split feasibility problem, Journal of Inequalities and Applications, [21] G H Taddele, P Kumam, A G Gebrie. An inertial extrapolation method for multiple-set split feasibility problem, Journal of Inequalities and Applications, 2020. [22] H K Xu. A variable Krasnosel’skii-Mann algorithm and the multiple-set split feasibility problem, Inverse Problems, 2006, 22(6): 2021-2034. [23] A L Yan, G Y Wang, N H Xiu. Robust solutions of split feasibility problem with uncertain linear operator, Journal of Industrial and Management Optimization, 2007, 3(4): 749-761. [24] Y H Yao, J G Wu, Y C Liou. Regularized methods for the split feasibility problem, Abstract and Applied Analysis, 2012. [25] W X Zhang, D Han, Z B Li. A self-adaptive projection method for solving the multiple-sets split feasibility problem, Inverse Problems, 2009, 25(11), DOI: 10.1088/0266- 5611/25/11/115001. [26] J L Zhao, Q Z Yang. Self-adaptive projection methods for the multiple-sets split feasibility problem, Inverse Problems, 2011, 27(3), DOI: 10.1088/0266-5611/27/3/035009. [27] Y Zhou, Z Haiyun, P Wang. Iterative methods for finding the minimum-norm solution of the standard monotone variational inequality problems with applications in Hilbert spaces, Journal of Inequalities and Applications, 2015. School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China. Email: jgdyz@163.com

Journal

Applied Mathematics-A Journal of Chinese Universities – Springer Journals

Published: Mar 1, 2023

Keywords: split feasible problem; inertial; Armijo-type line-search technique; projection algorithm; convergence; 47J05; 47J25

There are no references for this article.