October  2018, 14(4): 1595-1615. doi: 10.3934/jimo.2018023

The modified inertial relaxed CQ algorithm for solving the split feasibility problems

1. 

Department of Mathematics, Faculty of Science, Chiang Mai University, Chiang Mai 50200, Thailand

2. 

School of Science, University of Phayao, Phayao 56000, Thailand

∗ Corresponding author: prasitch2008@yahoo.com (P. Cholamjiak)

Received  April 2017 Revised  August 2017 Published  January 2018

In this work, we propose a new version of inertial relaxed CQ algorithms for solving the split feasibility problems in the frameworks of Hilbert spaces. We then prove its strong convergence by using a viscosity approximation method under some weakened assumptions. To be more precisely, the computation on the norm of operators and the metric projections is relaxed. Finally, we provide numerical experiments to illustrate the convergence behavior and to show the effectiveness of the sequences constructed by the inertial technique.

Citation: Suthep Suantai, Nattawut Pholasa, Prasit Cholamjiak. The modified inertial relaxed CQ algorithm for solving the split feasibility problems. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1595-1615. doi: 10.3934/jimo.2018023
References:
[1]

F. Alvarez and H. Attouch, An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping, Set-Valued Anal., 9 (2001), 3-11.  doi: 10.1023/A:1011253113155.  Google Scholar

[2]

J. P. Aubin, Optima and Equilibria: An Introduction to Nonlinear Analysis, Springer, Berlin, 1993.  Google Scholar

[3]

H. H. Bauschke and J. M. Borwein, On projection algorithms for solving convex feasibility problem, SIAM Rev., 38 (1996), 367-426.  doi: 10.1137/S0036144593251710.  Google Scholar

[4]

C. Byrne, Iterative oblique projection onto convex sets and the split feasibility problem, Inverse Probl., 18 (2002), 441-453.  doi: 10.1088/0266-5611/18/2/310.  Google Scholar

[5]

C. Byrne, A unified treatment of some iterative algorithms in signal processing and image reconstruction, Inverse Probl., 20 (2004), 103-120.  doi: 10.1088/0266-5611/20/1/006.  Google Scholar

[6]

A. Cegielski, General method for solving the split common fixed point problems, J. Optim. Theory Appl., 165 (2015), 385-404.  doi: 10.1007/s10957-014-0662-z.  Google Scholar

[7]

Y. Censor and T. Elfving, A multiprojection algorithm using Bregman projection in product space, Numer. Algor., 8 (1994), 221-239.  doi: 10.1007/BF02142692.  Google Scholar

[8]

Y. Dang and Y. Gao, The strong convergence of a KM-CQ-like algorithm for a split feasibility problem, Inverse Probl. 27 (2011), 015007, 9pp. doi: 10.1088/0266-5611/27/1/015007.  Google Scholar

[9]

Y. DangJ. Sun and H. Xu, Inertial accelerated algorithms for solving a split feasibility problem, J. Ind. Manag. Optim., 13 (2017), 1383-1394.  doi: 10.3934/jimo.2016078.  Google Scholar

[10]

Q. L. DongH. B. YuanY. J. Cho and Th. M. Rassias, Modified inertial Mann algorithm and inertial CQ-algorithm for nonexpansive mappings, Optim. Lett., (2016), 1-16.  doi: 10.1007/s11590-016-1102-9.  Google Scholar

[11]

M. Fukushima, A relaxed projection method for variational inequalities, Math. Program., 35 (1986), 58-70.  doi: 10.1007/BF01589441.  Google Scholar

[12]

S. He and Z. Zhao, Strong convergence of a relaxed CQ algorithm for the split feasibility problem, J. Inqe. Appl. 2013 (2013), p197.  Google Scholar

[13]

G. López, V. Martin-Marquez, F. H. Wang and H. K. Xu, Solving the split feasibility problem without prior knowledge of matrix norms, Inverse Probl. 28 (2012), 085004, 18pp. doi: 10.1088/0266-5611/28/8/085004.  Google Scholar

[14]

D. A. Lorenz and T. Pock, An inertial forward-backward algorithm for monotone inclusions, J. Math. Imaging Vis., 51 (2015), 311-325.  doi: 10.1007/s10851-014-0523-2.  Google Scholar

[15]

P. E. Maingé, Convergence theorems for inertial KM-type algorithms, J. Comput. Appl. Math., 219 (2008), 223-236.  doi: 10.1016/j.cam.2007.07.021.  Google Scholar

[16]

P. E. Maingé, Inertial iterative process for fixed points of certain quasi-nonexpansive mappings, Set Valued Anal., 15 (2007), 67-79.  doi: 10.1007/s11228-006-0027-3.  Google Scholar

[17]

P. E. Maingé, Approximation methods for common fixed points of nonexpansive mappings in Hilbert spaces, J. Math. Anal. Appl., 325 (2007), 469-479.  doi: 10.1016/j.jmaa.2005.12.066.  Google Scholar

[18]

P. E. Maingé, Strong convergence of projected subgradient methods for nonsmooth and nonstrictly convex minimization, Set-Valued Anal., 16 (2008), 899-912.  doi: 10.1007/s11228-008-0102-z.  Google Scholar

[19]

A. Moudafi, Viscosity approximation methods for fixed-points problems, J. Math. Anal. Appl., 241 (2000), 46-55.  doi: 10.1006/jmaa.1999.6615.  Google Scholar

[20]

A. Moudafi and M. Oliny, Convergence of a splitting inertial proximal method for monotone operators, J. Comput. Appl. Math., 155 (2003), 447-454.  doi: 10.1016/S0377-0427(02)00906-8.  Google Scholar

[21]

Y. Nesterov, A method for solving the convex programming problem with convergence rate (1/k2), Dokl. Akad. Nauk SSSR, 269 (1983), 543-547.   Google Scholar

[22]

B. T. Polyak, Some methods of speeding up the convergence of iteration methods, U. S. S. R. Comput. Math. Math. Phys., 4 (1964), 1-17.   Google Scholar

[23]

R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14 (1976), 877-898.  doi: 10.1137/0314056.  Google Scholar

[24]

F. Wang, On the convergence of CQ algorithm with variable steps for the split equality problem, Numer. Algor., 74 (2017), 927-935.  doi: 10.1007/s11075-016-0177-9.  Google Scholar

[25]

H. K. Xu, A variable Krasonosel'skii-Mann algorithm and the multiple-set split feasibility problem, Inverse Probl., 22 (2006), 2021-2034.  doi: 10.1088/0266-5611/22/6/007.  Google Scholar

[26]

H. K. Xu, Iterative methods for the split feasibility problem in infinite-dimensional Hilbert spaces, Inverse Probl. 26 (2010), 105018, 17pp.  Google Scholar

[27]

H. K. Xu, Iterative algorithms for nonlinear operators, J. Lond. Math. Soc., 66 (2002), 240-256.  doi: 10.1112/S0024610702003332.  Google Scholar

[28]

Q. Yang, The relaxed CQ algorithm for solving the split feasibility problem, Inverse Probl., 20 (2004), 1261-1266.  doi: 10.1088/0266-5611/20/4/014.  Google Scholar

[29]

Q. Yang, On variable-set relaxed projection algorithm for variational inequalities, J. Math. Anal. Appl., 302 (2005), 166-179.  doi: 10.1016/j.jmaa.2004.07.048.  Google Scholar

show all references

References:
[1]

F. Alvarez and H. Attouch, An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping, Set-Valued Anal., 9 (2001), 3-11.  doi: 10.1023/A:1011253113155.  Google Scholar

[2]

J. P. Aubin, Optima and Equilibria: An Introduction to Nonlinear Analysis, Springer, Berlin, 1993.  Google Scholar

[3]

H. H. Bauschke and J. M. Borwein, On projection algorithms for solving convex feasibility problem, SIAM Rev., 38 (1996), 367-426.  doi: 10.1137/S0036144593251710.  Google Scholar

[4]

C. Byrne, Iterative oblique projection onto convex sets and the split feasibility problem, Inverse Probl., 18 (2002), 441-453.  doi: 10.1088/0266-5611/18/2/310.  Google Scholar

[5]

C. Byrne, A unified treatment of some iterative algorithms in signal processing and image reconstruction, Inverse Probl., 20 (2004), 103-120.  doi: 10.1088/0266-5611/20/1/006.  Google Scholar

[6]

A. Cegielski, General method for solving the split common fixed point problems, J. Optim. Theory Appl., 165 (2015), 385-404.  doi: 10.1007/s10957-014-0662-z.  Google Scholar

[7]

Y. Censor and T. Elfving, A multiprojection algorithm using Bregman projection in product space, Numer. Algor., 8 (1994), 221-239.  doi: 10.1007/BF02142692.  Google Scholar

[8]

Y. Dang and Y. Gao, The strong convergence of a KM-CQ-like algorithm for a split feasibility problem, Inverse Probl. 27 (2011), 015007, 9pp. doi: 10.1088/0266-5611/27/1/015007.  Google Scholar

[9]

Y. DangJ. Sun and H. Xu, Inertial accelerated algorithms for solving a split feasibility problem, J. Ind. Manag. Optim., 13 (2017), 1383-1394.  doi: 10.3934/jimo.2016078.  Google Scholar

[10]

Q. L. DongH. B. YuanY. J. Cho and Th. M. Rassias, Modified inertial Mann algorithm and inertial CQ-algorithm for nonexpansive mappings, Optim. Lett., (2016), 1-16.  doi: 10.1007/s11590-016-1102-9.  Google Scholar

[11]

M. Fukushima, A relaxed projection method for variational inequalities, Math. Program., 35 (1986), 58-70.  doi: 10.1007/BF01589441.  Google Scholar

[12]

S. He and Z. Zhao, Strong convergence of a relaxed CQ algorithm for the split feasibility problem, J. Inqe. Appl. 2013 (2013), p197.  Google Scholar

[13]

G. López, V. Martin-Marquez, F. H. Wang and H. K. Xu, Solving the split feasibility problem without prior knowledge of matrix norms, Inverse Probl. 28 (2012), 085004, 18pp. doi: 10.1088/0266-5611/28/8/085004.  Google Scholar

[14]

D. A. Lorenz and T. Pock, An inertial forward-backward algorithm for monotone inclusions, J. Math. Imaging Vis., 51 (2015), 311-325.  doi: 10.1007/s10851-014-0523-2.  Google Scholar

[15]

P. E. Maingé, Convergence theorems for inertial KM-type algorithms, J. Comput. Appl. Math., 219 (2008), 223-236.  doi: 10.1016/j.cam.2007.07.021.  Google Scholar

[16]

P. E. Maingé, Inertial iterative process for fixed points of certain quasi-nonexpansive mappings, Set Valued Anal., 15 (2007), 67-79.  doi: 10.1007/s11228-006-0027-3.  Google Scholar

[17]

P. E. Maingé, Approximation methods for common fixed points of nonexpansive mappings in Hilbert spaces, J. Math. Anal. Appl., 325 (2007), 469-479.  doi: 10.1016/j.jmaa.2005.12.066.  Google Scholar

[18]

P. E. Maingé, Strong convergence of projected subgradient methods for nonsmooth and nonstrictly convex minimization, Set-Valued Anal., 16 (2008), 899-912.  doi: 10.1007/s11228-008-0102-z.  Google Scholar

[19]

A. Moudafi, Viscosity approximation methods for fixed-points problems, J. Math. Anal. Appl., 241 (2000), 46-55.  doi: 10.1006/jmaa.1999.6615.  Google Scholar

[20]

A. Moudafi and M. Oliny, Convergence of a splitting inertial proximal method for monotone operators, J. Comput. Appl. Math., 155 (2003), 447-454.  doi: 10.1016/S0377-0427(02)00906-8.  Google Scholar

[21]

Y. Nesterov, A method for solving the convex programming problem with convergence rate (1/k2), Dokl. Akad. Nauk SSSR, 269 (1983), 543-547.   Google Scholar

[22]

B. T. Polyak, Some methods of speeding up the convergence of iteration methods, U. S. S. R. Comput. Math. Math. Phys., 4 (1964), 1-17.   Google Scholar

[23]

R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14 (1976), 877-898.  doi: 10.1137/0314056.  Google Scholar

[24]

F. Wang, On the convergence of CQ algorithm with variable steps for the split equality problem, Numer. Algor., 74 (2017), 927-935.  doi: 10.1007/s11075-016-0177-9.  Google Scholar

[25]

H. K. Xu, A variable Krasonosel'skii-Mann algorithm and the multiple-set split feasibility problem, Inverse Probl., 22 (2006), 2021-2034.  doi: 10.1088/0266-5611/22/6/007.  Google Scholar

[26]

H. K. Xu, Iterative methods for the split feasibility problem in infinite-dimensional Hilbert spaces, Inverse Probl. 26 (2010), 105018, 17pp.  Google Scholar

[27]

H. K. Xu, Iterative algorithms for nonlinear operators, J. Lond. Math. Soc., 66 (2002), 240-256.  doi: 10.1112/S0024610702003332.  Google Scholar

[28]

Q. Yang, The relaxed CQ algorithm for solving the split feasibility problem, Inverse Probl., 20 (2004), 1261-1266.  doi: 10.1088/0266-5611/20/4/014.  Google Scholar

[29]

Q. Yang, On variable-set relaxed projection algorithm for variational inequalities, J. Math. Anal. Appl., 302 (2005), 166-179.  doi: 10.1016/j.jmaa.2004.07.048.  Google Scholar

Figure 1.  Comparison of the iterations of Choice 1 in Example 1
Figure 2.  Comparison of the iterations of Choice 2 in Example 1
Figure 3.  Comparison of the iterations of Choice 3 in Example 1
Figure 4.  Comparison of the iterations of Choice 4 in Example 1
Figure 5.  Comparison of the iterations of Choice 1 in Example 2
Figure 6.  Comparison of the iterations of Choice 2 in Example 2
Figure 7.  Comparison of the iterations of Choice 3 in Example 2
Figure 8.  Comparison of the iterations of Choice 4 in Example 2
Figure 9.  Error ploting of Choice 1 in Example 1
Figure 10.  Error ploting of Choice 2 in Example 1
Figure 11.  Error ploting of Choice 3 in Example 1
Figure 12.  Error ploting of Choice 4 in Example 1
Table 1.  Algorithm 3.1 with different cases of $\rho_n$ and different choices of $x_0$ and $x_1$
Case 1Case 2Case 3Case 4
Choice 1No. of Iter.11854
cpu (Time) $0.003553$ $0.002377$ $0.002195$ $0.002075$
Choice 2No. of Iter.7644
cpu (Time) $0.002799$ $0.002769$ $0.002357$ $0.002184$
Choice 3No. of Iter.12964
cpu (Time) $0.003828$ $0.002602$ $0.002401$ $0.002142$
Choice 4No. of Iter.2717119
cpu (Time) $0.007181$ $0.00343$ $0.002612$ $0.002431$
The numerical experiments for each case of $\rho_{n}$ are shown in Figure 1-4, respectively.
Case 1Case 2Case 3Case 4
Choice 1No. of Iter.11854
cpu (Time) $0.003553$ $0.002377$ $0.002195$ $0.002075$
Choice 2No. of Iter.7644
cpu (Time) $0.002799$ $0.002769$ $0.002357$ $0.002184$
Choice 3No. of Iter.12964
cpu (Time) $0.003828$ $0.002602$ $0.002401$ $0.002142$
Choice 4No. of Iter.2717119
cpu (Time) $0.007181$ $0.00343$ $0.002612$ $0.002431$
The numerical experiments for each case of $\rho_{n}$ are shown in Figure 1-4, respectively.
Table 2.  Algorithm 3.1 with different cases of $\rho_n$ and different choices of $x_0$ and $x_1$
Case 1Case 2Case 3Case 4
Choice 1No. of Iter.191055
cpu (Time) $0.005632$ $0.003408$ $0.003223$ $0.002791$
Choice 2No. of Iter.181066
cpu (Time) $0.00391$ $0.002683$ $0.002447$ $0.002381$
Choice 3No. of Iter.191066
cpu (Time) $0.004233$ $0.003016$ $0.002601$ $0.002575$
Choice 4No. of Iter.13766
cpu (Time) $0.004812$ $0.003559$ $0.002922$ $0.002412$
The numerical experiments are shown in Figure 5-8, respectively.
Case 1Case 2Case 3Case 4
Choice 1No. of Iter.191055
cpu (Time) $0.005632$ $0.003408$ $0.003223$ $0.002791$
Choice 2No. of Iter.181066
cpu (Time) $0.00391$ $0.002683$ $0.002447$ $0.002381$
Choice 3No. of Iter.191066
cpu (Time) $0.004233$ $0.003016$ $0.002601$ $0.002575$
Choice 4No. of Iter.13766
cpu (Time) $0.004812$ $0.003559$ $0.002922$ $0.002412$
The numerical experiments are shown in Figure 5-8, respectively.
Table 3.  Comparison of MIner-R-Iter, Iner-R-Iter and H-R-Iter in Example 1
MIner-R-IterIner-R-IterH-R-Iter
Choice 1 $u=(0, -1, -5)^T$No. of Iter.633223
$x_{0}=(2, 6, -3)^T$cpu (Time)0.0007370.0076770.064889
$x_{1}=(-2, -1, 8)^T$
Choice 2$u=(2, 1, 0)^T$No. of Iter.426378
$x_{0}=(3, 4, -1)^T$cpu (Time)0.0005220.0048610.137471
$x_{1}=(-5, -2, 1)^T$
Choice 3$u=(5, -3, -1)^T$No. of Iter.929140
$x_{0}=(2, 1, -1)^T$cpu (Time)0.0014580.0051750.026824
$x_{1}=(-5, 3, 5)^T$
Choice 4$u=(-2, -1, 4)^T$No. of Iter.934763
$x_{0}=(7.35, 1.75, -3.24)^T$cpu (Time)0.0014810.0080580.687214
$x_{1}=(-6.34, 0.42, 7.36)^T$
The error plotting of $E_n$ of MIner-R-Iter, Iner-R-Iter and H-R-Iter for each choice in Table 3 is shown in the following figures, respectively.
MIner-R-IterIner-R-IterH-R-Iter
Choice 1 $u=(0, -1, -5)^T$No. of Iter.633223
$x_{0}=(2, 6, -3)^T$cpu (Time)0.0007370.0076770.064889
$x_{1}=(-2, -1, 8)^T$
Choice 2$u=(2, 1, 0)^T$No. of Iter.426378
$x_{0}=(3, 4, -1)^T$cpu (Time)0.0005220.0048610.137471
$x_{1}=(-5, -2, 1)^T$
Choice 3$u=(5, -3, -1)^T$No. of Iter.929140
$x_{0}=(2, 1, -1)^T$cpu (Time)0.0014580.0051750.026824
$x_{1}=(-5, 3, 5)^T$
Choice 4$u=(-2, -1, 4)^T$No. of Iter.934763
$x_{0}=(7.35, 1.75, -3.24)^T$cpu (Time)0.0014810.0080580.687214
$x_{1}=(-6.34, 0.42, 7.36)^T$
The error plotting of $E_n$ of MIner-R-Iter, Iner-R-Iter and H-R-Iter for each choice in Table 3 is shown in the following figures, respectively.
[1]

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463

[2]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[3]

Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020351

[4]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076

[5]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078

[6]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462

[7]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250

[8]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319

[9]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

[10]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296

[11]

Hirokazu Ninomiya. Entire solutions of the Allen–Cahn–Nagumo equation in a multi-dimensional space. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 395-412. doi: 10.3934/dcds.2020364

[12]

Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251

[13]

Qingfang Wang, Hua Yang. Solutions of nonlocal problem with critical exponent. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5591-5608. doi: 10.3934/cpaa.2020253

[14]

Stefano Bianchini, Paolo Bonicatto. Forward untangling and applications to the uniqueness problem for the continuity equation. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020384

[15]

Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020453

[16]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[17]

Fioralba Cakoni, Pu-Zhao Kow, Jenn-Nan Wang. The interior transmission eigenvalue problem for elastic waves in media with obstacles. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020075

[18]

Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340

[19]

Zhilei Liang, Jiangyu Shuai. Existence of strong solution for the Cauchy problem of fully compressible Navier-Stokes equations in two dimensions. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020348

[20]

Mehdi Badsi. Collisional sheath solutions of a bi-species Vlasov-Poisson-Boltzmann boundary value problem. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020052

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (420)
  • HTML views (1745)
  • Cited by (8)

[Back to Top]