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

Previous Article
2D system analysis via dual problems and polynomial matrix inequalities
NACO Home
This Issue
Next Article

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

Abstract
Related Papers

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,, \emph{SIAM Rev.}, 38 (1996), 367. doi: 10.1137/S0036144593251710.
[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).
[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.
[4]	Y. Censor and A. Lent, Cyclic subgradient projections,, \emph{Math. Program.}, 24 (1982), 233. doi: 10.1007/BF01585107.
[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.
[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.
[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.
[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.
[9]	F. Deutsch, The method of alternating orthogonal projections, Approximation Theory, Spline Functions and Applications,, Kluwer Academic Publishers, (1992).
[10]	Y. Gao, Viability criteria for differential inclusions,, \emph{J. Syst. Sci. Complex.}, 24 (2011), 825. doi: 10.1007/s11424-011-9056-6.
[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.
[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.
[13]	K. Goebel and W. A. Kirk, Topics in Metric Fixed Point Theory,, Cambridge Studies in Advanced Mathematics 28, (1990). doi: 10.1017/CBO9780511526152.
[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.
[15]	G. T. Herman, Image Reconstruction From Projections: The Fundamentals of Computerized Tomography,, Academic Press, (1980).
[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.
[17]	L. Li and Y. Gao, Approximate subgradient projection algorithm for a convex feasibility problem,, \emph{J. Syst. Eng. Electron.}, 21 (2010), 527.
[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.
[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.
[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.
[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.
[22]	Z. Opial, Weak convergence of the sequence of successive approximations for nonexpansive mappings,, \emph{Bull. Am. Math. Soc.}, 73 (1967), 591.
[23]	G. Pierra, Decompasition through formalization in a product space,, \emph{Math. Program.}, 28 (1984), 96. doi: 10.1007/BF02612715.
[24]	B. T. Polyak, Some methods of speeding up the convergence of iteration method,, \emph{Zh. Vych. Math.}, 4 (1964), 791.

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.
[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).
[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.
[4]	Y. Censor and A. Lent, Cyclic subgradient projections,, \emph{Math. Program.}, 24 (1982), 233. doi: 10.1007/BF01585107.
[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.
[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.
[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.
[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.
[9]	F. Deutsch, The method of alternating orthogonal projections, Approximation Theory, Spline Functions and Applications,, Kluwer Academic Publishers, (1992).
[10]	Y. Gao, Viability criteria for differential inclusions,, \emph{J. Syst. Sci. Complex.}, 24 (2011), 825. doi: 10.1007/s11424-011-9056-6.
[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.
[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.
[13]	K. Goebel and W. A. Kirk, Topics in Metric Fixed Point Theory,, Cambridge Studies in Advanced Mathematics 28, (1990). doi: 10.1017/CBO9780511526152.
[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.
[15]	G. T. Herman, Image Reconstruction From Projections: The Fundamentals of Computerized Tomography,, Academic Press, (1980).
[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.
[17]	L. Li and Y. Gao, Approximate subgradient projection algorithm for a convex feasibility problem,, \emph{J. Syst. Eng. Electron.}, 21 (2010), 527.
[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.
[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.
[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.
[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.
[22]	Z. Opial, Weak convergence of the sequence of successive approximations for nonexpansive mappings,, \emph{Bull. Am. Math. Soc.}, 73 (1967), 591.
[23]	G. Pierra, Decompasition through formalization in a product space,, \emph{Math. Program.}, 28 (1984), 96. doi: 10.1007/BF02612715.
[24]	B. T. Polyak, Some methods of speeding up the convergence of iteration method,, \emph{Zh. Vych. Math.}, 4 (1964), 791.

[1]	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
[2]	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
[3]	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
[4]	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
[5]	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
[6]	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
[7]	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
[8]	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
[9]	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
[10]	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
[11]	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
[12]	Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018134
[13]	Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial & Management Optimization, 2019, 15 (2) : 909-932. doi: 10.3934/jimo.2018077
[14]	Jinkui Liu, Shengjie Li. Multivariate spectral DY-type projection method for convex constrained nonlinear monotone equations. Journal of Industrial & Management Optimization, 2017, 13 (1) : 283-295. doi: 10.3934/jimo.2016017
[15]	Hongtruong Pham, Xiwen Lu. The inverse parallel machine scheduling problem with minimum total completion time. Journal of Industrial & Management Optimization, 2014, 10 (2) : 613-620. doi: 10.3934/jimo.2014.10.613
[16]	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
[17]	Ran Ma, Jiping Tao. An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. Journal of Industrial & Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057
[18]	Hedy Attouch, Alexandre Cabot, Zaki Chbani, Hassan Riahi. Rate of convergence of inertial gradient dynamics with time-dependent viscous damping coefficient. Evolution Equations & Control Theory, 2018, 7 (3) : 353-371. doi: 10.3934/eect.2018018
[19]	Philippe Angot, Pierre Fabrie. Convergence results for the vector penalty-projection and two-step artificial compressibility methods. Discrete & Continuous Dynamical Systems - B, 2012, 17 (5) : 1383-1405. doi: 10.3934/dcdsb.2012.17.1383
[20]	Sanming Liu, Zhijie Wang, Chongyang Liu. Proximal iterative Gaussian smoothing algorithm for a class of nonsmooth convex minimization problems. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 79-89. doi: 10.3934/naco.2015.5.79

Impact Factor:

American Institute of Mathematical Sciences