Skip to main content
SpringerLink
Log in

Strict Fejér Monotonicity by Superiorization of Feasibility-Seeking Projection Methods

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

We consider the superiorization methodology, which can be thought of as lying between feasibility-seeking and constrained minimization. It is not quite trying to solve the full-fledged constrained minimization problem; rather, the task is to find a feasible point which is superior (with respect to the objective function value) to one returned by a feasibility-seeking only algorithm. Our main result reveals new information about the mathematical behavior of the superiorization methodology. We deal with a constrained minimization problem with a feasible region, which is the intersection of finitely many closed convex constraint sets, and use the dynamic string-averaging projection method, with variable strings and variable weights, as a feasibility-seeking algorithm. We show that any sequence, generated by the superiorized version of a dynamic string-averaging projection algorithm, not only converges to a feasible point but, additionally, also either its limit point solves the constrained minimization problem or the sequence is strictly Fejér monotone with respect to a subset of the solution set of the original problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. 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, 1065–1088 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  2. Censor, Y., Zaslavski, A.J.: Convergence and perturbation resilience of dynamic string-averaging projection methods. Comput. Optim. Appl. 54, 65–76 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  3. Bauschke, H.H., Koch, V.R.: Projection methods: swiss army knives for solving feasibility and best approximation problems with halfspaces. In: Reich, S., Zaslavski, A. (eds.) Proceedings of the Workshop “Infinite Products of Operators and Their Applications”, Haifa, 2012 (2013). Accepted for publication. http://arxiv.org/abs/1301.4506, https://people.ok.ubc.ca/bauschke/Research/c16

  4. Butnariu, D., Davidi, R., Herman, G.T., Kazantsev, I.G.: Stable convergence behavior under summable perturbations of a class of projection methods for convex feasibility and optimization problems. IEEE J. Sel. Top. Signal Process. 1, 540–547 (2007)

    Article  Google Scholar 

  5. Censor, Y., Davidi, R., Herman, G.T.: Perturbation resilience and superiorization of iterative algorithms. Inverse Probl. 26, 065008 (2010)

    Article  MathSciNet  Google Scholar 

  6. Davidi, R., Herman, G.T., Censor, Y.: Perturbation-resilient block-iterative projection methods with application to image reconstruction from projections. Int. Trans. Oper. Res. 16, 505–524 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  7. Garduño, E., Herman, G.T.: Superiorization of the ML-EM algorithm. IEEE Trans. Nucl. Sci. 61, 162–172 (2014)

    Article  Google Scholar 

  8. Davidi, R., Censor, Y., Schulte, R.W., Geneser, S., Xing, L.: Feasibility-seeking and superiorization algorithms applied to inverse treatment planning in radiation therapy. Contemp. Math., accepted for publication. http://arxiv.org/abs/1402.1310

  9. Herman, G.T., Davidi, R.: Image reconstruction from a small number of projections. Inverse Probl. 24, 045011 (2008)

    Article  MathSciNet  Google Scholar 

  10. Herman, G.T., Garduño, E., Davidi, R., Censor, Y.: Superiorization: an optimization heuristic for medical physics. Med. Phys. 39, 5532–5546 (2012)

    Article  Google Scholar 

  11. Jin, W., Censor, Y., Jiang, M.: A heuristic superiorization-like approach to bioluminescence tomography. In: International Federation for Medical and Biological Engineering (IFMBE) Proceedings, vol 39, pp. 1026–1029 (2012)

  12. Nikazad, T., Davidi, R., Herman, G.: Accelerated perturbation-resilient block-iterative projection methods with application to image reconstruction. Inverse Probl. 28, 035005 (2012)

    Article  MathSciNet  Google Scholar 

  13. Penfold, S.N., Schulte, R.W., Censor, Y., Rosenfeld, A.B.: Total variation superiorization schemes in proton computed tomography image reconstruction. Med. Phys. 37, 5887–5895 (2010)

    Article  Google Scholar 

  14. Censor, Y., Davidi, R., Herman, G.T., Schulte, R.W., Tetruashvili, L.: Projected subgradient minimization versus superiorization. J. Optim. Theory Appl. 160, 730–747 (2014)

    Article  MATH  MathSciNet  Google Scholar 

  15. Butnariu, D., Reich, S., Zaslavski, A.J.: Convergence to fixed points of inexact orbits of Bregman-monotone and of nonexpansive operators in Banach spaces. In: Nathansky, H .F., de Buen, B.G., Goebel, K., Kirk, W.A., Sims, B. (eds.) Fixed Point Theory and its Applications, (Conference Proceedings, Guanajuato, Mexico, 2005), pp. 11–32. Yokahama Publishers, Yokahama (2006)

  16. Butnariu, D., Reich, S., Zaslavski, A.J.: Stable convergence theorems for infinite products and powers of nonexpansive mappings. Numer. Funct. Anal. Optim. 29, 304–323 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  17. Censor, Y., Zaslavski, A.J.: String-averaging projected subgradient methods for constrained minimization. Optim. Methods Softw. 29, 658–670 (2014)

    Article  MATH  MathSciNet  Google Scholar 

  18. Bauschke, H.H., Borwein, J.M.: On projection algorithms for solving convex feasibility problems. SIAM Rev. 38, 367–426 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  19. Byrne, C.L.: Applied Iterative Methods. AK Peters, Wellsely (2008)

    MATH  Google Scholar 

  20. Chinneck, J.W.: Feasibility and Infeasibility in Optimization: Algorithms and Computational Methods. Springer, New York (2007)

    Google Scholar 

  21. Censor, Y., Zenios, S.A.: Parallel Optimization: Theory, Algorithms, and Applications. Oxford University Press, New York (1997)

    MATH  Google Scholar 

  22. Aharoni, R., Censor, Y.: Block-iterative projection methods for parallel computation of solutions to convex feasibility problems. Linear Algebra Appl. 120, 165–175 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  23. Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York (2011)

    MATH  Google Scholar 

  24. Bauschke, H.H., Matoušková, E., Reich, S.: Projection and proximal point methods: convergence results and counterexamples. Nonlinear Anal-Theor. 56, 715–738 (2004)

    Article  MATH  Google Scholar 

  25. Cegielski, A.: Iterative Methods for Fixed Point Problems in Hilbert Spaces. Lecture Notes in Mathematics, vol. 2057. Springer, Berlin (2012)

  26. Escalante, R., Raydan, M.: Alternating Projection Methods. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2011)

  27. Galántai, A.: Projectors and Projection Methods. Kluwer Academic Publishers, Dordrecht (2004)

    Book  MATH  Google Scholar 

  28. Herman, G.T.: Fundamentals of Computerized Tomography: Image Reconstruction from Projections, 2nd edn. Springer, Berlin (2009)

    Book  Google Scholar 

  29. Luo, S., Zhou, T.: Superiorization of EM algorithm and its application in single-photon emission computed tomography (SPECT). Inverse Probl. Imaging 8, 223–246 (2014)

    Article  MATH  MathSciNet  Google Scholar 

  30. Censor, Y., Elfving, T., Herman, G.T.: Averaging strings of sequential iterations for convex feasibility problems. In: Butnariu, D., Censor, Y., Reich, S. (eds.) Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications, pp. 101–114. Elsevier, Amsterdam (2001)

    Chapter  Google Scholar 

  31. Censor, Y., Segal, A.: On the string averaging method for sparse common fixed point problems. Int. Trans. Oper. Res. 16, 481–494 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  32. Censor, Y., Segal, A.: On string-averaging for sparse problems and on the split common fixed point problem. Contemp. Math. 513, 125–142 (2010)

    Article  MathSciNet  Google Scholar 

  33. Censor, Y., Tom, E.: Convergence of string-averaging projection schemes for inconsistent convex feasibility problems. Optim. Methods Softw. 18, 543–554 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  34. Crombez, G.: Finding common fixed points of strict paracontractions by averaging strings of sequential iterations. J. Nonlinear Conv. Anal. 3, 345–351 (2002)

    MATH  MathSciNet  Google Scholar 

  35. Gordon, D., Gordon, R.: Component-averaged row projections: a robust, block-parallel scheme for sparse linear systems. SIAM J. Sci. Comput. 27, 1092–1117 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  36. Penfold, S.N., Schulte, R.W., Censor, Y., Bashkirov, V., McAllister, S., Schubert, K.E., Rosenfeld, A.B.: Block-iterative and string-averaging projection algorithms in proton computed tomography image reconstruction. In: Censor, Y., Jiang, M., Wang, G. (eds.) Biomedical Mathematics: Promising Directions in Imaging, Therapy Planning and Inverse Problems, pp. 347–367. Medical Physics , Madison (2010)

  37. Rhee, H.: An application of the string averaging method to one-sided best simultaneous approximation. J. Korean Soc. Math. Educ. Ser. B 10, 49–56 (2003)

    MATH  MathSciNet  Google Scholar 

  38. Schott, D.: Basic properties of Fejér monotone sequences. Rostocker Math. Kolloq. 49, 57–74 (1995)

    MATH  MathSciNet  Google Scholar 

  39. Schrapp, M.J., Herman, G.T.: Data fusion in X-ray computed tomography using an superiorization approach. Rev. Sci. Instrum. 85, 053701 (2014)

    Article  Google Scholar 

Download references

Acknowledgments

We thank Gabor Herman for an enlightening discussion about terminology, and we greatly appreciate the constructive comments of two anonymous reviewers which helped us improve the paper.

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Haifa, Mt. Carmel, Haifa, 3498838, Israel

    Yair Censor

  2. Department of Mathematics, The Technion – Israel Institute of Technology, Technion City, Haifa, 32000, Israel

    Alexander J. Zaslavski

Authors
  1. Yair Censor
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alexander J. Zaslavski
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yair Censor.

Additional information

Communicated by Jonathan Michael Borwein.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Censor, Y., Zaslavski, A.J. Strict Fejér Monotonicity by Superiorization of Feasibility-Seeking Projection Methods. J Optim Theory Appl 165, 172–187 (2015). https://doi.org/10.1007/s10957-014-0591-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-014-0591-x

Keywords

Mathematics Subject Classification

Search

Navigation