- 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] |
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
Other articles
by authors
[Back to Top]