- Previous Article
- JIMO Home
- This Issue
-
Next Article
An efficient algorithm for non-convex sparse optimization
Double projection algorithms for solving the split feasibility problems
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 |
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.
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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[9] |
F. Deutsch, The method of alternating orthogonal projections, in Approximation Theory, Spline Functions and Applications, Kluwer Academic Publishers, Dordrecht, 1992,105-121. |
[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. |
[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. |
[13] |
G. T. Herman, Image Reconstruction From Projections: The Fundamentals of Computerized Tomography, Academic Press, New York, 1980. |
[14] |
D. Kinderlehrer and G. Stampacchia, An Introduction to Variational Inequalities and Their Applications, Academic Press, New York, 1980. |
[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. |
[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. |
[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. |
[18] |
R. T. Rockafellar, Convex Analysis, Princeton University Press, 1971. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[9] |
F. Deutsch, The method of alternating orthogonal projections, in Approximation Theory, Spline Functions and Applications, Kluwer Academic Publishers, Dordrecht, 1992,105-121. |
[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. |
[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. |
[13] |
G. T. Herman, Image Reconstruction From Projections: The Fundamentals of Computerized Tomography, Academic Press, New York, 1980. |
[14] |
D. Kinderlehrer and G. Stampacchia, An Introduction to Variational Inequalities and Their Applications, Academic Press, New York, 1980. |
[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. |
[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. |
[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. |
[18] |
R. T. Rockafellar, Convex Analysis, Princeton University Press, 1971. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
Initiative point | CQ Algorithm with stepsize |
Algorithm 3.1 | Algorithm 4.1 |
|
|||
|
| ||
|
Initiative point | CQ Algorithm with stepsize |
Algorithm 3.1 | Algorithm 4.1 |
|
|||
|
| ||
|
CQ Algorithm with stepsize |
Algorithm3.1 | Algorithm 4.1 | ||
0.8 | | |||
1.0 | | |||
1.8 | | |||
0.4 | ||||
1 | | |||
1.6 | |
CQ Algorithm with stepsize |
Algorithm3.1 | Algorithm 4.1 | ||
0.8 | | |||
1.0 | | |||
1.8 | | |||
0.4 | ||||
1 | | |||
1.6 | |
[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
Other articles
by authors
[Back to Top]