# American Institute of Mathematical Sciences

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, 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] 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] Yan Tang. Convergence analysis of a new iterative algorithm for solving split variational inclusion problems. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-20. doi: 10.3934/jimo.2018187 [4] 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 [5] 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 [6] 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 [7] 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 [8] 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 [9] 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, 2017, 13 (5) : 1-34. doi: 10.3934/jimo.2019030 [10] 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 [11] Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018142 [12] Yigui Ou, Haichan Lin. A class of accelerated conjugate-gradient-like methods based on a modified secant equation. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-16. doi: 10.3934/jimo.2019013 [13] Guodong Ma, Jinbao Jian. A QP-free algorithm of quasi-strongly sub-feasible directions for inequality constrained optimization. Journal of Industrial & Management Optimization, 2015, 11 (1) : 307-328. doi: 10.3934/jimo.2015.11.307 [14] Xueyong Wang, Yiju Wang, Gang Wang. An accelerated augmented Lagrangian method for multi-criteria optimization problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-9. doi: 10.3934/jimo.2018136 [15] Simai He, Min Li, Shuzhong Zhang, Zhi-Quan Luo. A nonconvergent example for the iterative water-filling algorithm. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 147-150. doi: 10.3934/naco.2011.1.147 [16] Lingling Lv, Zhe Zhang, Lei Zhang, Weishu Wang. An iterative algorithm for periodic sylvester matrix equations. Journal of Industrial & Management Optimization, 2018, 14 (1) : 413-425. doi: 10.3934/jimo.2017053 [17] Fabián Crocce, Ernesto Mordecki. A non-iterative algorithm for generalized pig games. Journal of Dynamics & Games, 2018, 5 (4) : 331-341. doi: 10.3934/jdg.2018020 [18] Suthep Suantai, Nattawut Pholasa, Prasit Cholamjiak. The modified inertial relaxed CQ algorithm for solving the split feasibility problems. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1595-1615. doi: 10.3934/jimo.2018023 [19] Rich Stankewitz, Hiroki Sumi. Random backward iteration algorithm for Julia sets of rational semigroups. Discrete & Continuous Dynamical Systems - A, 2015, 35 (5) : 2165-2175. doi: 10.3934/dcds.2015.35.2165 [20] Scott Crass. New light on solving the sextic by iteration: An algorithm using reliable dynamics. Journal of Modern Dynamics, 2011, 5 (2) : 397-408. doi: 10.3934/jmd.2011.5.397

2018 Impact Factor: 1.025