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

Yazheng  Dang; Fanwen  Meng; Jie  Sun

doi:10.3934/naco.2016023

Article Contents

2016, Volume 6, Issue 4: 505-519. Doi: 10.3934/naco.2016023

This issue Previous Article 2D system analysis via dual problems and polynomial matrix inequalities Next Article

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

1.
Business School, University of Shanghai for Science and Technology, Shanghai
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: November 2016

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: 49M37, 90C25, 90C90.

Citation:

Related Papers

Cited by

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