×

A sequential iteration algorithm with non-monotoneous behaviour in the method of projections onto convex sets. (English) Zbl 1164.47399

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 a corridor consists in taking a big step at different moments during the iteration, because in that way the monotonous behavior 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 at the same time guarantees convergence of the constructed sequence to a point in the intersection of the sets. Concerning convergence speed, we compare experimentally the behavior of the new algorithm with that of an existing monotonous algorithm.

MSC:

47N10 Applications of operator theory in optimization, convex analysis, mathematical programming, economics
47H09 Contraction-type mappings, nonexpansive mappings, \(A\)-proper mappings, etc.
40A99 Convergence and divergence of infinite limiting processes
49M30 Other numerical methods in calculus of variations (MSC2010)
52A20 Convex sets in \(n\) dimensions (including convex hypersurfaces)
90C25 Convex programming
PDF BibTeX XML Cite
Full Text: DOI EuDML Link

References:

[1] H. Bauschke and J. Borwein On projection algorithms for solving convex feasibility problems. Siam Review 38 (1996), 367–426. · 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. · Zbl 0708.90064
[3] Y. Censor and S. A. Zenios: Parallel optimization. Theory, algorithms, and applications, Oxford University Press, Inc., New York, 1997.
[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
[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
[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
[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. · Zbl 0815.47067
[8] W. Gearhart and M. Koshy: Acceleration schemes for the method of alternating projections. J. Comp. Appl. Math. 26 (1989), 235–249. · Zbl 0688.65040
[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. · Zbl 0199.51002
[10] M. Hanke and W. Niethammer: On the acceleration of Kaczmarz’s method for inconsistent linear systems. Linear Algebra Appl. 130 (1990), 83–98. · Zbl 0708.65033
[11] D. Schott: Iterative solution of convex problems by Fejér-monotone methods. Numer. Funct. Anal. and Optimiz. 16 (1995), 1323–1357. · Zbl 0853.65055
[12] H. Stark and Y. Yang: Vector space projections. J. Wiley & Sons, Inc., New York, 1998. · Zbl 0903.65001
[13] L. Vandenberghe and S. Boyd: Semidefinite programming. Siam Review 38 (1996), 49–95. · Zbl 0845.65023
[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.
[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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.