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]

Yazheng Dang, Fanwen Meng, Jie Sun. Convergence analysis of a parallel projection algorithm for solving convex feasibility problems. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 505-519. doi: 10.3934/naco.2016023
[2]

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

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, 2017, 13 (5) : 1-15. doi: 10.3934/jimo.2019017
[4]

Leong-Kwan Li, Sally Shao. Convergence analysis of the weighted state space search algorithm for recurrent neural networks. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 193-207. doi: 10.3934/naco.2014.4.193
[5]

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

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

Zhong Wan, Chaoming Hu, Zhanlu Yang. A spectral PRP conjugate gradient methods for nonconvex optimization problem based on modified line search. Discrete & Continuous Dynamical Systems - B, 2011, 16 (4) : 1157-1169. doi: 10.3934/dcdsb.2011.16.1157
[8]

Ai-Ling Yan, Gao-Yang Wang, Naihua Xiu. Robust solutions of split feasibility problem with uncertain linear operator. Journal of Industrial & Management Optimization, 2007, 3 (4) : 749-761. doi: 10.3934/jimo.2007.3.749
[9]

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

Aviv Gibali, Dang Thi Mai, Nguyen The Vinh. A new relaxed CQ algorithm for solving split feasibility problems in Hilbert spaces and its applications. Journal of Industrial & Management Optimization, 2019, 15 (2) : 963-984. doi: 10.3934/jimo.2018080
[11]

Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015
[12]

Mohamed A. Tawhid, Ahmed F. Ali. An effective hybrid firefly algorithm with the cuckoo search for engineering optimization problems. Mathematical Foundations of Computing, 2018, 1 (4) : 349-368. doi: 10.3934/mfc.2018017
[13]

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

Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. On a refinement of the convergence analysis for the new exact penalty function method for continuous inequality constrained optimization problem. Journal of Industrial & Management Optimization, 2012, 8 (2) : 485-491. doi: 10.3934/jimo.2012.8.485
[15]

Dang Van Hieu. Projection methods for solving split equilibrium problems. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-19. doi: 10.3934/jimo.2019056
[16]

Ming-Jong Yao, Yu-Chun Wang. Theoretical analysis and a search procedure for the joint replenishment problem with deteriorating products. Journal of Industrial & Management Optimization, 2005, 1 (3) : 359-375. doi: 10.3934/jimo.2005.1.359
[17]

Chunlin Hao, Xinwei Liu. Global convergence of an SQP algorithm for nonlinear optimization with overdetermined constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 19-29. doi: 10.3934/naco.2012.2.19
[18]

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

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

Mingyong Lai, Xiaojiao Tong. A metaheuristic method for vehicle routing problem based on improved ant colony optimization and Tabu search. Journal of Industrial & Management Optimization, 2012, 8 (2) : 469-484. doi: 10.3934/jimo.2012.8.469

2018 Impact Factor: 1.025

Tools

Metrics

  • PDF downloads (95)
  • HTML views (717)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences