American Institute of Mathematical Sciences

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

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

Yazheng Dang 1, , Fanwen Meng 2, and  Jie Sun 3,

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.
Keywords: asymptotic convergence., Convex feasible problem, inertial parallel projection algorithm.
Mathematics Subject Classification: 49M37, 90C25, 90C9.
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, SIAM Rev., 38 (1996), 367-426. 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 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, Philadlphia, PA, USA, 1994. doi: 10.1137/1.9781611970777.  Google Scholar

[4]

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

[5]

Y. Censor, Parallel application of block iterative methods in medical imaging and radiation therapy, Math. Program., 42 (1998), 307-325. doi: 10.1007/BF01589408.  Google Scholar

[6]

J. W. Chinneck, The constraint consensus method for finding approximately feasible points in nonlinear programs, INFORMS J. Comput., 16 (2004), 255-265. doi: 10.1287/ijoc.1030.0046.  Google Scholar

[7]

P. L. Combeties and S. G. Kruk, Extroplation algorithm for affine-convex feasibility problems, Numer. Algorithms, 41 (2006), 239-274. 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, Optimization, 63 (2014), 571-584. 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, Dordrecht, 1992.  Google Scholar

[10]

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

[11]

U. Garcia-palomares, Parallel projected aggregation methods for solving the convex feasibility problem, SIAM J. Optim., 3 (1993), 882-900. 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, Numer. Algorithms, 18 (1998), 177-193. 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, Cambridge University Press, Cambridge, 1990. doi: 10.1017/CBO9780511526152.  Google Scholar

[14]

N. I. M. Gould, How good are projection methods for convex feasibility problems, Comput. Optim. Appl., 40 (2008), 1-12. doi: 10.1007/s10589-007-9073-5.  Google Scholar

[15]

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

[16]

K. C. Kiwiel, Block-iterative surrogate projection methods for convex feasibility problem, Linear Algebra Appl., 215 (1995), 225-260. 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, J. Syst. Eng. Electron., 21 (2010), 527-530. Google Scholar

[18]

T. Lucio, A parallel subgradient projections method for the convex feasibility problem, J. Comput. Appl. Math., 18 (1987), 307-320. doi: 10.1016/0377-0427(87)90004-5.  Google Scholar

[19]

P. E. Mainge, Convergence theorem for inertial KM-type algorithms, J. Comput. Appl. Math., 219 (2008), 223-236. doi: 10.1016/j.cam.2007.07.021.  Google Scholar

[20]

M. Moudafi, Convergence of a splitting inertial proximal method for monotone operators, J. Comput. Appl. Math., 155 (2008), 447-454. 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, Int. J. Pure Appl. Math., 5 (2003), 283-299.  Google Scholar

[22]

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

[23]

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

[24]

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

show all references

References:
[1]

H. H. Bauschke and J. M. Borwein, On projection algorithms for solving convex feasibility problems, SIAM Rev., 38 (1996), 367-426. 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 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, Philadlphia, PA, USA, 1994. doi: 10.1137/1.9781611970777.  Google Scholar

[4]

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

[5]

Y. Censor, Parallel application of block iterative methods in medical imaging and radiation therapy, Math. Program., 42 (1998), 307-325. doi: 10.1007/BF01589408.  Google Scholar

[6]

J. W. Chinneck, The constraint consensus method for finding approximately feasible points in nonlinear programs, INFORMS J. Comput., 16 (2004), 255-265. doi: 10.1287/ijoc.1030.0046.  Google Scholar

[7]

P. L. Combeties and S. G. Kruk, Extroplation algorithm for affine-convex feasibility problems, Numer. Algorithms, 41 (2006), 239-274. 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, Optimization, 63 (2014), 571-584. 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, Dordrecht, 1992.  Google Scholar

[10]

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

[11]

U. Garcia-palomares, Parallel projected aggregation methods for solving the convex feasibility problem, SIAM J. Optim., 3 (1993), 882-900. 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, Numer. Algorithms, 18 (1998), 177-193. 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, Cambridge University Press, Cambridge, 1990. doi: 10.1017/CBO9780511526152.  Google Scholar

[14]

N. I. M. Gould, How good are projection methods for convex feasibility problems, Comput. Optim. Appl., 40 (2008), 1-12. doi: 10.1007/s10589-007-9073-5.  Google Scholar

[15]

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

[16]

K. C. Kiwiel, Block-iterative surrogate projection methods for convex feasibility problem, Linear Algebra Appl., 215 (1995), 225-260. 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, J. Syst. Eng. Electron., 21 (2010), 527-530. Google Scholar

[18]

T. Lucio, A parallel subgradient projections method for the convex feasibility problem, J. Comput. Appl. Math., 18 (1987), 307-320. doi: 10.1016/0377-0427(87)90004-5.  Google Scholar

[19]

P. E. Mainge, Convergence theorem for inertial KM-type algorithms, J. Comput. Appl. Math., 219 (2008), 223-236. doi: 10.1016/j.cam.2007.07.021.  Google Scholar

[20]

M. Moudafi, Convergence of a splitting inertial proximal method for monotone operators, J. Comput. Appl. Math., 155 (2008), 447-454. 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, Int. J. Pure Appl. Math., 5 (2003), 283-299.  Google Scholar

[22]

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

[23]

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

[24]

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

[1]

Xueling Zhou, Meixia Li, Haitao Che. Relaxed successive projection algorithm with strong convergence for the multiple-sets split equality problem. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2557-2572. doi: 10.3934/jimo.2020082
[2]

Abd-semii Oluwatosin-Enitan Owolabi, Timilehin Opeyemi Alakoya, Adeolu Taiwo, Oluwatosin Temitope Mewomo. A new inertial-projection algorithm for approximating common solution of variational inequality and fixed point problems of multivalued mappings. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021004
[3]

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

Le Thi Hoai An, Tran Duc Quynh, Kondo Hloindo Adjallah. A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. Journal of Industrial & Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243
[5]

Chengjin Li. Parameter-related projection-based iterative algorithm for a kind of generalized positive semidefinite least squares problem. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 511-520. doi: 10.3934/naco.2020048
[6]

Abdulkarim Hassan Ibrahim, Poom Kumam, Min Sun, Parin Chaipunya, Auwal Bala Abubakar. Projection method with inertial step for nonlinear equations: Application to signal recovery. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021173
[7]

Qingzhi Yang. The revisit of a projection algorithm with variable steps for variational inequalities. Journal of Industrial & Management Optimization, 2005, 1 (2) : 211-217. doi: 10.3934/jimo.2005.1.211
[8]

Guodong Ma, Jinbao Jian. A QP-free algorithm of quasi-strongly sub-feasible directions for inequality constrained optimization. Journal of Industrial & Management Optimization, 2015, 11 (1) : 307-328. doi: 10.3934/jimo.2015.11.307
[9]

Chunming Tang, Jinbao Jian, Guoyin Li. A proximal-projection partial bundle method for convex constrained minimax problems. Journal of Industrial & Management Optimization, 2019, 15 (2) : 757-774. doi: 10.3934/jimo.2018069
[10]

Luchuan Ceng, Qamrul Hasan Ansari, Jen-Chih Yao. Extragradient-projection method for solving constrained convex minimization problems. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 341-359. doi: 10.3934/naco.2011.1.341
[11]

Janosch Rieger. A learning-enhanced projection method for solving convex feasibility problems. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021054
[12]

Xin Yang, Nan Wang, Lingling Xu. A parallel Gauss-Seidel method for convex problems with separable structure. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 557-570. doi: 10.3934/naco.2020051
[13]

Gaohang Yu, Shanzhou Niu, Jianhua Ma. Multivariate spectral gradient projection method for nonlinear monotone equations with convex constraints. Journal of Industrial & Management Optimization, 2013, 9 (1) : 117-129. doi: 10.3934/jimo.2013.9.117
[14]

Rongliang Chen, Jizu Huang, Xiao-Chuan Cai. A parallel domain decomposition algorithm for large scale image denoising. Inverse Problems & Imaging, 2019, 13 (6) : 1259-1282. doi: 10.3934/ipi.2019055
[15]

Leyu Hu, Wenxing Zhang, Xingju Cai, Deren Han. A parallel operator splitting algorithm for solving constrained total-variation retinex. Inverse Problems & Imaging, 2020, 14 (6) : 1135-1156. doi: 10.3934/ipi.2020058
[16]

Jaakko Ketola, Lars Lamberg. An algorithm for recovering unknown projection orientations and shifts in 3-D tomography. Inverse Problems & Imaging, 2011, 5 (1) : 75-93. doi: 10.3934/ipi.2011.5.75
[17]

Yanxing Cui, Chuanlong Wang, Ruiping Wen. On the convergence of generalized parallel multisplitting iterative methods for semidefinite linear systems. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 863-873. doi: 10.3934/naco.2012.2.863
[18]

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

Abdul Rahim Khan, Chinedu Izuchukwu, Maggie Aphane, Godwin Chidi Ugwunnadi. Modified inertial algorithm for solving mixed equilibrium problems in Hadamard spaces. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021039
[20]

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

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences