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

Capa

Citar

Texto integral

Resumo

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.

Sobre autores

A Gibali

Ort Braude College

Email: avivg@braude.ac.il

D Teller

Ort Braude College

Email: ktui619@gmail.com

Bibliografia

  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.

Arquivos suplementares

Arquivos suplementares
Ação
1. JATS XML
Baixar

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».