Skip to main content
SpringerLink
Log in

Global and linear convergence of alternated inertial methods for split feasibility problems

  • Original Paper
  • Published:
Revista de la Real Academia de Ciencias Exactas, Físicas y Naturales. Serie A. Matemáticas Aims and scope Submit manuscript

Abstract

The focus of this paper is to introduce algorithms with alternated inertial step to solve split feasibility problems. We obtain global convergence of the sequences of iterates generated by the proposed methods under some appropriate conditions. When the split feasibility problem satisfies some bounded linear regularity property, we show that the generated sequences converge linearly. As far as we know, no linear convergence result has been obtained before now for algorithms with inertial steps to solve split feasibility problems in the literature. Our numerical experiments which include a real-world application to jointly constrained Nash equilibrium model show that our methods outperform some inertial methods and other related methods for split feasibility problems in the literature.

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. Alvarez, F., Attouch, H.: An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping. Set Valued Anal. 9(1–2), 3–11 (2001)

    MathSciNet  MATH  Google Scholar 

  2. Alsulami, S.M., Takahashi, W.: Iterative methods for the split feasibility problem in Banach spaces. J. Nonlinear Convex Anal. 16(4), 585–596 (2015)

    MathSciNet  MATH  Google Scholar 

  3. Attouch, H., Peypouquet, J., Redont, P.: A dynamical approach to an inertial forward-backward algorithm for convex minimization. SIAM J. Optim. 24(1), 232–256 (2014)

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  5. Bauschke, H.H., Combettes, P.L.: Convex analysis and monotone operator theory in Hilbert spaces. CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, pp. xvi+468. Springer, New York (2011) (ISBN: 978-1-4419-9466-0)

  6. Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1), 183–202 (2009)

    MathSciNet  MATH  Google Scholar 

  7. Bot, R.I., Csetnek, E.R., Hendrich, C.: Inertial Douglas-Rachford splitting for monotone inclusion. Appl. Math. Comput. 256, 472–487 (2015)

    MathSciNet  MATH  Google Scholar 

  8. Bot, R.I., Csetnek, E.R.: An inertial alternating direction method of multipliers. Minimax Theory Appl. 1, 29–49 (2016)

    MathSciNet  MATH  Google Scholar 

  9. Bot, R.I., Csetnek, E.R.: An inertial forward-backward-forward primal-dual splitting algorithm for solving monotone inclusion problems. Numer. Alg. 71, 519–540 (2016)

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  12. Censor, Y., Lent, A.: An iterative row-action method for interval convex programming. J. Optim. Theory Appl. 34(3), 321–353 (1981)

    MathSciNet  MATH  Google Scholar 

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

    Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  15. Chen, J.-Z., Ceng, L.-C., Qiu, Y.-Q., Kong, Z.-R.: Extra-gradient methods for solving split feasibility and fixed point problems. Fixed Point Theory Appl. (2015) (Paper No. 192, 21 pp)

  16. Chuang, C.-S.: Hybrid inertial proximal algorithm for the split variational inclusion problem in Hilbert spaces with applications. Optimization 66(5), 777–792 (2017)

    MathSciNet  MATH  Google Scholar 

  17. Contreras, J., Klusch, M., Krawczyk, J.B.: Numerical solution to Nash–Cournot equilibria in coupled constraint electricity markets. IEEE Trans. Power Syst. 19, 195–206 (2004)

    Google Scholar 

  18. Dang, Y., Gao, Y.: The strong convergence of a KM-CQ-like algorithm for a split feasibility problem. Inverse Prob. 27(1), 015007 (2011). 9 pp

    MathSciNet  MATH  Google Scholar 

  19. Dang, Y., Sun, J., Xu, H.: Inertial accelerated algorithms for solving a split feasibility problem. J. Ind. Manag. Optim. 13(3), 1383–1394 (2017)

    MathSciNet  MATH  Google Scholar 

  20. Dang, Y.-Z., Sun, J., Zhang, S.: Double projection algorithms for solving the split feasibility problems. J. Ind. Manag. Optim. 15(4), 2023–2034 (2019)

    MathSciNet  MATH  Google Scholar 

  21. Dong, Q.L., Li, X., Rassias, Th.M.: Two projection algorithms for a class of split feasibility problems with jointly constrained Nash equilibrium models. Optimization. https://doi.org/10.1080/02331934.2020.1753741

  22. Dong, Q.L., Tang, Y.C., Cho, Y.J., Rassias, T.M.: “Optimal” choice of the step length of the projection and contraction methods for solving the split feasibility problem. J. Global Optim. 71(2), 341–360 (2018)

    MathSciNet  MATH  Google Scholar 

  23. Dong, Q.L., Yuan, H.B., Cho, Y.J., Rassias, T.M.: Modified inertial Mann algorithm and inertial CQ-algorithm for nonexpansive mappings. Optim. Lett. 12, 87–102 (2018)

    MathSciNet  MATH  Google Scholar 

  24. Fukushima, M.: A relaxed projection method for variational inequalities. Math. Program. 35(1), 58–70 (1986)

    MathSciNet  MATH  Google Scholar 

  25. Gibali, A., Liu, L.-W., Tang, Y.-C.: Note on the modified relaxation CQ algorithm for the split feasibility problem. Optim. Lett. 12(4), 817–830 (2018)

    MathSciNet  MATH  Google Scholar 

  26. Gorbachuk, V.M.: Cournot-Nash and Bertrand-Nash equilibria for a heterogeneous duopoly of differentiated products. Cybern. Syst. Anal. 46(1), 25–33 (2010) (translated from Kibernet. Sistem. Anal. 46 (2010), no. 1, 29–37)

  27. Goebel, K., Kirk, W.A.: On Metric Fixed Point Theory. Cambridge University Press, Cambridge (1990)

    MATH  Google Scholar 

  28. Hendrickx, J.M., Olshevsky, A.: Matrix \(p\)-norms are NP-hard to approximate if \(P\ne 1,2,\infty \). SIAM J. Matrix Anal. Appl. 31(5), 2802–2812 (2010)

    MathSciNet  MATH  Google Scholar 

  29. Iusem, A.N.: On some properties of paramonotone operator. Convex Anal. 5, 269–278 (1998)

    MathSciNet  MATH  Google Scholar 

  30. Iutzeler, F., Hendrickx, J.M.: A generic online acceleration scheme for optimization algorithms via relaxation and inertia. Optim. Methods Softw. 34(2), 383–405 (2019)

    MathSciNet  MATH  Google Scholar 

  31. Iutzeler, F., Malick, J.: On the proximal gradient algorithm with alternated inertia. J. Optim. Theory Appl. 176(3), 688–710 (2018)

    MathSciNet  MATH  Google Scholar 

  32. Jouymandi, Z., Moradlou, F.: Extragradient and linesearch methods for solving split feasibility problems in Hilbert spaces. Math. Methods Appl. Sci. 42(12), 4343–4359 (2019)

    MathSciNet  MATH  Google Scholar 

  33. Kraikaew, R., Saejung, S.: A simple look at the method for solving split feasibility problems in Hilbert spaces. Rev. R. Acad. Cienc. Exactas FÌs. Nat. Ser. A Mat. RACSAM 114(3) (2020) (Paper No. 117, 9 pp)

  34. López, G., Martín-Márquez, V., Wang, F., Xu, H.-K.: Solving the split feasibility problem without prior knowledge of matrix norms. Inverse Prob. 28(8), 085004 (2012). 18 pp

    MathSciNet  MATH  Google Scholar 

  35. Lorenz, D.A., Pock, T.: An inertial forward-backward algorithm for monotone inclusions. J. Math. Imaging Vision 51(2), 311–325 (2015)

    MathSciNet  MATH  Google Scholar 

  36. Maingé, P.E.: Inertial iterative process for fixed points of certain quasi-nonexpansive mappings. Set Valued Anal. 15, 67–79 (2007)

    MathSciNet  MATH  Google Scholar 

  37. Malitsky, Y., Pock, T.: A first-order primal-dual algorithm with linesearch. SIAM J. Optim. 28(1), 411–432 (2018)

    MathSciNet  MATH  Google Scholar 

  38. Moudafi, A., Oliny, M.: Convergence of a splitting inertial proximal method for monotone operators. J. Comput. Appl. Math. 155, 447–454 (2003)

    MathSciNet  MATH  Google Scholar 

  39. Mu, Z., Peng, Y.: A note on the inertial proximal point method. Stat. Optim. Inf. Comput. 3(3), 241–248 (2015)

    MathSciNet  Google Scholar 

  40. Nesterov, Y.: A method for solving the convex programming problem with convergence rate \(O(1/k^2)\). Dokl. Akad. Nauk SSSR 269, 543–547 (1983)

    MathSciNet  Google Scholar 

  41. Polyak, B.T.: Some methods of speeding up the convergence of iteration methods. U. S. S. R. Comput. Math. Math. Phys. 4, 1–17 (1964)

    Google Scholar 

  42. Qin, X., Wang, L.: A fixed point method for solving a split feasibility problem in Hilbert spaces. Rev. R. Acad. Cienc. Exactas FÌs. Nat. Ser. A Mat. RACSAM 113(1), 315–325 (2019)

    MathSciNet  MATH  Google Scholar 

  43. Shehu, Y.: Iterative methods for split feasibility problems in certain Banach spaces. J. Nonlinear Convex Anal. 16(12), 2351–2364 (2015)

    MathSciNet  MATH  Google Scholar 

  44. Shehu, Y., Gibali, A.: New inertial relaxed method for solving split feasibilities. Optim. Lett. (2020). https://doi.org/10.1007/s11590-020-01603-1

    Article  Google Scholar 

  45. Shehu, Y., Iyiola, O.S., Enyi, C.D.: An iterative algorithm for solving split feasibility problems and fixed point problems in Banach spaces. Numer. Algorithms 72(4), 835–864 (2016)

    MathSciNet  MATH  Google Scholar 

  46. Shehu, Y., Vuong, P.T., Cholamjiak, P.: A self-adaptive projection method with an inertial technique for split feasibility problems in Banach spaces with applications to image restoration problems. J. Fixed Point Theory Appl. 21(2) (2019) (Art. 50, 24 pp)

  47. Shehu, Y., Iyiola, O.S.: Convergence analysis for the proximal split feasibility problem using an inertial extrapolation term method. J. Fixed Point Theory Appl. 19(4), 2483–2510 (2017)

    MathSciNet  MATH  Google Scholar 

  48. Shehu, Y., Iyiola, O.S.: Projection methods with alternating inertial steps for variational inequalities: weak and linear convergence. Appl. Numer. Math. 157, 315–337 (2020)

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  50. Suantai, S., Pholasa, N., Cholamjiak, P.: Relaxed CQ algorithms involving the inertial technique for multiple-sets split feasibility problems. Rev. R. Acad. Cienc. Exactas Fís. Nat. Ser. A Mat. RACSAM 113(2), 1081–1099 (2019)

    MathSciNet  MATH  Google Scholar 

  51. Suantai, S., Pholasa, N., Cholamjiak, P.: The modified inertial relaxed CQ algorithm for solving the split feasibility problems. J. Ind. Manag. Optim. 14(4), 1595–1615 (2018)

    MathSciNet  MATH  Google Scholar 

  52. Tang, Y., Gibali, A.: Several inertial methods for solving split convex feasibilities and related problems. Rev. R. Acad. Cienc. Exactas FÌs. Nat. Ser. A Mat. RACSAM 114(3) (2020) (Paper No. 121, 25 pp)

  53. Wang, F., Xu, H.K.: Cyclic algorithms for split feasibility problems in Hilbert spaces. Nonlinear Anal. Theory Methods Appl. 74, 4105–4111 (2011)

    MathSciNet  MATH  Google Scholar 

  54. Wang, J., Hu, Y., Li, C., Yao, J.-C.: Linear convergence of CQ algorithms and applications in gene regulatory network inference. Inverse Prob. 33(5), 055017 (2017)

    MathSciNet  MATH  Google Scholar 

  55. Wang, J., Hu, Y., Yu, C.K.W., Zhuang, X.: A family of projection gradient methods for solving the multiple-sets split feasibility problem. J. Optim. Theory Appl. 183(2), 520–534 (2019)

    MathSciNet  MATH  Google Scholar 

  56. Wei, J.Y., Yves, S.: Spatial oligopolistic electricity models with Cournot generators and regulated transmission prices. Oper. Res. 47(2), 102–112 (1999)

    MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  60. Yao, Y., Qin, X., Yao, J.-C.: Convergence analysis of an inertial iterate for the proximal split feasibility problem. J. Nonlinear Convex Anal. 20(3), 489–498 (2019)

    MathSciNet  Google Scholar 

  61. Yen, L.H., Huyen, N.T.T., Muu, L.D.: A subgradient algorithm for a class of nonlinear split feasibility problems: application to jointly constrained Nash equilibrium models. J. Global Optim. 73, 849–868 (2019)

    MathSciNet  MATH  Google Scholar 

  62. Yu, H., Zhan, W., Wang, F.: The ball-relaxed CQ algorithms for the split feasibility problem. Optimization 67(10), 1687–1699 (2018)

    MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors are grateful to the anonymous referee for the insightful comments and suggestions which have improved the earlier version of the manuscript greatly. We also thank Professor Fenghui Wang for his valuable help in the program. The second and third authors are supported by the Open Fund of Tianjin Key Lab for Advanced Signal Processing (2019ASP-TJ03).

Author information

Authors and Affiliations

  1. Department of Mathematics, Zhejiang Normal University, Jinhua, 321004, China

    Yekini Shehu

  2. College of Science, Civil Aviation University of China, Tianjin, 300300, China

    Qiao-Li Dong & Lu-Lu Liu

Authors
  1. Yekini Shehu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Qiao-Li Dong
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Lu-Lu Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yekini Shehu.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Shehu, Y., Dong, QL. & Liu, LL. Global and linear convergence of alternated inertial methods for split feasibility problems. RACSAM 115, 53 (2021). https://doi.org/10.1007/s13398-020-00979-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s13398-020-00979-0

Keywords

Mathematics Subject Classification

Search

Navigation