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]

Lan Luo, Zhe Zhang, Yong Yin. Simulated annealing and genetic algorithm based method for a bi-level seru loading problem with worker assignment in seru production systems. Journal of Industrial & Management Optimization, 2021, 17 (2) : 779-803. doi: 10.3934/jimo.2019134

[3]

Ying Liu, Yanping Chen, Yunqing Huang, Yang Wang. Two-grid method for semiconductor device problem by mixed finite element method and characteristics finite element method. Electronic Research Archive, 2021, 29 (1) : 1859-1880. doi: 10.3934/era.2020095

[4]

Abdollah Borhanifar, Maria Alessandra Ragusa, Sohrab Valizadeh. High-order numerical method for two-dimensional Riesz space fractional advection-dispersion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020355

[5]

Petr Čoupek, María J. Garrido-Atienza. Bilinear equations in Hilbert space driven by paths of low regularity. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 121-154. doi: 10.3934/dcdsb.2020230

[6]

Liam Burrows, Weihong Guo, Ke Chen, Francesco Torella. Reproducible kernel Hilbert space based global and local image segmentation. Inverse Problems & Imaging, 2021, 15 (1) : 1-25. doi: 10.3934/ipi.2020048

[7]

Hui Gao, Jian Lv, Xiaoliang Wang, Liping Pang. An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information. Journal of Industrial & Management Optimization, 2021, 17 (2) : 805-825. doi: 10.3934/jimo.2019135

[8]

Lekbir Afraites, Chorouk Masnaoui, Mourad Nachaoui. Shape optimization method for an inverse geometric source problem and stability at critical shape. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021006

[9]

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

[10]

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, 2021, 26 (1) : 61-79. doi: 10.3934/dcdsb.2020351

[11]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013

[12]

Xiaoxiao Li, Yingjing Shi, Rui Li, Shida Cao. Energy management method for an unpowered landing. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020180

[13]

Amru Hussein, Martin Saal, Marc Wrona. Primitive equations with horizontal viscosity: The initial value and The time-periodic problem for physical boundary conditions. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020398

[14]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019

[15]

Qing-Hu Hou, Yarong Wei. Telescoping method, summation formulas, and inversion pairs. Electronic Research Archive, , () : -. doi: 10.3934/era.2021007

[16]

Yanmei Sun, Yakui Huang. An alternate gradient method for optimization problems with orthogonality constraints. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021003

[17]

Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007

[18]

Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122

[19]

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

[20]

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

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (444)
  • HTML views (1746)
  • Cited by (8)

[Back to Top]