# American Institute of Mathematical Sciences

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

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

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

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
Evolutions of SNR with respect to iterations
Evolutions of objective value with respect to iterations
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).
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$
 (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$
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  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] 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 [2] Jia Cai, Guanglong Xu, Zhensheng Hu. Sketch-based image retrieval via CAT loss with elastic net regularization. Mathematical Foundations of Computing, 2020, 3 (4) : 219-227. doi: 10.3934/mfc.2020013 [3] Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167 [4] Shipra Singh, Aviv Gibali, Xiaolong Qin. Cooperation in traffic network problems via evolutionary split variational inequalities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020170 [5] Kha Van Huynh, Barbara Kaltenbacher. Some application examples of minimization based formulations of inverse problems and their regularization. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020074 [6] Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018 [7] M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014 [8] Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017 [9] Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321 [10] Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251 [11] Qingfang Wang, Hua Yang. Solutions of nonlocal problem with critical exponent. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5591-5608. doi: 10.3934/cpaa.2020253 [12] Stefano Bianchini, Paolo Bonicatto. Forward untangling and applications to the uniqueness problem for the continuity equation. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020384 [13] Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020453 [14] Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031 [15] Fioralba Cakoni, Pu-Zhao Kow, Jenn-Nan Wang. The interior transmission eigenvalue problem for elastic waves in media with obstacles. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020075 [16] Shun Zhang, Jianlin Jiang, Su Zhang, Yibing Lv, Yuzhen Guo. ADMM-type methods for generalized multi-facility Weber problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020171 [17] 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 [18] Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340 [19] 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, 2020  doi: 10.3934/dcdsb.2020351 [20] Zhilei Liang, Jiangyu Shuai. Existence of strong solution for the Cauchy problem of fully compressible Navier-Stokes equations in two dimensions. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020348

2019 Impact Factor: 1.366

## Metrics

• HTML views (798)
• Cited by (0)

• on AIMS