A real-time iterative projection scheme for solving the common fixed point problem and its applications

A. Gibali ; D. Teller

Contemporary Mathematics. Fundamental Directions, Contemporary problems in mathematics and physics, Tome 64 (2018) no. 4, pp. 616-636.

Résumé

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

Bibliographie

[1] L. G. Gurin, B. T. Polyak, E. V. Raik, “The method of projections for finding the common point of convex sets”, J. Comput. Math. Math. Phys., 7:6 (1967,), 1211–1228 (in Russian) | MR | Zbl

[2] Aharoni R., Censor Y., “Block-iterative projection methods for parallel computation of solutions to convex feasibility problems”, Linear Algebra Appl., 120 (1989), 165–175 | DOI | MR | Zbl

[3] Baillon J.-B., Bruck R. E., Reich S., “On the asymptotic behavior of nonexpansive mappings and semigroups in banach spaces”, Houston J. Math., 4 (1978), 1–9 | MR | Zbl

[4] Bauschke H. H., Borwein J., “On projection algorithms for solving convex feasibility problems”, SIAM Rev., 38 (1996), 367–426 | DOI | MR | Zbl

[5] Bauschke H. H., Combettes P. L., Convex analysis and monotone operator theory in Hilbert spaces, Springer, Berlin, 2011 | MR | Zbl

[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), Am. Math. Soc., Providence, 2015, 1–40 | MR | Zbl

[7] Borwein J. M., Tam M. K., “A cyclic Douglas–Rachford iteration scheme”, J. Optim. Theory Appl., 160 (2014), 1–29 | DOI | MR | Zbl

[8] Browder F. E., “Fixed point theorems for noncompact mappings in Hilbert space”, Proc. Natl. Acad. Sci. USA, 53 (1965), 1272–1276 | DOI | MR | Zbl

[9] Byrne C. L., “A unified treatment of some iterative algorithms in signal processing and image reconstruction”, Inverse Problems, 20 (1999), 1295–1313 | DOI | MR

[10] Byrne C. L., Applied iterative methods, AK Peters, Wellsely, 2008 | MR | Zbl

[11] Cegielski A., Iterative methods for fixed point problems in Hilbert spaces, Springer, Berlin–Heidelberg, 2012 | MR | Zbl

[12] Cegielski A., Reich S., Zalas R., “Regular sequences of quasi-nonexpansive operators and their applications”, SIAM J. Optim., 28 (2018), 1508–1532 | DOI | MR | Zbl

[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., 34 (2013), 255–283 | DOI | MR | Zbl

[14] Cegielski A., Zalas R., “Properties of a class of approximately shrinking operators and their applications”, Fixed Point Theory, 15 (2014), 399–426 | MR | Zbl

[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., 51 (2012), 1065–1088 | DOI | MR | Zbl

[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), North-Holland, Amsterdam, 2001, 101–113 | MR | Zbl

[17] Censor Y., Zenios S. A., Parallel optimization: theory, algorithms, and applications, Oxford Univ. Press, New York, 1997 | MR | Zbl

[18] Cimmino G., “Calcolo approssiomatto per le soluzioni dei sistemi di equazioni lineari”, La Ricerca Sci. XVI. Ser. II, 1 (1938), 326–333 | Zbl

[19] Combettes P. L., “Quasi-Fejé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), North-Holland, Amsterdam, 2001, 115–152 | MR | Zbl

[20] Das I., Potra F. A., “Subsequent convergence of iterative methods with applications to real-time model-predictive control”, J. Optim. Theory Appl., 119 (2003), 37–47 | DOI | MR | Zbl

[21] Diehl M., Real-Time optimization for large scale nonlinear processes, Univ. Heidelberg, Heidelberg, 2001 | Zbl

[22] Escalante R., Raydan M., Alternating projection methods, SIAM, Philadelphia, 2011 | MR | Zbl

[23] Galántai A., Projectors and projection methods, Kluwer Academic Publ., Boston–Dordrecht–London, 2004 | MR | Zbl

[24] Goebel K., Reich S., Uniform convexity, hyperbolic geometry, and nonexpansive mappings, Marcel Dekker, New York–Basel, 1984 | MR | Zbl

[25] Gordon D., Gordon R., “Component-averaged row projections: A robust block-parallel scheme for sparse linear systems”, SIAM J. Sci. Comput., 27 (2005), 1092–1117 | DOI | MR | Zbl

[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., 29 (1970), 471–481

[27] Hansen P. C., Saxild-Hansen M., “AIR Tools – a MATLAB package of algebraic iterative reconstruction methods”, J. Comput. Appl. Math., 236:8 (2012), 2167–2178 | DOI | MR | Zbl

[28] Iusem A., Jofré A., Thompson P., Incremental constraint projection methods for monotone stochastic variational inequalities, 2017, arXiv: 1703.00272v2

[29] Kaczmarz S., “Angenäherte auflösung von systemen linearer gleichungen”, Bull. Int. l'Acad. Polon. Sci. Lett. A, 35 (1937), 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, v. 1, 1992, 416–429

[31] Leventhal L., Lewis A. S., “Randomized methods for linear constraints: convergence rates and conditioning”, Math. Oper. Res., 35 (2010), 641–654 | DOI | MR | Zbl

[32] Măruşter Şt., Popirlan C., “On the Mann-type iteration and the convex feasibility problem”, J. Comput. Appl. Math., 212 (2008), 390–396 | DOI | MR

[33] Needell D., “Randomized Kaczmarz solver for noisy linear systems”, BIT Numer. Math., 50 (2010), 395–403 | DOI | MR | Zbl

[34] Opial Z., “Weak convergence of the sequence of successive approximations for nonexpansive mappings”, Bull. Am. Math. Soc., 73 (1967), 591–597 | DOI | MR | Zbl

[35] Ordoñ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., 90 (2017), 193–199 | DOI

[36] Penfold S., Censor Y., Schulte R. W., Bashkirov V., McAllister S., Schubert K. E., Rosenfeld A. B., “Block-iterative and string-averaging projection algorithms in proton computed tomography image reconstruction”, Biomedical Mathematics: Promising Directions in Imaging, Therapy Planning and Inverse Problems, Medical Phys. Publ., Madison, 2010, 347–368 | MR

[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, 72 (2016), 297–323 | DOI | MR | Zbl