Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
projections onto convex sets; nonlinear operators; slow convergence
projections onto convex sets; nonlinear operators; slow convergence
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.
References:
[1 H. Bauschke and J. Borwein] On projection algorithms for solving convex feasibility problems. Siam Review 38 (1996), 367–426. DOI 10.1137/S0036144593251710 | MR 1409591 | Zbl 0865.47039
[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. DOI 10.1080/00207169008803865
[3] Y. Censor and S. A. Zenios: Parallel optimization. Theory, algorithms, and applications, Oxford University Press, Inc., New York, 1997. MR 1486040
[4] G. Crombez: Viewing parallel projection methods as sequential ones in convex feasibility problems. Trans. Amer. Math. Soc. 347 (1995), 2575–2583. DOI 10.1090/S0002-9947-1995-1277105-1 | MR 1277105 | Zbl 0846.46010
[5] G. Crombez: Improving the speed of convergence in the method of projections onto convex sets. Publicationes Mathematicae Debrecen 58 (2001), 29–48. MR 1807574 | Zbl 0973.65001
[6] F. Deutsch: The method of alternating orthogonal projections. In: “Approximation theory, spline functions and applications”, Kluwer Academic Publishers, 1992, pp. 105–121. MR 1165964 | Zbl 0751.41031
[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
[8] W. Gearhart and M. Koshy: Acceleration schemes for the method of alternating projections. J. Comp. Appl. Math. 26 (1989), 235–249. DOI 10.1016/0377-0427(89)90296-3 | MR 1010558
[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. DOI 10.1016/0041-5553(67)90113-9
[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
[11] D. Schott: Iterative solution of convex problems by Fejér-monotone methods. Numer. Funct. Anal. and Optimiz. 16 (1995), 1323–1357. DOI 10.1080/01630569508816676 | MR 1374979
[12] H. Stark and Y. Yang: Vector space projections. J. Wiley & Sons, Inc., New York, 1998.
[13] L. Vandenberghe and S. Boyd: Semidefinite programming. Siam Review 38 (1996), 49–95. DOI 10.1137/1038003 | MR 1379041
[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. DOI 10.1109/83.392332
[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
Search
Partner of
