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: | http://hdl.handle.net/10338.dmlcz/128080 |

. | |

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/ |