American Institute of Mathematical Sciences

Advanced
October  2019, 15(4): 2023-2034. doi: 10.3934/jimo.2018135

Double projection algorithms for solving the split feasibility problems

Ya-zheng Dang 1, , Jie Sun 2,3,, and  Su Zhang 2,3,

1. 

School of Management, University of Shanghai for Science and Technology, Shanghai PRC 200093
2. 

Faculty of Science, Curtin University, Benteley, West Australia 6102
3. 

Business School, Nankai University, Tianjin PRC 300071

* Corresponding author: Jie Sun

Received  October 2016 Revised  November 2017 Published  September 2018

Fund Project: This work was partially supported by National Science Foundation of China (Grants 71572113 and 11401322) and Australian Research Council (Grant DP160102819).

We propose two new double projection algorithms for solving the split feasibility problem (SFP). Different from the extragradient projection algorithms, the proposed algorithms do not require fixed stepsize and do not employ the same projection region at different projection steps. We adopt flexible rules for selecting the stepsize and the projection region. The proposed algorithms are shown to be convergent under certain assumptions. Numerical experiments show that the proposed methods appear to be more efficient than the relaxed- CQ algorithm.

Keywords: Armijo-type line search, convergence analysis, double projection algorithm, optimization, split feasibility problem.
Mathematics Subject Classification: Primary: 37C25, 47H09; Secondary: 90C25.
Citation: Ya-zheng Dang, Jie Sun, Su Zhang. Double projection algorithms for solving the split feasibility problems. Journal of Industrial & Management Optimization, 2019, 15 (4) : 2023-2034. doi: 10.3934/jimo.2018135
References:
[1]

H. H. Bauschke and J. M. Borwein, On projection algorithms for solving convex feasibility problems, SIAM Review, 38 (1996), 367-426.  doi: 10.1137/S0036144593251710.  Google Scholar

[2]

C. Byrne, An 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

[3]

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

[4]

J. W. Chinneck, The constraint consensus method for finding approximately feasible points in nonlinear programs, INFORMS Journal on Computing, 16 (2004), 255-265.  doi: 10.1287/ijoc.1030.0046.  Google Scholar

[5]

Y. Censor, Parallel application of block iterative methods in medical imaging and radiation therapy, Mathematical Programming, 42 (1998), 307-325.  doi: 10.1007/BF01589408.  Google Scholar

[6]

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

[7]

Y. Censor, T. Elfving, N. Kopf and T. Bortfeld, The multiple-sets split feasibility problem and its applications for inverse problems, Inverse Problems, 21 (2005), 2071-2084.  doi: 10.1088/0266-5611/21/6/017.  Google Scholar

[8]

L. C. Ceng, Q. H. Ansari and J. C. Yao, An extragradient method for solving split feasibility and fixed point problems, Computers and Mathematics with Applications, 64 (2012), 633-642.  doi: 10.1016/j.camwa.2011.12.074.  Google Scholar

[9]

F. Deutsch, The method of alternating orthogonal projections, in Approximation Theory, Spline Functions and Applications, Kluwer Academic Publishers, Dordrecht, 1992,105-121.  Google Scholar

[10]

Y. Dang and Y. Gao, The strong convergence of a KM-CQ-Like algorithm for split feasibility problem, Inverse Problems, 27 (2011), 9pp. doi: 10.1088/0266-5611/27/1/015007.  Google Scholar

[11]

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

[12]

B. He, Inexact implicit methods for monotone general variational inequalities, Mathematical Programming, 35 (1999), 199-217.  doi: 10.1007/s101070050086.  Google Scholar

[13]

G. T. Herman, Image Reconstruction From Projections: The Fundamentals of Computerized Tomography, Academic Press, New York, 1980.  Google Scholar

[14]

D. Kinderlehrer and G. Stampacchia, An Introduction to Variational Inequalities and Their Applications, Academic Press, New York, 1980.  Google Scholar

[15]

N. Nadezhkina and W. Takahashi, Weak convergence theorem by an extragradient method for nonexpansive mappings and monotone mappings, Journal of Optimization Theory and Applications, 128 (2006), 191-201.  doi: 10.1007/s10957-005-7564-z.  Google Scholar

[16]

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

[17]

B. Qu and N. Xiu, A new halfspace-relaxation projection method for the split feasibility problem, Linear Algebra and Its Application, 428 (2008), 1218-1229.  doi: 10.1016/j.laa.2007.03.002.  Google Scholar

[18]

R. T. Rockafellar, Convex Analysis, Princeton University Press, 1971.  Google Scholar

[19]

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

[20]

A. L. Yan, G. Y. Wang and N. Xiu, Robust solutions of split feasibility problem with uncertain linear operator, Journal of Industrial and Management Optimization, 3 (2007), 749-761.  doi: 10.3934/jimo.2007.3.749.  Google Scholar

[21]

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

[22]

Y. N. Yang, Q. Yang and S. Zhang, Modified alternating direction methods for the modified multiple-sets split feasibility problems, Journal of Optimization Theory and Applications, 163 (2014), 130-147.  doi: 10.1007/s10957-013-0502-6.  Google Scholar

[23]

W. X. Zhang, D. Han and Z. B. Li, A self-adaptive projection method for solving the multiple-sets split feasibility problem, Inverse Problem, 25 (2009), 115001, 16pp. doi: 10.1088/0266-5611/25/11/115001.  Google Scholar

[24]

J. L. Zhao and Q. Yang, Self-adaptive projection methods for the multiple-sets split feasibility problem, Inverse Problem, 27 (2011), 035009, 13pp. doi: 10.1088/0266-5611/27/3/035009.  Google Scholar

[25]

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

[26]

E. H. Zarantonello, Projections on convex set in Hilbert space and spectral theory, in Contributions to Nonlinear Functional Analysis (ed. E. H. Zarantonello), Academic, New York, 1971.  Google Scholar

show all references

References:
[1]

H. H. Bauschke and J. M. Borwein, On projection algorithms for solving convex feasibility problems, SIAM Review, 38 (1996), 367-426.  doi: 10.1137/S0036144593251710.  Google Scholar

[2]

C. Byrne, An 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

[3]

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

[4]

J. W. Chinneck, The constraint consensus method for finding approximately feasible points in nonlinear programs, INFORMS Journal on Computing, 16 (2004), 255-265.  doi: 10.1287/ijoc.1030.0046.  Google Scholar

[5]

Y. Censor, Parallel application of block iterative methods in medical imaging and radiation therapy, Mathematical Programming, 42 (1998), 307-325.  doi: 10.1007/BF01589408.  Google Scholar

[6]

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

[7]

Y. Censor, T. Elfving, N. Kopf and T. Bortfeld, The multiple-sets split feasibility problem and its applications for inverse problems, Inverse Problems, 21 (2005), 2071-2084.  doi: 10.1088/0266-5611/21/6/017.  Google Scholar

[8]

L. C. Ceng, Q. H. Ansari and J. C. Yao, An extragradient method for solving split feasibility and fixed point problems, Computers and Mathematics with Applications, 64 (2012), 633-642.  doi: 10.1016/j.camwa.2011.12.074.  Google Scholar

[9]

F. Deutsch, The method of alternating orthogonal projections, in Approximation Theory, Spline Functions and Applications, Kluwer Academic Publishers, Dordrecht, 1992,105-121.  Google Scholar

[10]

Y. Dang and Y. Gao, The strong convergence of a KM-CQ-Like algorithm for split feasibility problem, Inverse Problems, 27 (2011), 9pp. doi: 10.1088/0266-5611/27/1/015007.  Google Scholar

[11]

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

[12]

B. He, Inexact implicit methods for monotone general variational inequalities, Mathematical Programming, 35 (1999), 199-217.  doi: 10.1007/s101070050086.  Google Scholar

[13]

G. T. Herman, Image Reconstruction From Projections: The Fundamentals of Computerized Tomography, Academic Press, New York, 1980.  Google Scholar

[14]

D. Kinderlehrer and G. Stampacchia, An Introduction to Variational Inequalities and Their Applications, Academic Press, New York, 1980.  Google Scholar

[15]

N. Nadezhkina and W. Takahashi, Weak convergence theorem by an extragradient method for nonexpansive mappings and monotone mappings, Journal of Optimization Theory and Applications, 128 (2006), 191-201.  doi: 10.1007/s10957-005-7564-z.  Google Scholar

[16]

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

[17]

B. Qu and N. Xiu, A new halfspace-relaxation projection method for the split feasibility problem, Linear Algebra and Its Application, 428 (2008), 1218-1229.  doi: 10.1016/j.laa.2007.03.002.  Google Scholar

[18]

R. T. Rockafellar, Convex Analysis, Princeton University Press, 1971.  Google Scholar

[19]

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

[20]

A. L. Yan, G. Y. Wang and N. Xiu, Robust solutions of split feasibility problem with uncertain linear operator, Journal of Industrial and Management Optimization, 3 (2007), 749-761.  doi: 10.3934/jimo.2007.3.749.  Google Scholar

[21]

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

[22]

Y. N. Yang, Q. Yang and S. Zhang, Modified alternating direction methods for the modified multiple-sets split feasibility problems, Journal of Optimization Theory and Applications, 163 (2014), 130-147.  doi: 10.1007/s10957-013-0502-6.  Google Scholar

[23]

W. X. Zhang, D. Han and Z. B. Li, A self-adaptive projection method for solving the multiple-sets split feasibility problem, Inverse Problem, 25 (2009), 115001, 16pp. doi: 10.1088/0266-5611/25/11/115001.  Google Scholar

[24]

J. L. Zhao and Q. Yang, Self-adaptive projection methods for the multiple-sets split feasibility problem, Inverse Problem, 27 (2011), 035009, 13pp. doi: 10.1088/0266-5611/27/3/035009.  Google Scholar

[25]

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

[26]

E. H. Zarantonello, Projections on convex set in Hilbert space and spectral theory, in Contributions to Nonlinear Functional Analysis (ed. E. H. Zarantonello), Academic, New York, 1971.  Google Scholar

Table 1.  The numerical results of Example 5.1
Initiative point CQ Algorithm with stepsize $\frac{1}{\rho(A^{T}A})$ Algorithm 3.1 Algorithm 4.1
$ x^{0}=$ $ k=269; s=0.063$ $ k=54; s=0.101$ $ k=28; s=0.077$
$ (-5,-2,-10)^{T}$ $x^{\ast}=(0.5071,-1.8186,01.9072)^{T}$ $x^{\ast}=(0.8718; -1.6577; -1.4080)^{T}$ $x^{\ast}=(1.1595;-1.0082;0-1.0814)^{T}$
$ x^{0}=$ $ k=261; s =0.063$ $ k=16; s=0.061$ $ k=1; s=0.045$
$ (-2,-1,-5)^{T}$ $x^{\ast}=(0.1098;-1.7655; -1.6134)^{T}$ $x^{\ast}=(0.6814;-1.4212; -1.0762)^{T}$ $x^{\ast}=(0.4734;-1.7714 ; -1.3758)^{T}$
$ x^{0}=$ $ k=6450; s =0.525$ $ k=59; s=0.096$ $ k=1; s=0.048$
$(-6,0,-1)^{T}$ $x^{\ast}=(-3.9899;-0.6144; 1.8062)^{T}$ $x^{\ast}=((-3.8898;-0.5850; 1.9604)^{T}$ $x^{\ast}=(-3.9302,-1.0861,1.9786)^{T}$
Table Options

Download as excel

Initiative point CQ Algorithm with stepsize $\frac{1}{\rho(A^{T}A})$ Algorithm 3.1 Algorithm 4.1
$ x^{0}=$ $ k=269; s=0.063$ $ k=54; s=0.101$ $ k=28; s=0.077$
$ (-5,-2,-10)^{T}$ $x^{\ast}=(0.5071,-1.8186,01.9072)^{T}$ $x^{\ast}=(0.8718; -1.6577; -1.4080)^{T}$ $x^{\ast}=(1.1595;-1.0082;0-1.0814)^{T}$
$ x^{0}=$ $ k=261; s =0.063$ $ k=16; s=0.061$ $ k=1; s=0.045$
$ (-2,-1,-5)^{T}$ $x^{\ast}=(0.1098;-1.7655; -1.6134)^{T}$ $x^{\ast}=(0.6814;-1.4212; -1.0762)^{T}$ $x^{\ast}=(0.4734;-1.7714 ; -1.3758)^{T}$
$ x^{0}=$ $ k=6450; s =0.525$ $ k=59; s=0.096$ $ k=1; s=0.048$
$(-6,0,-1)^{T}$ $x^{\ast}=(-3.9899;-0.6144; 1.8062)^{T}$ $x^{\ast}=((-3.8898;-0.5850; 1.9604)^{T}$ $x^{\ast}=(-3.9302,-1.0861,1.9786)^{T}$
Table 2.  The numerical results of Example 5.2
$M, N $ CQ Algorithm with stepsize $\frac{1}{\rho(A^{T}A}$ $t_{k}$ Algorithm3.1 Algorithm 4.1
$ M=20, N=10$ $ k=485, s =1.040$ 0.8 $ k=274, s =0.312$ $ k=210, s =0.270$
1.0 $ k=193, s =0.100$ $ k=108, s =0.070$
1.8 $ k=103, s =0.067$ $ k=64, s =0.021$
$M=100, N=90$ $ k=3987, s =3.100$ 0.4 $ k=1534, s =0.690$ $ k=1244, s =0.530$
1 $ k=1074, s =0.500$ $ k=630, s =0.261$
1.6 $ k=674, s =0.201$ $ k=412, s =0.132$
Table Options

Download as excel

$M, N $ CQ Algorithm with stepsize $\frac{1}{\rho(A^{T}A}$ $t_{k}$ Algorithm3.1 Algorithm 4.1
$ M=20, N=10$ $ k=485, s =1.040$ 0.8 $ k=274, s =0.312$ $ k=210, s =0.270$
1.0 $ k=193, s =0.100$ $ k=108, s =0.070$
1.8 $ k=103, s =0.067$ $ k=64, s =0.021$
$M=100, N=90$ $ k=3987, s =3.100$ 0.4 $ k=1534, s =0.690$ $ k=1244, s =0.530$
1 $ k=1074, s =0.500$ $ k=630, s =0.261$
1.6 $ k=674, s =0.201$ $ k=412, s =0.132$
[1]

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

Martial Agueh, Reinhard Illner, Ashlin Richardson. Analysis and simulations of a refined flocking and swarming model of Cucker-Smale type. Kinetic & Related Models, 2011, 4 (1) : 1-16. doi: 10.3934/krm.2011.4.1
[3]

Haibo Cui, Haiyan Yin. Convergence rate of solutions toward stationary solutions to the isentropic micropolar fluid model in a half line. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020210
[4]

Xue-Ping Luo, Yi-Bin Xiao, Wei Li. Strict feasibility of variational inclusion problems in reflexive Banach spaces. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2495-2502. doi: 10.3934/jimo.2019065
[5]

Mingxin Wang, Qianying Zhang. Dynamics for the diffusive Leslie-Gower model with double free boundaries. Discrete & Continuous Dynamical Systems - A, 2018, 38 (5) : 2591-2607. doi: 10.3934/dcds.2018109
[6]

Jan Prüss, Laurent Pujo-Menjouet, G.F. Webb, Rico Zacher. Analysis of a model for the dynamics of prions. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 225-235. doi: 10.3934/dcdsb.2006.6.225
[7]

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

Andrea Cianchi, Adele Ferone. Improving sharp Sobolev type inequalities by optimal remainder gradient norms. Communications on Pure & Applied Analysis, 2012, 11 (3) : 1363-1386. doi: 10.3934/cpaa.2012.11.1363
[9]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017
[10]

Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018
[11]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[12]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[13]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[14]

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

Fernando P. da Costa, João T. Pinto, Rafael Sasportes. On the convergence to critical scaling profiles in submonolayer deposition models. Kinetic & Related Models, 2018, 11 (6) : 1359-1376. doi: 10.3934/krm.2018053
[16]

Alberto Bressan, Carlotta Donadello. On the convergence of viscous approximations after shock interactions. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 29-48. doi: 10.3934/dcds.2009.23.29
[17]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133
[18]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327
[19]

Ademir Fernando Pazoto, Lionel Rosier. Uniform stabilization in weighted Sobolev spaces for the KdV equation posed on the half-line. Discrete & Continuous Dynamical Systems - B, 2010, 14 (4) : 1511-1535. doi: 10.3934/dcdsb.2010.14.1511
[20]

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

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (212)
  • HTML views (916)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences