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

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

[2]

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

[3]

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

[4]

Y. Censor and A. Lent, Cyclic subgradient projections,, \emph{Math. Program.}, 24 (1982), 233.  doi: 10.1007/BF01585107.  Google Scholar

[5]

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

[6]

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

[7]

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

[8]

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

[9]

F. Deutsch, The method of alternating orthogonal projections, Approximation Theory, Spline Functions and Applications,, Kluwer Academic Publishers, (1992).   Google Scholar

[10]

Y. Gao, Viability criteria for differential inclusions,, \emph{J. Syst. Sci. Complex.}, 24 (2011), 825.  doi: 10.1007/s11424-011-9056-6.  Google Scholar

[11]

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

[12]

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

[13]

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

[14]

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

[15]

G. T. Herman, Image Reconstruction From Projections: The Fundamentals of Computerized Tomography,, Academic Press, (1980).   Google Scholar

[16]

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

[17]

L. Li and Y. Gao, Approximate subgradient projection algorithm for a convex feasibility problem,, \emph{J. Syst. Eng. Electron.}, 21 (2010), 527.   Google Scholar

[18]

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

[19]

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

[20]

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

[21]

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

[22]

Z. Opial, Weak convergence of the sequence of successive approximations for nonexpansive mappings,, \emph{Bull. Am. Math. Soc.}, 73 (1967), 591.   Google Scholar

[23]

G. Pierra, Decompasition through formalization in a product space,, \emph{Math. Program.}, 28 (1984), 96.  doi: 10.1007/BF02612715.  Google Scholar

[24]

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

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

[2]

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

[3]

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

[4]

Y. Censor and A. Lent, Cyclic subgradient projections,, \emph{Math. Program.}, 24 (1982), 233.  doi: 10.1007/BF01585107.  Google Scholar

[5]

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

[6]

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

[7]

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

[8]

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

[9]

F. Deutsch, The method of alternating orthogonal projections, Approximation Theory, Spline Functions and Applications,, Kluwer Academic Publishers, (1992).   Google Scholar

[10]

Y. Gao, Viability criteria for differential inclusions,, \emph{J. Syst. Sci. Complex.}, 24 (2011), 825.  doi: 10.1007/s11424-011-9056-6.  Google Scholar

[11]

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

[12]

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

[13]

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

[14]

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

[15]

G. T. Herman, Image Reconstruction From Projections: The Fundamentals of Computerized Tomography,, Academic Press, (1980).   Google Scholar

[16]

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

[17]

L. Li and Y. Gao, Approximate subgradient projection algorithm for a convex feasibility problem,, \emph{J. Syst. Eng. Electron.}, 21 (2010), 527.   Google Scholar

[18]

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

[19]

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

[20]

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

[21]

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

[22]

Z. Opial, Weak convergence of the sequence of successive approximations for nonexpansive mappings,, \emph{Bull. Am. Math. Soc.}, 73 (1967), 591.   Google Scholar

[23]

G. Pierra, Decompasition through formalization in a product space,, \emph{Math. Program.}, 28 (1984), 96.  doi: 10.1007/BF02612715.  Google Scholar

[24]

B. T. Polyak, Some methods of speeding up the convergence of iteration method,, \emph{Zh. Vych. Math.}, 4 (1964), 791.   Google Scholar

[1]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

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

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

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: 

Metrics

  • PDF downloads (60)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]