Access the full text.
Sign up today, get DeepDyve free for 14 days.
E. Godwin, C. Izuchukwu, O. Mewomo (2021)
An inertial extrapolation method for solving generalized split feasibility problems in real hilbert spacesBollettino dell'Unione Matematica Italiana, 14
M. Tian, Hui-Fang Zhang (2017)
The regularized CQ algorithm without a priori knowledge of operator norm for solving the split feasibility problemJournal of Inequalities and Applications, 2017
Haiying Li, Yulian Wu, Fenghui Wang (2021)
New Inertial Relaxed CQ Algorithms for Solving Split Feasibility Problems in Hilbert SpacesJournal of Mathematics, 2021
B. Qu, N. Xiu (2008)
A new halfspace-relaxation projection method for the split feasibility problemLinear Algebra and its Applications, 428
Y. Censor, T. Elfving (1994)
A multiprojection algorithm using Bregman projections in a product spaceNumerical Algorithms, 8
Y. Shehu, F. Ogbuisi (2015)
Convergence analysis for proximal split feasibility problems and fixed point problemsJournal of Applied Mathematics and Computing, 48
G. López, Victoria Martín-Márquez, Fenghui Wang, Hong-Kun Xu (2012)
Solving the split feasibility problem without prior knowledge of matrix normsInverse Problems, 28
B T Polyak (1964)
Some methods of speeding up the convergence of iteration methodsMathematical Physics, 4
N. Vinh, P. Cholamjiak, S. Suantai (2019)
A New CQ Algorithm for Solving Split Feasibility Problems in Hilbert SpacesBulletin of the Malaysian Mathematical Sciences Society, 42
A. Cegielski, S. Reich, Rafał Zalas (2018)
Weak, strong and linear convergence of the CQ-method via the regularity of Landweber operatorsOptimization, 69
Yonghong Yao, W. Jigang, Y. Liou (2012)
Regularized Methods for the Split Feasibility ProblemAbstract and Applied Analysis, 2012
Hong-Kun Xu (2006)
A variable Krasnosel'skii–Mann algorithm and the multiple-set split feasibility problemInverse Problems, 22
P. Combettes, Valérie Wajs (2005)
Signal Recovery by Proximal Forward-Backward SplittingMultiscale Model. Simul., 4
Q. Ansari, Aisha Rehan (2014)
Split Feasibility and Fixed Point Problems
A. Yan, Gaoyang Wang, N. Xiu (2007)
Robust solutions of split feasibility problem with uncertain linear operatorJournal of Industrial and Management Optimization, 3
Y. Shehu, Q. Dong, Lulu Liu (2021)
Global and linear convergence of alternated inertial methods for split feasibility problemsRevista de la Real Academia de Ciencias Exactas, Físicas y Naturales. Serie A. Matemáticas, 115
C. Byrne (2004)
A unified treatment of some iterative algorithms in signal processing and image reconstructionInverse Problems, 20
Y. Dang, Yan Gao (2014)
Bi-extrapolated subgradient projection algorithm for solving multiple-sets split feasibility problemApplied Mathematics-A Journal of Chinese Universities, 29
Boris Polyak (1964)
Some methods of speeding up the convergence of iteration methodsUssr Computational Mathematics and Mathematical Physics, 4
G. Taddele, P. Kumam, Anteneh Gebrie (2020)
An inertial extrapolation method for multiple-set split feasibility problemJournal of Inequalities and Applications, 2020
Jinling Zhao, Qingzhi Yang (2011)
Self-adaptive projection methods for the multiple-sets split feasibility problemInverse Problems, 27
C. Byrne (2002)
Iterative oblique projection onto convex sets and the split feasibility problemInverse Problems, 18
Yu Zhou, Haiyun Zhou, Peiyuan Wang (2015)
Iterative methods for finding the minimum-norm solution of the standard monotone variational inequality problems with applications in Hilbert spacesJournal of Inequalities and Applications, 2015
Y. Dang, Zhonghui Xue, Bo Wang (2016)
Hybrid CQ projection algorithm with line-search process for the split feasibility problemJournal of Inequalities and Applications, 2016
A. Gibali, Y. Shehu (2018)
An efficient iterative method for finding common fixed point and variational inequalities in Hilbert spacesOptimization, 68
B. Qu, N. Xiu (2005)
A note on the CQ algorithm for the split feasibility problemInverse Problems, 21
Wenxing Zhang, Deren Han, Zhibao Li (2009)
A self-adaptive projection method for solving the multiple-sets split feasibility problemInverse Problems, 25
Y. Dang, Yan Gao (2010)
The strong convergence of a KM–CQ-like algorithm for a split feasibility problemInverse Problems, 27
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 ﬁrstly introduced by Censor and Elfving [4] in 1994, which is to ﬁnd 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 deﬁned 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 deﬁne 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 modiﬁcations 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 inﬁnite 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 ﬁnding a common solution to a ﬁxed 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 ﬁxed 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 diﬀerent from the general self-adaptive Armijo-type procedure [25,26]. On the other hand, in [15], Polyak ﬁrstly 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 coeﬃcient 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 eﬃciency 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 Diﬀerent 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 deﬁnitions 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 eﬀectiveness 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 ﬁxed 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 iﬀ 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 suﬃcient 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 diﬀerentiable. 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 ﬁrst 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 deﬁnition, we have e(x; 1) = e(x), and x ∈ Γ if and only if e(x; ) = 0. For any x ∈ ℜ and ≥ 0, deﬁne 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 ﬁrst 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 ﬁrst 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 satisﬁed 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 deﬁnition 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 satisﬁed 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 deﬁnition 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 deﬁnition 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 deﬁnition 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 deﬁnition 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 deﬁnition 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 deﬁnition 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 deﬁnition 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 deﬁned 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 deﬁne 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 ﬁnd that the magnitude of inertial term has a certain eﬀect 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 eﬀective, and they still converge faster than the general CQ algorithm. x5 Some concluding remarks This paper presentes two hybrid inertial CQ projection algorithms with diﬀerent rules of stepsize selection for solving SFP. Based on the hybrid CQ projection algorithm, we add the inertial term in the ﬁrst projection step to accelerate the convergence of the algorithm. The main diﬀerence between Algorithm 3.1 and Algorithm 3.2 is the projection region obtained by diﬀerent line-search methods in the second projection step. According to our convergence theory and also conﬁrmed 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 ﬁxed 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 uniﬁed 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 ﬁxed 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 eﬃcient iterative method for ﬁnding common ﬁxed 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 ﬁnding 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
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
You can share this free article with as many people as you like with the url below! We hope you enjoy this feature!
Read and print from thousands of top scholarly journals.
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Copy and paste the desired citation format or use the link below to download a file formatted for EndNote
Access the full text.
Sign up today, get DeepDyve free for 14 days.
All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.