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. CensorT. BortfeldB. 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. HeC. 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. RechtM. 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. CensorT. BortfeldB. 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. HeC. 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. RechtM. 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 2.  Evolutions of objective value with respect to iterations
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).
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 $
(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 $
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

  • PDF downloads (334)
  • HTML views (798)
  • Cited by (0)

Other articles
by authors

[Back to Top]