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]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271

[2]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

[3]

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

[4]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327

[5]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006

[6]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017

[7]

Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018

[8]

Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002

[9]

Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263

[10]

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149

[11]

Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83

[12]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008

[13]

Xue-Ping Luo, Yi-Bin Xiao, Wei Li. Strict feasibility of variational inclusion problems in reflexive Banach spaces. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2495-2502. doi: 10.3934/jimo.2019065

[14]

Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321

[15]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[16]

Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781

[17]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021

[18]

Valery Y. Glizer. Novel Conditions of Euclidean space controllability for singularly perturbed systems with input delay. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020027

[19]

Alina Chertock, Alexander Kurganov, Mária Lukáčová-Medvi${\rm{\check{d}}}$ová, Șeyma Nur Özcan. An asymptotic preserving scheme for kinetic chemotaxis models in two space dimensions. Kinetic & Related Models, 2019, 12 (1) : 195-216. doi: 10.3934/krm.2019009

[20]

Wei Liu, Pavel Krejčí, Guoju Ye. Continuity properties of Prandtl-Ishlinskii operators in the space of regulated functions. Discrete & Continuous Dynamical Systems - B, 2017, 22 (10) : 3783-3795. doi: 10.3934/dcdsb.2017190

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (458)
  • HTML views (1747)
  • Cited by (8)

[Back to Top]