American Institute of Mathematical Sciences

Advanced
July  2020, 16(4): 1555-1569. doi: 10.3934/jimo.2019017

Fast self-adaptive regularization iterative algorithm for solving split feasibility problem

Ya-Zheng Dang 1, , Zhong-Hui Xue 2,, , Yan Gao 1, and  Jun-Xiang Li 1,

1. 

School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China
2. 

Shanghai Publication and Printing College, Shanghai 200093, China

* Corresponding author

Received  June 2018 Revised  September 2018 Published  July 2020 Early access  March 2019

Split feasibility problem (SFP) is to find a point which belongs to one convex set in one space, such that its image under a linear transformation belongs to another convex set in the image space. This paper deals with a unified regularized SFP for the convex case. We first construct a self-adaptive regularization iterative algorithm by using Armijo-like search for the SFP and show it converges at a subliner rate of $ O(1/k) $, where $ k $ represents the number of iterations. More interestingly, inspired by the acceleration technique introduced by Nesterov[12], we present a fast Armijo-like regularization iterative algorithm and show it converges at rate of $ O(1/k^{2}) $. The efficiency of the algorithms is demonstrated by some random data and image debluring problems.

Keywords: Split feasible problem, accelerated iterative algorithm, Armijo-like search, regularization, iteration complexity, image deblurring.
Mathematics Subject Classification: 90C25, 47J25.
Citation: Ya-Zheng Dang, Zhong-Hui Xue, Yan Gao, Jun-Xiang Li. Fast self-adaptive regularization iterative algorithm for solving split feasibility problem. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1555-1569. doi: 10.3934/jimo.2019017
References:
[1]

C. Byrne, A 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.

[2]

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.

[3]

Y. Censor, T. Bortfeld, B. Mortin and A. Trofimov, A unified approach for inversion problems in intensity-modulated radiation, Physics in Medicine and Biology, 51 (2006), 2353-2365.  doi: 10.1088/0031-9155/51/10/001.

[4]

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.

[5]

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.

[6]

H. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems, Spring Netherlands, 2000.

[7] Y. Gao, Nonsmooth Optimization (in Chinese), Science Press, Beijing, 2008. 
[8]

P.C. Hansen, J. G. Nagy and D. P. Oleary, Deblurring Images: Matices, Spectra and Giltering, SIAM, 2006. doi: 10.1137/1.9780898718874.

[9]

H. J. He, C. Ling and H. Xu, An implementable splitting algorithm for the $ l_{1} $ norm regularized split feasibility problem, Journal of Scientific Computing, 67 (2016), 281-298.  doi: 10.1007/s10915-015-0078-4.

[10]

S. N. He and W. L. Zhu, A note on approximating curve with 1-norm regularization method for the split feasibility problem, Journal of Applied Mathematics, 2012 (2012), Article ID 683890, 10 pages. doi: 10.1155/2012/683890.

[11]

M. Li, Improved relaxed CQ methods for solving the split feasibility problem, Advanced Modeling and Optimization, 13 (2011), 305-317. 

[12]

Y. Nesterov, A method for solving a convex programming problems with convergence rate $ O(1/k^{2}) $., Soviet Math. Dokl, 269 (1983), 543-547. 

[13]

J. M. Ortega and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Classics in Applied Mathematics, 30, SIAM, Philadelphia, 2000. doi: 10.1137/1.9780898719468.

[14]

B. Qu and N. Xiu, A note on the CQ algorithm for the split feasibility problem, Inverse Problem, 21 (2005), 1655-1665.  doi: 10.1088/0266-5611/21/5/009.

[15]

B. Recht, M. Fazel and P. Parrilo, Guaranteed minimum rank solutions of matrix equations via neclear norm minimization, SIAM Rev, 52 (2010), 471-501.  doi: 10.1137/070697835.

[16]

A. Sabharwal and L. Potter, Convexly constrained linear inverse problemsares and regularization, IEEE Trans. Signal Process, 46 (1998), 2345-2352.  doi: 10.1109/78.709518.

[17]

H. Xu, A variate Krasnosel$'$ ski-Mann algorithm and the multiple-set split feasibility problem, Inverse Problems, 22 (2006), 2021-2034.  doi: 10.1088/0266-5611/22/6/007.

[18]

H. Xu and F. Wang, Approximating curve and strong convergence of the CQ algorithm for the split feasibility problem, Journal of Inequalities and Applicatio, 2010 (2010), Article ID102085, 13 pages. doi: 10.1155/2010/102085.

[19]

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.

[20]

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.

show all references

References:
[1]

C. Byrne, A 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.

[2]

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.

[3]

Y. Censor, T. Bortfeld, B. Mortin and A. Trofimov, A unified approach for inversion problems in intensity-modulated radiation, Physics in Medicine and Biology, 51 (2006), 2353-2365.  doi: 10.1088/0031-9155/51/10/001.

[4]

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.

[5]

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.

[6]

H. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems, Spring Netherlands, 2000.

[7] Y. Gao, Nonsmooth Optimization (in Chinese), Science Press, Beijing, 2008. 
[8]

P.C. Hansen, J. G. Nagy and D. P. Oleary, Deblurring Images: Matices, Spectra and Giltering, SIAM, 2006. doi: 10.1137/1.9780898718874.

[9]

H. J. He, C. Ling and H. Xu, An implementable splitting algorithm for the $ l_{1} $ norm regularized split feasibility problem, Journal of Scientific Computing, 67 (2016), 281-298.  doi: 10.1007/s10915-015-0078-4.

[10]

S. N. He and W. L. Zhu, A note on approximating curve with 1-norm regularization method for the split feasibility problem, Journal of Applied Mathematics, 2012 (2012), Article ID 683890, 10 pages. doi: 10.1155/2012/683890.

[11]

M. Li, Improved relaxed CQ methods for solving the split feasibility problem, Advanced Modeling and Optimization, 13 (2011), 305-317. 

[12]

Y. Nesterov, A method for solving a convex programming problems with convergence rate $ O(1/k^{2}) $., Soviet Math. Dokl, 269 (1983), 543-547. 

[13]

J. M. Ortega and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Classics in Applied Mathematics, 30, SIAM, Philadelphia, 2000. doi: 10.1137/1.9780898719468.

[14]

B. Qu and N. Xiu, A note on the CQ algorithm for the split feasibility problem, Inverse Problem, 21 (2005), 1655-1665.  doi: 10.1088/0266-5611/21/5/009.

[15]

B. Recht, M. Fazel and P. Parrilo, Guaranteed minimum rank solutions of matrix equations via neclear norm minimization, SIAM Rev, 52 (2010), 471-501.  doi: 10.1137/070697835.

[16]

A. Sabharwal and L. Potter, Convexly constrained linear inverse problemsares and regularization, IEEE Trans. Signal Process, 46 (1998), 2345-2352.  doi: 10.1109/78.709518.

[17]

H. Xu, A variate Krasnosel$'$ ski-Mann algorithm and the multiple-set split feasibility problem, Inverse Problems, 22 (2006), 2021-2034.  doi: 10.1088/0266-5611/22/6/007.

[18]

H. Xu and F. Wang, Approximating curve and strong convergence of the CQ algorithm for the split feasibility problem, Journal of Inequalities and Applicatio, 2010 (2010), Article ID102085, 13 pages. doi: 10.1155/2010/102085.

[19]

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.

[20]

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.

Figure 1.  Evolutions of SNR with respect to iterations
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Evolutions of objective value with respect to iterations
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  In each subgraph (a or b or c) top(from left to right): clean images and corrupted images, respectively; bottom(from left to right): Recovered images by Algorithm 3.1 and Algorithm 4.1, respectively. house.png (256 × 256); boat.png (256 × 256); pepper.png (256 × 256).
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Numerical comparison for synthetic date
(N, M) CQ algorithm Algorithm 3.1 Algorithm 4.1
$ (10, 20) $ $ Iter.=13673; s =0.6915 $ $ Iter.=5019; s=0.5747 $ $ Iter.=565; s=0.0553 $
$ (20, 40) $ $ Iter.=23694; s =0.9182 $ $ Iter.=2752; s =0.3956 $ $ Iter.=1553; s=0.3027 $
$ (50, 50) $ $ Iter.=49389; s =1.9104 $ $ Iter.=16794, s =1.1770 $ $ Iter.=1407; s=0.4170 $
Table Options

Download as excel

(N, M) CQ algorithm Algorithm 3.1 Algorithm 4.1
$ (10, 20) $ $ Iter.=13673; s =0.6915 $ $ Iter.=5019; s=0.5747 $ $ Iter.=565; s=0.0553 $
$ (20, 40) $ $ Iter.=23694; s =0.9182 $ $ Iter.=2752; s =0.3956 $ $ Iter.=1553; s=0.3027 $
$ (50, 50) $ $ Iter.=49389; s =1.9104 $ $ Iter.=16794, s =1.1770 $ $ Iter.=1407; s=0.4170 $
Table 2.  The numerical results for image deblurring
image Algorithm 3.1 Algorithm 4.1
house $ Iter.=645, s =35.6395 $ $ SNR=24.0820 $ $ Iter.=357, s =13.8825 $ $ SNR=24.2712 $
boat $ Iter.=800, s =133.7814 $ $ SNR=21.2978 $ $ Iter.=530, s =42.8210 $$ SNR= 21.4350 $
pepper $ Iter.=1026, s =57.6502 $ $ SNR=20.1239 $ $ Iter.=588, s =30.8807 $ $ SNR= 20.2807 $
Table Options

Download as excel

image Algorithm 3.1 Algorithm 4.1
house $ Iter.=645, s =35.6395 $ $ SNR=24.0820 $ $ Iter.=357, s =13.8825 $ $ SNR=24.2712 $
boat $ Iter.=800, s =133.7814 $ $ SNR=21.2978 $ $ Iter.=530, s =42.8210 $$ SNR= 21.4350 $
pepper $ Iter.=1026, s =57.6502 $ $ SNR=20.1239 $ $ Iter.=588, s =30.8807 $ $ SNR= 20.2807 $
[1]

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

Xiangtuan Xiong, Jinmei Li, Jin Wen. Some novel linear regularization methods for a deblurring problem. Inverse Problems and Imaging, 2017, 11 (2) : 403-426. doi: 10.3934/ipi.2017019
[3]

Dang Van Hieu, Le Dung Muu, Pham Kim Quy. New iterative regularization methods for solving split variational inclusion problems. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021185
[4]

Yan Tang. Convergence analysis of a new iterative algorithm for solving split variational inclusion problems. Journal of Industrial and Management Optimization, 2020, 16 (2) : 945-964. doi: 10.3934/jimo.2018187
[5]

Alina Toma, Bruno Sixou, Françoise Peyrin. Iterative choice of the optimal regularization parameter in TV image restoration. Inverse Problems and Imaging, 2015, 9 (4) : 1171-1191. doi: 10.3934/ipi.2015.9.1171
[6]

Jamilu Abubakar, Poom Kumam, Abor Isa Garba, Muhammad Sirajo Abdullahi, Abdulkarim Hassan Ibrahim, Wachirapong Jirakitpuwapat. An efficient iterative method for solving split variational inclusion problem with applications. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021160
[7]

Xin Li, Ziguan Cui, Linhui Sun, Guanming Lu, Debnath Narayan. Research on iterative repair algorithm of Hyperchaotic image based on support vector machine. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1199-1218. doi: 10.3934/dcdss.2019083
[8]

Yazheng Dang, Marcus Ang, Jie Sun. An inertial triple-projection algorithm for solving the split feasibility problem. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022019
[9]

Kien Ming Ng, Trung Hieu Tran. A parallel water flow algorithm with local search for solving the quadratic assignment problem. Journal of Industrial and Management Optimization, 2019, 15 (1) : 235-259. doi: 10.3934/jimo.2018041
[10]

Jie Huang, Marco Donatelli, Raymond H. Chan. Nonstationary iterated thresholding algorithms for image deblurring. Inverse Problems and Imaging, 2013, 7 (3) : 717-736. doi: 10.3934/ipi.2013.7.717
[11]

Emeka Chigaemezu Godwin, Adeolu Taiwo, Oluwatosin Temitope Mewomo. Iterative method for solving split common fixed point problem of asymptotically demicontractive mappings in Hilbert spaces. Numerical Algebra, Control and Optimization, 2022  doi: 10.3934/naco.2022005
[12]

Jacob Ashiwere Abuchu, Godwin Chidi Ugwunnadi, Ojen Kumar Narain. Inertial Mann-Type iterative method for solving split monotone variational inclusion problem with applications. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022075
[13]

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

Xueling Zhou, Meixia Li, Haitao Che. Relaxed successive projection algorithm with strong convergence for the multiple-sets split equality problem. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2557-2572. doi: 10.3934/jimo.2020082
[15]

Grace Nnennaya Ogwo, Chinedu Izuchukwu, Oluwatosin Temitope Mewomo. A modified extragradient algorithm for a certain class of split pseudo-monotone variational inequality problem. Numerical Algebra, Control and Optimization, 2022, 12 (2) : 373-393. doi: 10.3934/naco.2021011
[16]

Nam-Yong Lee, Bradley J. Lucier. Preconditioned conjugate gradient method for boundary artifact-free image deblurring. Inverse Problems and Imaging, 2016, 10 (1) : 195-225. doi: 10.3934/ipi.2016.10.195
[17]

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

Yishui Wang, Dongmei Zhang, Peng Zhang, Yong Zhang. Local search algorithm for the squared metric $ k $-facility location problem with linear penalties. Journal of Industrial and Management Optimization, 2021, 17 (4) : 2013-2030. doi: 10.3934/jimo.2020056
[19]

Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial and Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703
[20]

Behrad Erfani, Sadoullah Ebrahimnejad, Amirhossein Moosavi. An integrated dynamic facility layout and job shop scheduling problem: A hybrid NSGA-II and local search algorithm. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1801-1834. doi: 10.3934/jimo.2019030

2021 Impact Factor: 1.411

Tools

Metrics

  • PDF downloads (543)
  • HTML views (1025)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy