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 & 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.  Google Scholar

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

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

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

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

[6]

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

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

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

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

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

[11]

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

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

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

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

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

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

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

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

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

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

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.  Google Scholar

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

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

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

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

[6]

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

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

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

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

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

[11]

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

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

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

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

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

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

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

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

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

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

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 & 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 & 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 & 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 & 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 & 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 & 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 & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1199-1218. doi: 10.3934/dcdss.2019083
[8]

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

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

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
[11]

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 & Optimization, 2021  doi: 10.3934/naco.2021011
[12]

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

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 & Management Optimization, 2021, 17 (4) : 2013-2030. doi: 10.3934/jimo.2020056
[14]

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

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 & Management Optimization, 2020, 16 (4) : 1801-1834. doi: 10.3934/jimo.2019030
[16]

Bin Feng, Lixin Wei, Ziyu Hu. An adaptive large neighborhood search algorithm for Vehicle Routing Problem with Multiple Time Windows constraints. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021197
[17]

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

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
[19]

Chengjin Li. Parameter-related projection-based iterative algorithm for a kind of generalized positive semidefinite least squares problem. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 511-520. doi: 10.3934/naco.2020048
[20]

Tianyu Yang, Yang Yang. A stable non-iterative reconstruction algorithm for the acoustic inverse boundary value problem. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021038

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (482)
  • HTML views (927)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy