Geodesic
A sequential iteration algorithm with non-monotoneous behaviour in the method of projections onto convex sets
Czechoslovak Mathematical Journal, Tome 56 (2006) no. 2, pp. 491-506 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 40A99, 47H09, 47H10, 47N10, 49M30, 52A20, 90C25
Keywords: projections onto convex sets; nonlinear operators; slow convergence 
@article{CMJ_2006_56_2_a14,
     author = {Crombez, G.},
     title = {A sequential iteration algorithm with non-monotoneous behaviour in the method of projections onto convex sets},
     journal = {Czechoslovak Mathematical Journal},
     pages = {491--506},
     year = {2006},
     volume = {56},
     number = {2},
     mrnumber = {2291750},
     zbl = {1164.47399},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2006_56_2_a14/}
}
TY  - JOUR
AU  - Crombez, G.
TI  - A sequential iteration algorithm with non-monotoneous behaviour in the method of projections onto convex sets
JO  - Czechoslovak Mathematical Journal
PY  - 2006
SP  - 491
EP  - 506
VL  - 56
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/CMJ_2006_56_2_a14/
LA  - en
ID  - CMJ_2006_56_2_a14
ER  - 
%0 Journal Article
%A Crombez, G.
%T A sequential iteration algorithm with non-monotoneous behaviour in the method of projections onto convex sets
%J Czechoslovak Mathematical Journal
%D 2006
%P 491-506
%V 56
%N 2
%U http://geodesic.mathdoc.fr/item/CMJ_2006_56_2_a14/
%G en
%F CMJ_2006_56_2_a14
Crombez, G. A sequential iteration algorithm with non-monotoneous behaviour in the method of projections onto convex sets. Czechoslovak Mathematical Journal, Tome 56 (2006) no. 2, pp. 491-506. http://geodesic.mathdoc.fr/item/CMJ_2006_56_2_a14/

[1 H. Bauschke and J. Borwein] On projection algorithms for solving convex feasibility problems. Siam Review 38 (1996), 367–426. | DOI | MR | Zbl

[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

[3] Y. Censor and S. A. Zenios: Parallel optimization. Theory, algorithms, and applications, Oxford University Press, Inc., New York, 1997. | MR

[4] G. Crombez: Viewing parallel projection methods as sequential ones in convex feasibility problems. Trans. Amer. Math. Soc. 347 (1995), 2575–2583. | DOI | MR | Zbl

[5] G. Crombez: Improving the speed of convergence in the method of projections onto convex sets. Publicationes Mathematicae Debrecen 58 (2001), 29–48. | MR | Zbl

[6] F. Deutsch: The method of alternating orthogonal projections. In: “Approximation theory, spline functions and applications”, Kluwer Academic Publishers, 1992, pp. 105–121. | MR | Zbl

[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

[8] W. Gearhart and M. Koshy: Acceleration schemes for the method of alternating projections. J. Comp. Appl. Math. 26 (1989), 235–249. | DOI | MR

[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] M. Hanke and W. Niethammer: On the acceleration of Kaczmarz’s method for inconsistent linear systems. Linear Algebra Appl. 130 (1990), 83–98. | MR

[11] D. Schott: Iterative solution of convex problems by Fejér-monotone methods. Numer. Funct. Anal. and Optimiz. 16 (1995), 1323–1357. | DOI | MR

[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 | MR

[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

[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