Article Contents
Article Contents

Inertial accelerated algorithms for solving a split feasibility problem

• * Corresponding author:Yazheng Dang. The reviewing process of the paper was handled by Changzhi Wu as a Guest Editor
• Inspired by the inertial proximal algorithms for finding a zero of a maximal monotone operator, in this paper, we propose two inertial accelerated algorithms to solve the split feasibility problem. One is an inertial relaxed-CQ algorithm constructed by applying inertial technique to a relaxed-CQ algorithm, the other is a modified inertial relaxed-CQ algorithm which combines the KM method with the inertial relaxed-CQ algorithm. We prove their asymptotical convergence under some suitable conditions. Numerical results are reported to show the effectiveness of the proposed algorithms.

Mathematics Subject Classification: Primary: 65K05, 65K10; Secondary: 49J52.

 Citation:

• Table 1.  The numerical results of example 5.1

 Initiative point R-Iter Iner-R-Iter $x^{0}=(3.2, 4.2, 5.2)$ $k=74; s =0.068$ $k=5; s=0.016$ $x^{1}=(-0.5843,$ $x^{\ast}=(-0.6200, 1.6180, 1.6216)$ $x^{\ast}=(-1.1281, 1.0720, 1.9694)$ $2.3078, 3.3435)$ $x^{0}=(10, 0, 10)$ $k=93; s =0.090$ $k=84; s=0.085$ $x^{1}=(2.0825,$ $x^{\ast}=(0.9000, -1.7152, 1.7074)$ $x^{\ast}=(-0.1061, -1.4514, 2.1596)$ $-2.5275, 6.4589)$ $x^{0}=(2, -5, 2)$ $k=73; s =0.075$ $k=35; s =0.035$ $x^{1}=(1.3327,$ $x^{\ast}=(1.1512, -2.7679;1.8616)$ $x^{\ast}=(0.9010, -2.1029, 1.8169)$ $-3.2657, 1.9328)$

Table 2.  The numerical results of example 5.1

 Initiative point $\alpha_{k}$ Iner-KM-R-Iter $x^{0}=(3.2, 4.2, 5.2)$ 0.4 $k=3; s=0.016$ $x^{1}=(-0.5843, 2.3078, 3.3435)$ $x^{\ast}=(-2.6931, 1.2534, 2.2937)$ 0.8 $k=3; s= 0.013$ $x^{\ast}=(-2.6828, 1.2585, 2.2835)$ $x^{0}=(10, 0, 10)$ 0.4 $k=76; s =0.086$ $x^{1}=(2.0825, -2.5275, 6.4589)$ $x^{\ast}=(-0.1346, -2.6392, 2.3046)$ 0.8 $k= 74; s=0.085$ $x^{\ast}=(-0.0799, -2.6190, 2.3611)$ $x^{0}=(2, -5, 2)$ 0.6 $k=62; s =0.056$ $x^{1}=(1.3327, -3.2657, 1.9328)$ $x^{\ast}=(0.9006, -2.1031, 1.8171)$ 0.8 $k=45; s= 0.046$ $x^{\ast}=(0.9008, -2.1030, 1.8170)$

Table 3.  The numerical results of example 5.2

 Initiative point R-Iter Iner-R-Iter $x^{0}=(0, 0, 0, 0, 0)$ $k=15$; s $=0.675$ $k=5$; s $=0.018$ $x^{1}=(-0.0092, 0,$ $x^{\ast}=(-0.0208, 0,$ $x^{\ast}=(0.0015, 0,$ $-0.0132, -0.0026, -0.0092)$ $-0.0297, -0.0059, -0.0208)$ $-0.0412, -0.0082, -0.0288)$ $x^{0}=(1, 1, 1, 1, 1)$ $k=20$; s $=0.083$ $k=3$; s $=0.0272$ $x^{1}=(0.3237, 0.5471,$ $x^{\ast}=(0.0171, 0.3822,$ $x^{\ast}=(-0.0784, 0.2935,$ $0.2280, 0.4833, 0.3237)$ $-0.1394, 0.2779, 0.0171)$ $-0.2378, 0.1873, -0.0784)$ $x^{0}=(20, 10, 20, 10, 20)$ $k=22$; s $=0.090$ $k=6$; s $=0.067$ $x^{1}=(6.1605, 5.0023,$ $x^{\ast}=(0.0837, 0.3910,$ $x^{\ast}=(-0.2490, -0.2117,$ $4.5130, 3.9040, 6.1605)$ $-0.2155, 0.1915, 0.0837)$ $-0.1742, -0.1619, -0.2490)$

Table 4.  The numerical results of example 5.2

 Initiative point $\alpha_{k}$ Iner-KM-R-Iter $x^{0}=(0, 0, 0, 0, 0)$ 0.6 $k=6$; s $=0.020$ $x^{1}=(-0.0092, 0, -0.0132,$ $x^{\ast}=(-0.0209, 0, -0.0299, -0.0059, -0.0209)$ $-0.0026, -0.0092)$ 0.8 k=5; s=0.018 $x^{\ast}=(-0.0212, 0, -0.0304, -0.0060, -0.0212)$ $x^{0}=(1, 1, 1, 1, 1)$ 0.4 $k=3$; s $=0.034$ $x^{1}=(0.3237, 0.5471,$ $x^{\ast}=(-0.0644, 0.2935, -0.2177, 0.1913, -0.0644)$ $0.2280, 0.4833, 0.3237)$ 0.6 k=3; s=0.034 $x^{\ast}=(-0.0691, 0.2935, -0.2244, 0.1899, -0.0691)$ $x^{0}=(20, 10, 20, 10, 20)$ 0.6 $k=9$; s $=0.072$ $x^{1}=(6.1605, 5.0023,$ $x^{\ast}=(-0.2263, -0.1045, -0.2337, -0.1094, -0.2263)$ $4.5130, 3.9040, 6.1605)$ 0.8 k= 7; s=0.071 $x^{\ast}=(-0.2283, -0.1610, -0.1881, -0.1342, -0.2283)$

Table 5.  The numerical results of example 5.3

 $M, N$ R-Iter Iner-R-Iter Iner-KM-R-Iter $M=20, N=10$ $k=436, s =0.970$ $k=174, s =0.500$ $k=210, s =0.270$ $M=100, N=90$ $k=3788, s =0.130$ $k=602, s =0.680$ $k=534, s =0.690$
•  [1] F. Alvarez, On the minimizing property of a second order dissipative dynamical system in Hilbert spaces, SIAM Journal on Control and Optimization, 39 (2000), 1102-1119.  doi: 10.1137/S0363012998335802. [2] F. Alvarez and H. Attouch, An inertial proximal method for maximal monotone operators via Discretization of a nonlinear oscillator with damping, Set-Valued Analysis, 9 (2001), 3-11.  doi: 10.1023/A:1011253113155. [3] F. Alvarez, Weak convergence of a relaxed and inertial hybrid projection-proximal point algorithm for maximal monotone operators in Hilbert space, SIAM Journal on Optimization, 14 (2003), 773-782.  doi: 10.1137/S1052623403427859. [4] H. H. Bauschke and J. M. Borwein, On projection algorithms for solving convex feasibility problems, SIAM Review, 38 (1996), 367-426.  doi: 10.1137/S0036144593251710. [5] C. Byrne, Iterative oblique projection onto convex sets and the split feasibility problem, Inverse Problems, 18 (2002), 441-453.  doi: 10.1088/0266-5611/18/2/310. [6] C. Byrne, An unified treatment of some iterative algorithm algorithms in signal processing and image reconstruction, Inverse Problems, 20 (2004), 103-120.  doi: 10.1088/0266-5611/20/1/006. [7] J. W. Chinneck, The constraint consensus method for finding approximately feasible points in nonlinear programs, INFORMS Journal on Computing, 16 (2004), 255-265.  doi: 10.1287/ijoc.1030.0046. [8] Y. Censor, Parallel application of block iterative methods in medical imaging and radiation therapy, Mathematical Programming, 42 (1998), 307-325.  doi: 10.1007/BF01589408. [9] Y. Censor and T. Elfving, A multiprojection algorithm using Bregman projections in a product space, Numerical Algorithms, 8 (1994), 221-239.  doi: 10.1007/BF02142692. [10] Y. Censor, T. Elfving, N. Kopf and T. Bortfeld, The multiple-sets solit feasibility problem and its applications for inverse problems, Inverse Problems, 21 (2005), 2071-2084.  doi: 10.1088/0266-5611/21/6/017. [11] G. Crombez, A geometrical look at iterative methods for operators with fixed points, Numerical Functional Analysis and Optimization, 26 (2005), 137-175.  doi: 10.1081/NFA-200063882. [12] F. H. Clarke, Optimization and Nonsmooth Analysis, John Wiley and Sons, New York, 1983. [13] F. Deutsch, The method of alternating orthogonal projections, Approximation Theory, Spline Functions and Applications, 105-121, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci. , 356, Kluwer Acad. Publ. , Dordrecht, 1992 [14] Y. Dang and Y. Gao, The strong convergence of a KM-CQ-Like algorithm for split feasibility problem, Inverse Problems 27 (2011), 015007, 9 pp. doi: 10.1088/0266-5611/27/1/015007. [15] M. Fukushima, On the convergence of a class of outer approximation algorithms for convex programs, Journal of Computational and Applied Mathematics, 10 (1984), 147-156.  doi: 10.1016/0377-0427(84)90051-7. [16] M. Fukushima, A relaxed projection method for variational inequalities, Mathematics Programming, 35 (1986), 58-70.  doi: 10.1007/BF01589441. [17] Y. Gao, Piecewise smooth Lyapunov function for a nonlinear dynamical system, Journal of Convex Analysis, 19 (2012), 1009-1015. [18] G. T. Herman, Image Reconstruction From Projections: The Fundamentals of Computerized Tomography, Academic Press, New York, 1980. [19] P. E. Mainge, Inertial iterative process for fixed points of certain quasi-nonexpansive mappings, Set-valued Analysis, 15 (2007), 67-79.  doi: 10.1007/s11228-006-0027-3. [20] P. E. Mainge, Convergence theorem for inertial KM-type algorithms, Journal of Computational and Applied Mathematics, 219 (2008), 223-236.  doi: 10.1016/j.cam.2007.07.021. [21] Z. Opial, Weak convergence of the sequence of successive approximations for non-expansive mappings, Bull. American Mathematical Society, 73 (1967), 591-597.  doi: 10.1090/S0002-9904-1967-11761-0. [22] B. Qu and N. Xiu, A new halfspace-relaxation projection method for the split feasibility problem, Linear Algebra and Its Application, 428 (2008), 1218-1229.  doi: 10.1016/j.laa.2007.03.002. [23] H. Xu, A variabe Krasnoselski-Mann algorithm and the multiple-set split feasibility problem, Inverse Problems, 22 (2006), 2021-2034.  doi: 10.1088/0266-5611/22/6/007. [24] Q. Yang, The relaxed CQ algorithm solving the split feasibility problem, Inverse Problems, 20 (2004), 1261-1266.  doi: 10.1088/0266-5611/20/4/014. [25] A. L. Yan, G. Y. Wang and N. H. Xiu, Robust solutions of split feasibility problem with uncertain linear operator, Journal of Industrial and Management Optimization, 3 (2007), 749-761.  doi: 10.3934/jimo.2007.3.749. [26] J. Zhao and Q. Yang, Several solution methods for the split feasibility problem, Inverse Problems, 21 (2005), 1791-1799.  doi: 10.1088/0266-5611/21/5/017.

Tables(5)