A sequential iteration algorithm with non-monotoneous behaviour in the method of projections onto convex sets

Gilbert Crombez

Czechoslovak Mathematical Journal (2006)

  • Volume: 56, Issue: 2, page 491-506
  • ISSN: 0011-4642

Abstract

top
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.

How to cite

top

Crombez, Gilbert. "A sequential iteration algorithm with non-monotoneous behaviour in the method of projections onto convex sets." Czechoslovak Mathematical Journal 56.2 (2006): 491-506. <http://eudml.org/doc/31042>.

@article{Crombez2006,
abstract = {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.},
author = {Crombez, Gilbert},
journal = {Czechoslovak Mathematical Journal},
keywords = {projections onto convex sets; nonlinear operators; slow convergence; projections onto convex sets; nonlinear operators; slow convergence},
language = {eng},
number = {2},
pages = {491-506},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {A sequential iteration algorithm with non-monotoneous behaviour in the method of projections onto convex sets},
url = {http://eudml.org/doc/31042},
volume = {56},
year = {2006},
}

TY - JOUR
AU - Crombez, Gilbert
TI - A sequential iteration algorithm with non-monotoneous behaviour in the method of projections onto convex sets
JO - Czechoslovak Mathematical Journal
PY - 2006
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 56
IS - 2
SP - 491
EP - 506
AB - 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.
LA - eng
KW - projections onto convex sets; nonlinear operators; slow convergence; projections onto convex sets; nonlinear operators; slow convergence
UR - http://eudml.org/doc/31042
ER -

References

top
  1. 10.1137/S0036144593251710, Siam Review 38 (1996), 367–426. (1996) Zbl0865.47039MR1409591DOI10.1137/S0036144593251710
  2. 10.1080/00207169008803865, Intern. J. Computer Math. 34 (1990), 79–94. (1990) DOI10.1080/00207169008803865
  3. Parallel optimization, Theory, algorithms, and applications, Oxford University Press, Inc., New York, 1997. (1997) MR1486040
  4. 10.1090/S0002-9947-1995-1277105-1, Trans. Amer. Math. Soc. 347 (1995), 2575–2583. (1995) Zbl0846.46010MR1277105DOI10.1090/S0002-9947-1995-1277105-1
  5. Improving the speed of convergence in the method of projections onto convex sets, Publicationes Mathematicae Debrecen 58 (2001), 29–48. (2001) Zbl0973.65001MR1807574
  6. The method of alternating orthogonal projections, In: “Approximation theory, spline functions and applications”, Kluwer Academic Publishers, 1992, pp. 105–121. (1992) Zbl0751.41031MR1165964
  7. Random products of nonexpansive mappings, In: “Optimization and Nonlinear Analysis”, Pitman Research Notes in Mathematics Series, Vol. 244, Longman, Harlow, 1992, pp. 106–118. (1992) MR1184635
  8. 10.1016/0377-0427(89)90296-3, J. Comp. Appl. Math. 26 (1989), 235–249. (1989) MR1010558DOI10.1016/0377-0427(89)90296-3
  9. 10.1016/0041-5553(67)90113-9, USSR Comput. Math. and Math. Phys. 7 (1967), 1–24. (1967) DOI10.1016/0041-5553(67)90113-9
  10. On the acceleration of Kaczmarz’s method for inconsistent linear systems, Linear Algebra Appl. 130 (1990), 83–98. (1990) MR1057802
  11. 10.1080/01630569508816676, Numer. Funct. Anal. and Optimiz. 16 (1995), 1323–1357. (1995) MR1374979DOI10.1080/01630569508816676
  12. Vector space projections, J. Wiley & Sons, Inc., New York, 1998. (1998) 
  13. 10.1137/1038003, Siam Review 38 (1996), 49–95. (1996) MR1379041DOI10.1137/1038003
  14. 10.1109/83.392332, IEEE Trans. Image Processing 4 (1995), 896–908. (1995) DOI10.1109/83.392332
  15. 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. (1987) MR0896707

NotesEmbed ?

top

You must be logged in to post comments.