# 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] 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 [2] J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008 [3] Charles Amorim, Miguel Loayza, Marko A. Rojas-Medar. The nonstationary flows of micropolar fluids with thermal convection: An iterative approach. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2509-2535. doi: 10.3934/dcdsb.2020193 [4] Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781 [5] Lekbir Afraites, Abdelghafour Atlas, Fahd Karami, Driss Meskine. Some class of parabolic systems applied to image processing. Discrete & Continuous Dynamical Systems - B, 2016, 21 (6) : 1671-1687. doi: 10.3934/dcdsb.2016017 [6] Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321 [7] Israa Mohammed Khudher, Yahya Ismail Ibrahim, Suhaib Abduljabbar Altamir. Individual biometrics pattern based artificial image analysis techniques. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2020056 [8] Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022 [9] Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021 [10] 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 [11] Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463 [12] Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020401 [13] Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151 [14] Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261 [15] Hailing Xuan, Xiaoliang Cheng. Numerical analysis and simulation of an adhesive contact problem with damage and long memory. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2781-2804. doi: 10.3934/dcdsb.2020205 [16] Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1757-1778. doi: 10.3934/dcdss.2020453 [17] Hailing Xuan, Xiaoliang Cheng. Numerical analysis of a thermal frictional contact problem with long memory. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021031 [18] Rongchang Liu, Jiangyuan Li, Duokui Yan. New periodic orbits in the planar equal-mass three-body problem. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 2187-2206. doi: 10.3934/dcds.2018090 [19] 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 [20] Namsu Ahn, Soochan Kim. Optimal and heuristic algorithms for the multi-objective vehicle routing problem with drones for military surveillance operations. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021037

2019 Impact Factor: 1.366