Skip to main content
SpringerLink
Log in

Algorithms for the Split Variational Inequality Problem

  • Original Paper
  • Published:
Numerical Algorithms Aims and scope Submit manuscript

Abstract

We propose a prototypical Split Inverse Problem (SIP) and a new variational problem, called the Split Variational Inequality Problem (SVIP), which is a SIP. It entails finding a solution of one inverse problem (e.g., a Variational Inequality Problem (VIP)), the image of which under a given bounded linear transformation is a solution of another inverse problem such as a VIP. We construct iterative algorithms that solve such problems, under reasonable conditions, in Hilbert space and then discuss special cases, some of which are new even in Euclidean space.

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

  2. Bauschke, H.H., Combettes, P.L.: A weak-to-strong convergence principle for Fejér-monotone methods in Hilbert spaces. Math. Oper. Res. 26, 248–264 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  3. Bertsekas, D.P., Tsitsiklis, J.N.: Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, Englwood Cliffs (1989)

    MATH  Google Scholar 

  4. Browder, F.E.: Fixed point theorems for noncompact mappings in Hilbert space. Proc. Natl. Acad. Sci. USA 53, 1272–1276 (1965)

    Article  MATH  MathSciNet  Google Scholar 

  5. Byrne, C.L.: Iterative projection onto convex sets using multiple Bregman distances. Inverse Probl. 15, 1295–1313 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  6. Byrne, C.: Iterative oblique projection onto convex sets and the split feasibility problem. Inverse Probl. 18, 441–453 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  7. Byrne, C.: A unified treatment of some iterative algorithms in signal processing and image reconstruction. Inverse Probl. 20 103–120 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  8. Cegielski, A.: Generalized relaxations of nonexpansive operators and convex feasibility problems. Contemp. Math. 513, 111–123 (2010)

    MathSciNet  Google Scholar 

  9. Cegielski, A., Censor, Y.: Opial-type theorems and the common fixed point problem. In: Bauschke, H., Burachik, R., Combettes, P., Elser, V., Luke, R., Wolkowicz, H. (eds.) Fixed-Point Algorithms for Inverse Problems in Science and Engineering, pp. 155–183. Springer, New York (2011)

    Chapter  Google Scholar 

  10. Censor, Y., Altschule, M.D., Powlis, W.D.: On the use of Cimmino’s simultaneous projections method for computing a solution of the inverse problem in radiation therapy treatment planning. Inverse Probl. 4, 607–623 (1988)

    Article  MATH  Google Scholar 

  11. Censor, Y., Bortfeld, T., Martin, B., Trofimov, A.: A unified approach for inversion problems in intensity-modulated radiation therapy. Phys. Med. Biol. 51, 2353–2365 (2006)

    Article  Google Scholar 

  12. 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. (2011, accepted for publication). doi:10.1007/s10589-011-9401-7. http://arxiv.org/abs/0912.4367

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

    Article  MathSciNet  Google Scholar 

  14. Censor, Y., Elfving, T.: A multiprojection algorithm using Bregman projections in product space. Numer. Algorithms 8, 221–239 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  15. Censor, Y., Elfving, T., Kopf, N., Bortfeld, T.: The multiple-sets split feasibility problem and its applications for inverse problems. Inverse Probl. 21, 2071–2084 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  16. Censor, Y., Gibali, A., Reich, S.: Extensions of Korpelevich’s extragradient method for solving the variational inequality problem in Euclidean space. Optimization (2011, accepted for publication)

  17. Censor, Y., Gibali, A., Reich, S.: The subgradient extragradient method for solving the variational inequality problem in Hilbert space. J. Optim. Theory Appl. 148, 318–335 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  18. Censor, Y., Gibali, A., Reich, S.: Strong convergence of subgradient extragradient methods for the variational inequality problem in Hilbert space. Optim. Methods Softw. (2011, accepted for publication)

  19. Censor, Y., Gibali, A., Reich, S., Sabach, S.: Common solutions to variational inequalities. Technical Report, 5 April 2011. Revised: July 18, 2011

  20. Censor, Y., Segal, A.: The split common fixed point problem for directed operators. J. Convex Anal. 16, 587–600 (2009)

    MATH  MathSciNet  Google Scholar 

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

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

    MathSciNet  Google Scholar 

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

    MATH  Google Scholar 

  24. Combettes, P.L.: Quasi-Fejérian analysis of some optimization algorithms. In: Butnariu, D., Censor, Y., Reich, S. (eds.) Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications, pp. 115–152. Elsevier, Amsterdam (2001)

    Google Scholar 

  25. Crombez, G.: A geometrical look at iterative methods for operators with fixed points. Numer. Funct. Anal. Optim. 26, 157–175 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  26. Crombez, G.: A hierarchical presentation of operators with fixed points on Hilbert spaces. Numer. Funct. Anal. Optim. 27, 259–277 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  27. Dang, Y., Gao, Y.: The strong convergence of a KM–CQ-like algorithm for a split feasibility problem. Inverse Probl. 27, 015007 (2011)

    Article  MathSciNet  Google Scholar 

  28. Goebel, K., Reich, S.: Uniform Convexity, Hyperbolic Geometry, and Nonexpansive Mappings. Marcel Dekker, New York (1984)

    MATH  Google Scholar 

  29. He, S., Yang, C., Duan, P.: Realization of the hybrid method for Mann iteration. Appl. Math. Comput. 217, 4239–4247 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  30. Korpelevich, G.M.: The extragradient method for finding saddle points and other problems. Ekon. Mat. Metody 12, 747–756 (1976)

    MATH  Google Scholar 

  31. López, G., Martín-Márquez, V., Xu, H.K.: Iterative algorithms for the multiple-sets split feasibility problem. In: Censor, Y., Jiang, M., Wang, G. (eds.) Biomedical Mathematics: Promising Directions in Imaging, Therapy Planning and Inverse Problems, pp. 243–279. Medical Physics Publishing, Madison (2010)

    Google Scholar 

  32. Măruşter, Ş., Popirlan, C.: On the Mann-type iteration and the convex feasibility problem. J. Comput. Appl. Math. 212, 390–396 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  33. Masad, E., Reich, S.: A note on the multiple-set split convex feasibility problem in Hilbert space. J. Nonlinear Convex Anal. 8, 367–371 (2007)

    MATH  MathSciNet  Google Scholar 

  34. Moudafi, A.: The split common fixed-point problem for demicontractive mappings. Inverse Probl. 26, 1–6 (2010)

    Article  MathSciNet  Google Scholar 

  35. Nadezhkina, N., Takahashi, W.: Weak convergence theorem by an extragradient method for nonexpansive mappings and monotone mappings. J. Optim. Theory Appl. 128, 191–201 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  36. Opial, Z.: Weak convergence of the sequence of successive approximations for nonexpansive mappings. Bull. Am. Math. Soc. 73, 591–597 (1967)

    Article  MATH  MathSciNet  Google Scholar 

  37. Pierra, G.: Decomposition through formalization in a product space. Math. Program. 28, 96–115 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  38. Qu, B., Xiu, N.: A note on the CQ algorithm for the split feasibility problem. Inverse Probl. 21, 1655–1666 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  39. Rockafellar, R.T.: On the maximality of sums of nonlinear monotone operators. Trans. Am. Math. Soc. 149, 75–88 (1970)

    Article  MATH  MathSciNet  Google Scholar 

  40. Schöpfer, F., Schuster, T., Louis, A.K.: An iterative regularization method for the solution of the split feasibility problem in Banach spaces. Inverse Probl. 24, 055008 (2008)

    Article  Google Scholar 

  41. Segal, A.: Directed operators for common fixed point problems and convex programming problems. Ph.D. Thesis, University of Haifa (2008)

  42. Takahashi, W., Toyoda, M.: Weak convergence theorems for nonexpansive mappings and monotone mappings. J. Optim. Theory Appl. 118, 417–428 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  43. Xu, H.K.: A variable Krasnosel’skii–Mann algorithm and the multiple-set split feasibility problem. Inverse Probl. 22, 2021–2034 (2006)

    Article  MATH  Google Scholar 

  44. Xu, H.K.: Iterative methods for the split feasibility problem in infinite-dimensional Hilbert spaces. Inverse Probl. 26, 105018 (2010)

    Article  Google Scholar 

  45. Yamada, I., Ogura, N.: Adaptive projected subgradient method for asymptotic minimization of sequence of nonnegative convex functions. Numer. Funct. Anal. Optim. 25, 593–617 (2005)

    Article  MathSciNet  Google Scholar 

  46. Yang, Q.: The relaxed CQ algorithm solving the split feasibility problem. Inverse Probl. 20, 1261–1266 (2004)

    Article  MATH  Google Scholar 

  47. Zaknoon, M.: Algorithmic developments for the convex feasibility problem. Ph.D. Thesis, University of Haifa (2003)

  48. Zhang, W., Han, D., Li, Z.: A self-adaptive projection method for solving the multiple-sets split feasibility problem. Inverse Probl. 25, 115001 (2009)

    Article  MathSciNet  Google Scholar 

  49. Zhao, J., Yang, Q.: Several solution methods for the split feasibility problem. Inverse Probl. 21, 1791–1800 (2005)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

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

    Yair Censor

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

    Aviv Gibali & Simeon Reich

Authors
  1. Yair Censor
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Aviv Gibali
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Simeon Reich
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yair Censor.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Censor, Y., Gibali, A. & Reich, S. Algorithms for the Split Variational Inequality Problem. Numer Algor 59, 301–323 (2012). https://doi.org/10.1007/s11075-011-9490-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11075-011-9490-5

Keywords

Search

Navigation