[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

General splitting methods with linearization for the split feasibility problem

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

In this article, we introduce a general splitting method with linearization to solve the split feasibility problem and propose a way of selecting the stepsizes such that the implementation of the method does not need any prior information about the operator norm. We present the constant and adaptive relaxation parameters, and the latter is “optimal” in theory. These ways of selecting stepsizes and relaxation parameters are also practised to the relaxed splitting method with linearization where the two closed convex sets are both level sets of convex functions. The weak convergence of two proposed methods is established under standard conditions and the linear convergence of the general splitting method with linearization is analyzed. The numerical examples are presented to illustrate the advantage of our methods by comparing with other methods.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

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. Aragón Artacho, F.J., Campoy, R.: Solving graph coloring problems with the Douglas–Rachford algorithm. Set Valued Var. Anal. 26, 277–304 (2018)

    MathSciNet  MATH  Google Scholar 

  2. Aragón Artacho, F.J., Campoy, R., Elser, V.: An enhanced formulation for solving graph coloring problems with the Douglas–Rachford algorithm. J. Glob. Optim. 77(2), 383–403 (2020)

    MathSciNet  MATH  Google Scholar 

  3. Aragón Artacho, F.J., Borwein, J.M.: Global convergence of a non-convex Douglas–Rachford iteration. J. Glob. Optim. 57, 753–769 (2013)

    MathSciNet  MATH  Google Scholar 

  4. Aragón Artacho, F.J., Borwein, J.M., Tam, M.K.: Recent results on Douglas–Rachford methods for combinatorial optimization problems. J. Optim. Theory App. 163, 1–30 (2014)

    MathSciNet  MATH  Google Scholar 

  5. Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd edn. Springer, Berlin (2017)

    MATH  Google Scholar 

  6. Bauschke, H.H., Noll, D.: On the local convergence of the Douglas–Rachford algorithm. Arch. Math. 102, 589–600 (2014)

    MathSciNet  MATH  Google Scholar 

  7. Bauschke, H.H., Moursi, W.M.: On the Douglas–Rachford algorithm. Math. Program. 164, 263–284 (2017)

    MathSciNet  MATH  Google Scholar 

  8. Bauschke, H.H., Moursi, W.M.: The Douglas–Rachford algorithm for two (not necessarily intersecting) affine subspaces. SIAM J. Optim. 26, 968–985 (2016)

    MathSciNet  MATH  Google Scholar 

  9. Borwein, J.M., Tam, M.K.: A cyclic Douglas–Rachford iteration scheme. J. Optim. Theory Appl. 160, 1–29 (2014)

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  12. Cegielski, A.: Iterative Methods for Fixed Point Problems in Hilbert Spaces. Springer, Berlin (2012)

    MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  14. Combettes, P.L., Pesquet, J.C.: A Douglas–Rachford splitting approach to nonsmooth convex variational signal recovery. IEEE J. Sel. Top. Signal Process. 1, 564–574 (2007)

    Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  16. Dong, Q.L., He, S., Zhao, J.: Solving the split equality problem without prior knowledge of operator norms. Optimization 64(9), 1887–1906 (2015)

    MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

  18. 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. Glob. Optim. 71, 341–360 (2018)

    MathSciNet  MATH  Google Scholar 

  19. Dong, Q.L., Yao, Y., He, S.: Weak convergence theorems of the modified relaxed projection algorithms for the split feasibility problem in hilbert spaces. Optim. Lett. 8, 1031–1046 (2014)

    MathSciNet  MATH  Google Scholar 

  20. Douglas, J., Rachford, H.H.: On the numerical solution of heat conduction problems in two or three space variables. Trans. Am. Math. Soc. 82, 421–439 (1956)

    MathSciNet  MATH  Google Scholar 

  21. Eckstein, J., Bertsekas, D.P.: On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55, 293–318 (1992)

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  24. Giselsson, P., Boyd, S.: Diagonal scaling in Douglas–Rachford splitting and ADMM. In: Proceedings of the 53rd IEEE Conference on Decision and Control, pp. 5033–5039 (2014)

  25. He, B., Yuan, X.: On the \(O(1/n)\) convergence rate of the Douglas–Rachford alternating direction method. SIAM J. Numer. Anal. 50, 700–709 (2012)

    MathSciNet  MATH  Google Scholar 

  26. He, B., Liu, H., Wang, Z., Yuan, X.: A strictly contractive Peaceman–Rachford splitting method for convex programming. SIAM J. Optim. 24(3), 1011–1040 (2014)

    MathSciNet  MATH  Google Scholar 

  27. He, S., Xu, H.K.: The selective projection method for convex feasibility and split feasibility problems. J. Nonlinear Sci. Appl. 19(7), 1199–1215 (2018)

    MathSciNet  MATH  Google Scholar 

  28. Hesse, R., Luke, D.R., Neumann, P.: Alternating projections and Douglas–Rachford for sparse affine feasibility. IEEE Trans. Signal. Proces. 62, 4868–4881 (2014)

    MathSciNet  MATH  Google Scholar 

  29. Li, G., Liu, T., Pong, T.K.: Peaceman–Rachford splitting for a class of nonconvex optimization problems. Comput. Optim. Appl. 68, 407–436 (2017)

    MathSciNet  MATH  Google Scholar 

  30. Li, G., Pong, T.K.: Douglas–Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems. Math. Program. 159, 371–401 (2016)

    MathSciNet  MATH  Google Scholar 

  31. Li, M., Wu, Z.: Convergence analysis of the generalized splitting methods for a class of nonconvex optimization problems. J Optim. Theory Appl. 183, 535–565 (2019)

    MathSciNet  MATH  Google Scholar 

  32. Lindstrom, S.B., Sims, B., Survey: Sixty Years of Douglas–Rachford (2020). https://arxiv.org/abs/1809.07181?context=math

  33. Lions, P.L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16, 964–979 (1979)

    MathSciNet  MATH  Google Scholar 

  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 Probl. 27, 085004 (2012)

    MathSciNet  MATH  Google Scholar 

  35. Moudafi, A., Thakur, B.S.: Solving proximal split feasibility problems without prior knowledge of operator norms. Optim. Lett. 8, 2099–2110 (2014)

    MathSciNet  MATH  Google Scholar 

  36. Peaceman, D.W., Rachford, H.H.: The numerical solution of parabolic and elliptic differential equations. J. Soc. Ind. Appl. Math. 3, 28–41 (1955)

    MathSciNet  MATH  Google Scholar 

  37. Qu, B., Wang, C., Xiu, N.: Analysis on Newton projection method for the split feasibility problem. Comput. Optim. Appl. 67, 175–199 (2017)

    MathSciNet  MATH  Google Scholar 

  38. Shehu, Y., Iyiola, O.S.: Nonlinear iteration method for proximal split feasibility problems. Math. Method Appl. Sci. 41, 781–802 (2018)

    MathSciNet  MATH  Google Scholar 

  39. Themelis, A., Patrinos, P.: Douglas–Rachford splitting and ADMM for nonconvex optimization: tight convergence results. SIAM J. Optim. 30, 149–181 (2020)

    MathSciNet  MATH  Google Scholar 

  40. Tibshirani, R.: Regression shrinkage and selection via the lasso. J. R. Stat. Soc. Ser. B. Stat. Methodol. 58, 267–288 (1996)

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  42. Wang, D., Wang, X.: A parameterized Douglas–Rachford algorithm. Comput. Optim. Appl. 73, 839–869 (2019)

    MathSciNet  MATH  Google Scholar 

  43. Wang, F.: Polyak’s gradient method for split feasibility problem constrained by level sets. Numer. Algorithms 77, 925–938 (2018)

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  45. 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. Glob. Optim. 73, 849–868 (2019)

    MathSciNet  MATH  Google Scholar 

  46. Yen, L.H., Muu, L.D., Huyen, N.T.T.: An algorithm for a class of split feasibility problems: application to a model in electricity production. Math. Methods Oper. Res. 84, 549–565 (2016)

    MathSciNet  MATH  Google Scholar 

  47. Zhao, J.: Solving split equality fixed-point problem of quasi-nonexpansive mappings without prior knowledge of operators norms. Optimization 64, 2619–2630 (2015)

    MathSciNet  MATH  Google Scholar 

  48. Zhao, J., Yang, Q.: Self-adaptive projection methods for the multiple-sets split feasibility problem. Inverse Probl. 27, 035009 (2011)

    MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

We sincerely thank the anonymous reviewers for their constructive comments and suggestions that greatly improved the manuscript. We would like to thank Professor Yuchao Tang for his valuable help in the program.

Author information

Authors and Affiliations

  1. College of Science, Civil Aviation University of China, Tianjin, 300300, People’s Republic of China

    Qiao-Li Dong & Songnian He

  2. Institute of Mathematics, University of Zurich, 8057, Zurich, Switzerland

    Michael Th. Rassias

  3. Moscow Institute of Physics and Technology, Dolgoprudny, Russia, 141700

    Michael Th. Rassias

Authors
  1. Qiao-Li Dong
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Songnian He
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Michael Th. Rassias
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Qiao-Li Dong.

Additional information

Publisher's Note

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

Fundamental Research Funds for the Central Universities (No. 3122019142)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Dong, QL., He, S. & Rassias, M.T. General splitting methods with linearization for the split feasibility problem. J Glob Optim 79, 813–836 (2021). https://doi.org/10.1007/s10898-020-00963-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-020-00963-3

Keywords

Mathematics Subject Classification

Search

Navigation