A Real-Time Iterative Projection Scheme for Solving the Common Fixed Point Problem and Its Applications

Cover Page

Cite item

Full Text

Abstract

In this paper, we are concerned with the Common Fixed Point Problem (CFPP) with demicontractive operators and its special instance, the Convex Feasibility Problem (CFP) in real Hilbert spaces. Motivated by the recent result of Ordon˜ ez et al. [35] and in general, the field of online/real-time algorithms, e.g., [20, 21, 30], in which the entire input is not available from the beginning and given piece-by-piece, we propose an online/real-time iterative scheme for solving CFPPs and CFPs in which the involved operators/sets emerge along time. This scheme is capable of operating on any block, for any finite number of iterations, before moving, in a serial way, to the next block. The scheme is based on the recent novel result of Reich and Zalas [37] known as the Modular String Averaging (MSA) procedure. The convergence of the scheme follows [37] and other classical results in the fields of fixed point theory and variational inequalities, such as [34]. Numerical experiments for linear and non-linear feasibility problems with applications to image recovery are presented and demonstrate the validity and potential applicability of our scheme, e.g., to online/real-time scenarios.

About the authors

A Gibali

Ort Braude College

Email: avivg@braude.ac.il

D Teller

Ort Braude College

Email: ktui619@gmail.com

References

  1. Губин Л. Г., Поляк Б. Т., Райк Е. В. Метод проекции для нахождения общей точки выпуклых множеств// Журн. выч. мат. и мат. физ. - 1967. - 7.- C. 1-24.
  2. Aharoni R., Censor Y. Block-iterative projection methods for parallel computation of solutions to convex feasibility problems// Linear Algebra Appl. - 1989. - 120. - C. 165-175.
  3. Baillon J.-B., Bruck R. E., Reich S. On the asymptotic behavior of nonexpansive mappings and semigroups in banach spaces// Houston J. Math. - 1978. - 4. - C. 1-9.
  4. Bauschke H. H., Borwein J. On projection algorithms for solving convex feasibility problems// SIAM Rev. - 1996. - 38. - C. 367-426.
  5. Bauschke H. H., Combettes P. L. Convex analysis and monotone operator theory in Hilbert spaces. - Berlin: Springer, 2011.
  6. Bauschke H. H., Koch V. R. Projection methods: Swiss army knives for solving feasibility and best approximation problems with halfspaces// В сб.: «Infinite Products of Operators and Their Applications. A Research Workshop of the Israel Science Foundation, Haifa, Israel, May 21-24, 2012». - Providence: Am. Math. Soc., 2015. - С. 1-40.
  7. Borwein J. M., Tam М. K. A cyclic Douglas-Rachford iteration scheme// J. Optim. Theory Appl. - 2014. - 160.- C. 1-29.
  8. Browder F. E. Fixed point theorems for noncompact mappings in Hilbert space// Proc. Natl. Acad. Sci. USA. - 1965. - 53. - C. 1272-1276.
  9. Byrne C. L. A unified treatment of some iterative algorithms in signal processing and image reconstruction// Inverse Problems. - 1999. - 20. - C. 1295-1313.
  10. Byrne C. L. Applied iterative methods. - Wellsely: AK Peters, 2008.
  11. Cegielski A. Iterative methods for fixed point problems in Hilbert spaces. - Berlin-Heidelberg: Springer, 2012.
  12. Cegielski A., Reich S., Zalas R. Regular sequences of quasi-nonexpansive operators and their applications// SIAM J. Optim. - 2018. - 28. - C. 1508-1532.
  13. Cegielski A., Zalas R. Methods for variational inequality problem over the intersection of fixed point sets of quasi-nonexpansive operators// Numer. Funct. Anal. Optim. - 2013. - 34. - C. 255-283.
  14. Cegielski A., Zalas R. Properties of a class of approximately shrinking operators and their applications// Fixed Point Theory. - 2014. - 15. - C. 399-426.
  15. Censor Y., Chen W., Combettes P. L., Davidi R., Herman G. T. On the effectiveness of projection methods for convex feasibility problems with linear inequality constraints// Comput. Optim. Appl. - 2012. - 51.- C. 1065-1088.
  16. Censor Y., Elfving T., Herman G. T. Averaging strings of sequential iterations for convex feasibility problems// В сб.: «Infinite Products of Operators and Their Applications. A Research Workshop of the Israel Science Foundation, Haifa, Israel, March 13-16, 2000». - Amsterdam: North-Holland, 2001. - С. 101-113.
  17. Censor Y., Zenios S. A. Parallel optimization: theory, algorithms, and applications. - New York: Oxford Univ. Press, 1997.
  18. Cimmino G. Calcolo approssiomatto per le soluzioni dei sistemi di equazioni lineari// La Ricerca Sci. XVI. Ser. II. - 1938. - 1. - C. 326-333.
  19. Combettes P. L. Quasi-Feje´rian analysis of some optimization algorithms// В сб.: «Infinite Products of Operators and Their Applications. A Research Workshop of the Israel Science Foundation, Haifa, Israel, March 13-16, 2000». - Amsterdam: North-Holland, 2001. - С. 115-152.
  20. Das I., Potra F. A. Subsequent convergence of iterative methods with applications to real-time modelpredictive control// J. Optim. Theory Appl. - 2003. - 119. - C. 37-47.
  21. Diehl M. Real-Time optimization for large scale nonlinear processes. - Heidelberg: Univ. Heidelberg, 2001.
  22. Escalante R., Raydan M. Alternating projection methods. - Philadelphia: SIAM, 2011.
  23. Gala´ ntai A. Projectors and projection methods. - Boston-Dordrecht-London: Kluwer Academic Publ., 2004.
  24. Goebel K., Reich S. Uniform convexity, hyperbolic geometry, and nonexpansive mappings. - New York- Basel: Marcel Dekker, 1984.
  25. Gordon D., Gordon R. Component-averaged row projections: A robust block-parallel scheme for sparse linear systems// SIAM J. Sci. Comput. - 2005. - 27. - C. 1092-1117.
  26. Gordon R., Bender R., Herman G. T. Algebraic reconstruction techniques (art) for three-dimensional electron microscopy and X-ray photography// Bull. Am. Math. Soc. - 1970. - 29. - C. 471-481.
  27. Hansen P. C., Saxild-Hansen M. AIR Tools - a MATLAB package of algebraic iterative reconstruction methods// J. Comput. Appl. Math. - 2012. - 236, № 8. - C. 2167-2178.
  28. Iusem A., Jofre´ A., Thompson P. Incremental constraint projection methods for monotone stochastic variational inequalities// arXiv:1703.00272v2. - 2017.
  29. Kaczmarz S. Angena¨herte auflo¨sung von systemen linearer gleichungen// Bull. Int. l’Acad. Polon. Sci. Lett. A. - 1937. - 35. - C. 355-357.
  30. Karp R. M. On-line algorithms versus off-line algorithms: How much is it worth to know the future?// В сб.: «Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture, Information Processing ’92». - 1992. - 1. - С. 416-429.
  31. Leventhal L., Lewis A. S. Randomized methods for linear constraints: convergence rates and conditioning// Math. Oper. Res. - 2010. - 35. - C. 641-654.
  32. Ma˘ rus¸ter S¸ t., Popirlan C. On the Mann-type iteration and the convex feasibility problem// J. Comput. Appl. Math. - 2008. - 212. - C. 390-396.
  33. Needell D. Randomized Kaczmarz solver for noisy linear systems// BIT Numer. Math. - 2010. - 50.- C. 395-403.
  34. Opial Z. Weak convergence of the sequence of successive approximations for nonexpansive mappings// Bull. Am. Math. Soc. - 1967. - 73. - C. 591-597.
  35. Ordon˜ ez C. E., Karonis N., Duffin K., Coutrakon G., Schulte R., Johnson R., Pankuch M. A real-time image reconstruction system for particle treatment planning using proton computed tomography (PCT)// Phys. Proc. - 2017. - 90. - C. 193-199.
  36. Penfold S., Censor Y., Schulte R. W., Bashkirov V., McAllister S., Schubert K. E., Rosenfeld A. B. Blockiterative and string-averaging projection algorithms in proton computed tomography image reconstruction// В сб.: «Biomedical Mathematics: Promising Directions in Imaging, Therapy Planning and Inverse Problems». - Madison: Medical Phys. Publ., 2010. - С. 347-368.
  37. Reich S., Zalas R. A modular string averaging procedure for solving the common fixed point problem for quasi-nonexpansive mappings in hilbert space// Numer. Algorithms. - 2016. - 72. - C. 297-323.

Copyright (c) 2019 Contemporary Mathematics. Fundamental Directions

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies