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]

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

Li Cai, Fubao Zhang. The Brezis-Nirenberg type double critical problem for a class of Schrödinger-Poisson equations. Electronic Research Archive, , () : -. doi: 10.3934/era.2020125
[3]

Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122
[4]

George W. Patrick. The geometry of convergence in numerical analysis. Journal of Computational Dynamics, 2021, 8 (1) : 33-58. doi: 10.3934/jcd.2021003
[5]

Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005
[6]

Hassan Mohammad. A diagonal PRP-type projection method for convex constrained nonlinear monotone equations. Journal of Industrial & Management Optimization, 2021, 17 (1) : 101-116. doi: 10.3934/jimo.2019101
[7]

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

Matúš Tibenský, Angela Handlovičová. Convergence analysis of the discrete duality finite volume scheme for the regularised Heston model. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1181-1195. doi: 10.3934/dcdss.2020226
[9]

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

Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007
[11]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031
[12]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[13]

Claudia Lederman, Noemi Wolanski. An optimization problem with volume constraint for an inhomogeneous operator with nonstandard growth. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020391
[14]

Hui Gao, Jian Lv, Xiaoliang Wang, Liping Pang. An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information. Journal of Industrial & Management Optimization, 2021, 17 (2) : 805-825. doi: 10.3934/jimo.2019135
[15]

Lekbir Afraites, Chorouk Masnaoui, Mourad Nachaoui. Shape optimization method for an inverse geometric source problem and stability at critical shape. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021006
[16]

Wei Ouyang, Li Li. Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods. Journal of Industrial & Management Optimization, 2021, 17 (1) : 169-184. doi: 10.3934/jimo.2019105
[17]

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

Nguyen Huy Tuan. On an initial and final value problem for fractional nonclassical diffusion equations of Kirchhoff type. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020354
[19]

Lan Luo, Zhe Zhang, Yong Yin. Simulated annealing and genetic algorithm based method for a bi-level seru loading problem with worker assignment in seru production systems. Journal of Industrial & Management Optimization, 2021, 17 (2) : 779-803. doi: 10.3934/jimo.2019134
[20]

Yunfeng Jia, Yi Li, Jianhua Wu, Hong-Kun Xu. Cauchy problem of semilinear inhomogeneous elliptic equations of Matukuma-type with multiple growth terms. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3485-3507. doi: 10.3934/dcds.2019227

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (208)
  • HTML views (915)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences