    2016, 6(4): 505-519. doi: 10.3934/naco.2016023

## Convergence analysis of a parallel projection algorithm for solving convex feasibility problems

 1 Business School, University of Shanghai for Science and Technology, Shanghai, China 2 Department of Health Services and Outcomes Research, National Healthcare Group, 138543 3 Department of Mathematics and Statistics, Curtin University, Perth,WA 6845

Received  January 2016 Revised  November 2016 Published  December 2016

The convex feasibility problem (CFP) is a classical problem in nonlinear analysis. In this paper, we propose an inertial parallel projection algorithm for solving CFP. Different from the previous algorithms, the proposed method introduces a sequence of parameters and uses the information of last two iterations at each step. To prove its convergence in a simple way, we transform the parallel algorithm to a sequential one in a constructed product space. Preliminary experiments are conducted to demonstrate that the proposed approach converges faster than the general extrapolated algorithms.
Citation: 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
##### References:
  H. H. Bauschke and J. M. Borwein, On projection algorithms for solving convex feasibility problems,, \emph{SIAM Rev.}, 38 (1996), 367.  doi: 10.1137/S0036144593251710.  Google Scholar  H. H. Bauschke, J. M.Borwein, and A. S. Lewis, The method of cyclic projections for closed convex sets in Hilbert space,, in \emph{Proceedings of the Special Session on Optimization and Nonlinear Analysis}, (1995).   Google Scholar  S. Boyd, L. EI Ghaoui, E. Feron and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory,, Society for Industrial and Applied Mathematics, (1994).  doi: 10.1137/1.9781611970777.  Google Scholar  Y. Censor and A. Lent, Cyclic subgradient projections,, \emph{Math. Program.}, 24 (1982), 233.  doi: 10.1007/BF01585107.  Google Scholar  Y. Censor, Parallel application of block iterative methods in medical imaging and radiation therapy,, \emph{Math. Program.}, 42 (1998), 307.  doi: 10.1007/BF01589408.  Google Scholar  J. W. Chinneck, The constraint consensus method for finding approximately feasible points in nonlinear programs,, \emph{INFORMS J. Comput.}, 16 (2004), 255.  doi: 10.1287/ijoc.1030.0046.  Google Scholar  P. L. Combeties and S. G. Kruk, Extroplation algorithm for affine-convex feasibility problems,, \emph{Numer. Algorithms}, 41 (2006), 239.  doi: 10.1007/s11075-005-9010-6.  Google Scholar  Y. Dang and Y. Gao, Non-monotonous accelerated parallel subgradient projection algorithm for convex feasibility problem,, \emph{Optimization}, 63 (2014), 571.  doi: 10.1080/02331934.2012.677447.  Google Scholar  F. Deutsch, The method of alternating orthogonal projections, Approximation Theory, Spline Functions and Applications,, Kluwer Academic Publishers, (1992). Google Scholar  Y. Gao, Viability criteria for differential inclusions,, \emph{J. Syst. Sci. Complex.}, 24 (2011), 825.  doi: 10.1007/s11424-011-9056-6.  Google Scholar  U. Garcia-palomares, Parallel projected aggregation methods for solving the convex feasibility problem,, \emph{SIAM J. Optim.}, 3 (1993), 882.  doi: 10.1137/0803046.  Google Scholar  U. M. Garcia-Palomares and F. J. Gonzalez-Castano, Incomplete projection algorithms for solving the convex feasibility problem,, \emph{Numer. Algorithms}, 18 (1998), 177.  doi: 10.1023/A:1019165330848.  Google Scholar  K. Goebel and W. A. Kirk, Topics in Metric Fixed Point Theory,, Cambridge Studies in Advanced Mathematics 28, (1990).  doi: 10.1017/CBO9780511526152.  Google Scholar  N. I. M. Gould, How good are projection methods for convex feasibility problems,, \emph{Comput. Optim. Appl.}, 40 (2008), 1.  doi: 10.1007/s10589-007-9073-5.  Google Scholar  G. T. Herman, Image Reconstruction From Projections: The Fundamentals of Computerized Tomography,, Academic Press, (1980). Google Scholar  K. C. Kiwiel, Block-iterative surrogate projection methods for convex feasibility problem,, \emph{Linear Algebra Appl.}, 215 (1995), 225.  doi: 10.1016/0024-3795(93)00089-I.  Google Scholar  L. Li and Y. Gao, Approximate subgradient projection algorithm for a convex feasibility problem,, \emph{J. Syst. Eng. Electron.}, 21 (2010), 527.   Google Scholar  T. Lucio, A parallel subgradient projections method for the convex feasibility problem,, \emph{J. Comput. Appl. Math.}, 18 (1987), 307.  doi: 10.1016/0377-0427(87)90004-5.  Google Scholar  P. E. Mainge, Convergence theorem for inertial KM-type algorithms,, \emph{J. Comput. Appl. Math.}, 219 (2008), 223.  doi: 10.1016/j.cam.2007.07.021.  Google Scholar  M. Moudafi, Convergence of a splitting inertial proximal method for monotone operators,, \emph{J. Comput. Appl. Math.}, 155 (2008), 447.  doi: 10.1016/S0377-0427(02)00906-8.  Google Scholar  A. Moudafi and E. Elisabeth, An approximate inertial proximal method using enlargement of a maximal monotone operator,, \emph{Int. J. Pure Appl. Math.}, 5 (2003), 283. Google Scholar  Z. Opial, Weak convergence of the sequence of successive approximations for nonexpansive mappings,, \emph{Bull. Am. Math. Soc.}, 73 (1967), 591. Google Scholar  G. Pierra, Decompasition through formalization in a product space,, \emph{Math. Program.}, 28 (1984), 96.  doi: 10.1007/BF02612715.  Google Scholar  B. T. Polyak, Some methods of speeding up the convergence of iteration method,, \emph{Zh. Vych. Math.}, 4 (1964), 791. Google Scholar

show all references

##### References:
  H. H. Bauschke and J. M. Borwein, On projection algorithms for solving convex feasibility problems,, \emph{SIAM Rev.}, 38 (1996), 367.  doi: 10.1137/S0036144593251710.  Google Scholar  H. H. Bauschke, J. M.Borwein, and A. S. Lewis, The method of cyclic projections for closed convex sets in Hilbert space,, in \emph{Proceedings of the Special Session on Optimization and Nonlinear Analysis}, (1995).   Google Scholar  S. Boyd, L. EI Ghaoui, E. Feron and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory,, Society for Industrial and Applied Mathematics, (1994).  doi: 10.1137/1.9781611970777.  Google Scholar  Y. Censor and A. Lent, Cyclic subgradient projections,, \emph{Math. Program.}, 24 (1982), 233.  doi: 10.1007/BF01585107.  Google Scholar  Y. Censor, Parallel application of block iterative methods in medical imaging and radiation therapy,, \emph{Math. Program.}, 42 (1998), 307.  doi: 10.1007/BF01589408.  Google Scholar  J. W. Chinneck, The constraint consensus method for finding approximately feasible points in nonlinear programs,, \emph{INFORMS J. Comput.}, 16 (2004), 255.  doi: 10.1287/ijoc.1030.0046.  Google Scholar  P. L. Combeties and S. G. Kruk, Extroplation algorithm for affine-convex feasibility problems,, \emph{Numer. Algorithms}, 41 (2006), 239.  doi: 10.1007/s11075-005-9010-6.  Google Scholar  Y. Dang and Y. Gao, Non-monotonous accelerated parallel subgradient projection algorithm for convex feasibility problem,, \emph{Optimization}, 63 (2014), 571.  doi: 10.1080/02331934.2012.677447.  Google Scholar  F. Deutsch, The method of alternating orthogonal projections, Approximation Theory, Spline Functions and Applications,, Kluwer Academic Publishers, (1992). Google Scholar  Y. Gao, Viability criteria for differential inclusions,, \emph{J. Syst. Sci. Complex.}, 24 (2011), 825.  doi: 10.1007/s11424-011-9056-6.  Google Scholar  U. Garcia-palomares, Parallel projected aggregation methods for solving the convex feasibility problem,, \emph{SIAM J. Optim.}, 3 (1993), 882.  doi: 10.1137/0803046.  Google Scholar  U. M. Garcia-Palomares and F. J. Gonzalez-Castano, Incomplete projection algorithms for solving the convex feasibility problem,, \emph{Numer. Algorithms}, 18 (1998), 177.  doi: 10.1023/A:1019165330848.  Google Scholar  K. Goebel and W. A. Kirk, Topics in Metric Fixed Point Theory,, Cambridge Studies in Advanced Mathematics 28, (1990).  doi: 10.1017/CBO9780511526152.  Google Scholar  N. I. M. Gould, How good are projection methods for convex feasibility problems,, \emph{Comput. Optim. Appl.}, 40 (2008), 1.  doi: 10.1007/s10589-007-9073-5.  Google Scholar  G. T. Herman, Image Reconstruction From Projections: The Fundamentals of Computerized Tomography,, Academic Press, (1980). Google Scholar  K. C. Kiwiel, Block-iterative surrogate projection methods for convex feasibility problem,, \emph{Linear Algebra Appl.}, 215 (1995), 225.  doi: 10.1016/0024-3795(93)00089-I.  Google Scholar  L. Li and Y. Gao, Approximate subgradient projection algorithm for a convex feasibility problem,, \emph{J. Syst. Eng. Electron.}, 21 (2010), 527.   Google Scholar  T. Lucio, A parallel subgradient projections method for the convex feasibility problem,, \emph{J. Comput. Appl. Math.}, 18 (1987), 307.  doi: 10.1016/0377-0427(87)90004-5.  Google Scholar  P. E. Mainge, Convergence theorem for inertial KM-type algorithms,, \emph{J. Comput. Appl. Math.}, 219 (2008), 223.  doi: 10.1016/j.cam.2007.07.021.  Google Scholar  M. Moudafi, Convergence of a splitting inertial proximal method for monotone operators,, \emph{J. Comput. Appl. Math.}, 155 (2008), 447.  doi: 10.1016/S0377-0427(02)00906-8.  Google Scholar  A. Moudafi and E. Elisabeth, An approximate inertial proximal method using enlargement of a maximal monotone operator,, \emph{Int. J. Pure Appl. Math.}, 5 (2003), 283. Google Scholar  Z. Opial, Weak convergence of the sequence of successive approximations for nonexpansive mappings,, \emph{Bull. Am. Math. Soc.}, 73 (1967), 591. Google Scholar  G. Pierra, Decompasition through formalization in a product space,, \emph{Math. Program.}, 28 (1984), 96.  doi: 10.1007/BF02612715.  Google Scholar  B. T. Polyak, Some methods of speeding up the convergence of iteration method,, \emph{Zh. Vych. Math.}, 4 (1964), 791. Google Scholar
  Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070  Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465  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  Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018  Vivina Barutello, Gian Marco Canneori, Susanna Terracini. Minimal collision arcs asymptotic to central configurations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 61-86. doi: 10.3934/dcds.2020218  Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076  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  Qingfang Wang, Hua Yang. Solutions of nonlocal problem with critical exponent. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5591-5608. doi: 10.3934/cpaa.2020253  Zhenzhen Wang, Tianshou Zhou. Asymptotic behaviors and stochastic traveling waves in stochastic Fisher-KPP equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020323  Wei Feng, Michael Freeze, Xin Lu. On competition models under allee effect: Asymptotic behavior and traveling waves. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5609-5626. doi: 10.3934/cpaa.2020256  Scipio Cuccagna, Masaya Maeda. A survey on asymptotic stability of ground states of nonlinear Schrödinger equations II. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020450  Stefano Bianchini, Paolo Bonicatto. Forward untangling and applications to the uniqueness problem for the continuity equation. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020384  Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $L^2-$norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077  Lei Liu, Li Wu. Multiplicity of closed characteristics on $P$-symmetric compact convex hypersurfaces in $\mathbb{R}^{2n}$. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378  Yichen Zhang, Meiqiang Feng. A coupled $p$-Laplacian elliptic system: Existence, uniqueness and asymptotic behavior. Electronic Research Archive, 2020, 28 (4) : 1419-1438. doi: 10.3934/era.2020075  Hoang The Tuan. On the asymptotic behavior of solutions to time-fractional elliptic equations driven by a multiplicative white noise. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020318  Yongxiu Shi, Haitao Wan. Refined asymptotic behavior and uniqueness of large solutions to a quasilinear elliptic equation in a borderline case. Electronic Research Archive, , () : -. doi: 10.3934/era.2020119  Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020453  Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031  Fioralba Cakoni, Pu-Zhao Kow, Jenn-Nan Wang. The interior transmission eigenvalue problem for elastic waves in media with obstacles. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020075

Impact Factor: