• Previous Article
    Three concepts of robust efficiency for uncertain multiobjective optimization problems via set order relations
  • JIMO Home
  • This Issue
  • Next Article
    The inexact log-exponential regularization method for mathematical programs with vertical complementarity constraints
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, 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.

[2]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[11]

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

[12]

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

[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.

[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.

[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.

[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.

[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.

[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.

[19]

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

[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.

[21]

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

[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.

[23]

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

[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.

[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.

[26]

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

[27]

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

[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.

[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.

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.

[2]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[11]

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

[12]

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

[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.

[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.

[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.

[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.

[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.

[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.

[19]

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

[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.

[21]

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

[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.

[23]

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

[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.

[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.

[26]

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

[27]

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

[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.

[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.

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]

Aviv Gibali, Dang Thi Mai, Nguyen The Vinh. A new relaxed CQ algorithm for solving split feasibility problems in Hilbert spaces and its applications. Journal of Industrial & Management Optimization, 2018, 13 (5) : 1-22. doi: 10.3934/jimo.2018080

[2]

Yazheng Dang, Jie Sun, Honglei Xu. Inertial accelerated algorithms for solving a split feasibility problem. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1383-1394. doi: 10.3934/jimo.2016078

[3]

Biao Qu, Naihua Xiu. A relaxed extragradient-like method for a class of constrained optimization problem. Journal of Industrial & Management Optimization, 2007, 3 (4) : 645-654. doi: 10.3934/jimo.2007.3.645

[4]

Ai-Ling Yan, Gao-Yang Wang, Naihua Xiu. Robust solutions of split feasibility problem with uncertain linear operator. Journal of Industrial & Management Optimization, 2007, 3 (4) : 749-761. doi: 10.3934/jimo.2007.3.749

[5]

Libin Mou, Jiongmin Yong. Two-person zero-sum linear quadratic stochastic differential games by a Hilbert space method. Journal of Industrial & Management Optimization, 2006, 2 (1) : 95-117. doi: 10.3934/jimo.2006.2.95

[6]

Jing Zhou, Dejun Chen, Zhenbo Wang, Wenxun Xing. A conic approximation method for the 0-1 quadratic knapsack problem. Journal of Industrial & Management Optimization, 2013, 9 (3) : 531-547. doi: 10.3934/jimo.2013.9.531

[7]

Chaoxu Pei, Mark Sussman, M. Yousuff Hussaini. A space-time discontinuous Galerkin spectral element method for the Stefan problem. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 1-28. doi: 10.3934/dcdsb.2017216

[8]

Bernd Hofmann, Barbara Kaltenbacher, Elena Resmerita. Lavrentiev's regularization method in Hilbert spaces revisited. Inverse Problems & Imaging, 2016, 10 (3) : 741-764. doi: 10.3934/ipi.2016019

[9]

Andrew E.B. Lim, John B. Moore. A path following algorithm for infinite quadratic programming on a Hilbert space. Discrete & Continuous Dynamical Systems - A, 1998, 4 (4) : 653-670. doi: 10.3934/dcds.1998.4.653

[10]

Yulan Lu, Minghui Song, Mingzhu Liu. Convergence rate and stability of the split-step theta method for stochastic differential equations with piecewise continuous arguments. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 1-23. doi: 10.3934/dcdsb.2018203

[11]

Zhiming Chen, Shaofeng Fang, Guanghui Huang. A direct imaging method for the half-space inverse scattering problem with phaseless data. Inverse Problems & Imaging, 2017, 11 (5) : 901-916. doi: 10.3934/ipi.2017042

[12]

Christopher Bose, Rua Murray. The exact rate of approximation in Ulam's method. Discrete & Continuous Dynamical Systems - A, 2001, 7 (1) : 219-235. doi: 10.3934/dcds.2001.7.219

[13]

Francisco Guillén-González, Mamadou Sy. Iterative method for mass diffusion model with density dependent viscosity. Discrete & Continuous Dynamical Systems - B, 2008, 10 (4) : 823-841. doi: 10.3934/dcdsb.2008.10.823

[14]

Frederic Rousset. The residual boundary conditions coming from the real vanishing viscosity method. Discrete & Continuous Dynamical Systems - A, 2002, 8 (3) : 605-625. doi: 10.3934/dcds.2002.8.606

[15]

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

[16]

Xin-Guo Liu, Kun Wang. A multigrid method for the maximal correlation problem. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 785-796. doi: 10.3934/naco.2012.2.785

[17]

Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial & Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521

[18]

Baolan Yuan, Wanjun Zhang, Yubo Yuan. A Max-Min clustering method for $k$-means algorithm of data clustering. Journal of Industrial & Management Optimization, 2012, 8 (3) : 565-575. doi: 10.3934/jimo.2012.8.565

[19]

Xiaojun Chen, Guihua Lin. CVaR-based formulation and approximation method for stochastic variational inequalities. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 35-48. doi: 10.3934/naco.2011.1.35

[20]

Piotr Gwiazda, Piotr Orlinski, Agnieszka Ulikowska. Finite range method of approximation for balance laws in measure spaces. Kinetic & Related Models, 2017, 10 (3) : 669-688. doi: 10.3934/krm.2017027

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (113)
  • HTML views (469)
  • Cited by (0)

[Back to Top]