Previous |  Up |  Next


Title: A sequential iteration algorithm with non-monotoneous behaviour in the method of projections onto convex sets (English)
Author: Crombez, G.
Language: English
Journal: Czechoslovak Mathematical Journal
ISSN: 0011-4642 (print)
ISSN: 1572-9141 (online)
Volume: 56
Issue: 2
Year: 2006
Pages: 491-506
Summary lang: English
Category: math
Summary: The method of projections onto convex sets to find a point in the intersection of a finite number of closed convex sets in a Euclidean space, may lead to slow convergence of the constructed sequence when that sequence enters some narrow “corridor” between two or more convex sets. A way to leave such corridor consists in taking a big step at different moments during the iteration, because in that way the monotoneous behaviour that is responsible for the slow convergence may be interrupted. In this paper we present a technique that may introduce interruption of the monotony for a sequential algorithm, but that at the same time guarantees convergence of the constructed sequence to a point in the intersection of the sets. We compare experimentally the behaviour concerning the speed of convergence of the new algorithm with that of an existing monotoneous algorithm. (English)
Keyword: projections onto convex sets
Keyword: nonlinear operators
Keyword: slow convergence
MSC: 40A99
MSC: 47H09
MSC: 47H10
MSC: 47N10
MSC: 49M30
MSC: 52A20
MSC: 90C25
idZBL: Zbl 1164.47399
idMR: MR2291750
Date available: 2009-09-24T11:34:47Z
Last updated: 2020-07-03
Stable URL:
Reference: [1 H. Bauschke and J. Borwein] : On projection algorithms for solving convex feasibility problems.Siam Review 38 (1996), 367–426. Zbl 0865.47039, MR 1409591, 10.1137/S0036144593251710
Reference: [2] D. Butnariu and Y. Censor: On the behaviour of a block-iterative projection method for solving convex feasibility problems.Intern. J. Computer Math. 34 (1990), 79–94. 10.1080/00207169008803865
Reference: [3] Y. Censor and S. A. Zenios: Parallel optimization.Theory, algorithms, and applications, Oxford University Press, Inc., New York, 1997. MR 1486040
Reference: [4] G. Crombez: Viewing parallel projection methods as sequential ones in convex feasibility problems.Trans. Amer. Math. Soc. 347 (1995), 2575–2583. Zbl 0846.46010, MR 1277105, 10.1090/S0002-9947-1995-1277105-1
Reference: [5] G. Crombez: Improving the speed of convergence in the method of projections onto convex sets.Publicationes Mathematicae Debrecen 58 (2001), 29–48. Zbl 0973.65001, MR 1807574
Reference: [6] F. Deutsch: The method of alternating orthogonal projections.In: “Approximation theory, spline functions and applications”, Kluwer Academic Publishers, 1992, pp. 105–121. Zbl 0751.41031, MR 1165964
Reference: [7] J. Dye and S. Reich: Random products of nonexpansive mappings.In: “Optimization and Nonlinear Analysis”, Pitman Research Notes in Mathematics Series, Vol. 244, Longman, Harlow, 1992, pp. 106–118. MR 1184635
Reference: [8] W. Gearhart and M. Koshy: Acceleration schemes for the method of alternating projections.J. Comp. Appl. Math. 26 (1989), 235–249. MR 1010558, 10.1016/0377-0427(89)90296-3
Reference: [9] L. G. Gubin, B. T. Polyak and E. V. Raik: The method of projections for finding the common point of convex sets.USSR Comput. Math. and Math. Phys. 7 (1967), 1–24. 10.1016/0041-5553(67)90113-9
Reference: [10] M. Hanke and W. Niethammer: On the acceleration of Kaczmarz’s method for inconsistent linear systems.Linear Algebra Appl. 130 (1990), 83–98. MR 1057802
Reference: [11] D. Schott: Iterative solution of convex problems by Fejér-monotone methods.Numer. Funct. Anal. and Optimiz. 16 (1995), 1323–1357. MR 1374979, 10.1080/01630569508816676
Reference: [12] H. Stark and Y. Yang: Vector space projections.J. Wiley & Sons, Inc., New York, 1998.
Reference: [13] L. Vandenberghe and S. Boyd: Semidefinite programming.Siam Review 38 (1996), 49–95. MR 1379041, 10.1137/1038003
Reference: [14] Y. Yang, N. Galatsanos and A. Katsaggelos: Projection-based spatially adaptive reconstruction of block-transform compressed images.IEEE Trans. Image Processing 4 (1995), 896–908. 10.1109/83.392332
Reference: [15] D. C. Youla: Mathematical theory of image restoration by the method of convex projections.In: H. Stark (editor), “Image recovery: theory and applications”, Academic Press, New York, 1987, pp. 29–77. MR 0896707


Files Size Format View
CzechMathJ_56-2006-2_15.pdf 367.3Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo