[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Extension of the subgradient extragradient algorithm for solving variational inequalities without monotonicity

  • Original Research
  • Published:
Journal of Applied Mathematics and Computing Aims and scope Submit manuscript

Abstract

Two improved subgradient extragradient algorithms are proposed for solving nonmonotone variational inequalities under the nonempty assumption of the solution set of the dual variational inequalities. First, when the mapping is Lipschitz continuous, we propose an improved subgradient extragradient algorithm with self-adaptive step-size (ISEGS for short). In ISEGS, the next iteration point is obtained by projecting sequentially the current iteration point onto two different half-spaces, and only one projection onto the feasible set is required in the process of constructing the half-spaces per iteration. The self-adaptive technique allows us to determine the step-size without using the Lipschitz constant. Second, we extend our algorithm into the case where the mapping is merely continuous. The Armijo line search approach is used to handle the non-Lipschitz continuity of the mapping. The global convergence of both algorithms is established without monotonicity assumption of the mapping. The computational complexity of the two proposed algorithms is analyzed. Some numerical examples are given to show the efficiency of the new algorithms.

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
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

Data availability

The data that support the findings of this study are available from the corresponding author upon reasonable request.

Code availability

The codes that support the findings of this study are available from the corresponding author upon reasonable request.

References

  1. Goldstein, A.A.: Convex programming in Hilbert space. Bull. Amer. Math. Soc. 70, 709–710 (1964)

    Article  MathSciNet  MATH  Google Scholar 

  2. Levitin, E.S., Polyak, B.T.: Constrained minimization methods. USSR Comput. Math. Math. Phys. 6, 1–50 (1966)

    Article  MATH  Google Scholar 

  3. Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control. Optim. 14, 877–898 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  4. Burachik, R.S., Iusem, A.N.: A generalized proximal point algorithm for the variational inequality problem in a Hilbert space. SIAM J. Optim. 8, 197–216 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  5. Korpelevich, G.M.: The extragradient method for finding saddle points and other problems. Matecon. 12, 747–756 (1976)

    MathSciNet  MATH  Google Scholar 

  6. Wang, Y.J., Xiu, N.H., Wang, C.Y.: Unified framework of extragradient-type methods for pseudomonotone variational inequalities. J. Optim. Theory Appl. 111, 641–656 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  7. He, B.S.: A class of projection and contraction methods for monotone variational inequalities. Appl. Math. Optim. 35, 69–76 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  8. Solodov, M.V., Svaiter, B.F.: A new projection method for variational inequality problems. SIAM J. Control. Optim. 37, 765–776 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  9. He, Y.R.: A new double projection algorithm for variational inequalities. J. Comput. Appl. Math. 185, 166–173 (2006)

    Article  MathSciNet  MATH  Google Scholar 

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

  11. Malitsky, Y.: Projected reflected gradient methods for monotone variational inequalities. SIAM J. Optim. 25, 502–520 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  12. Malitsky, Y.: Golden ratio algorithms for variational inequalities. Math. Program. 184, 383–410 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  13. Ye, M.L., He, Y.R.: A double projection method for solving variational inequalities without monotonicity. Comput. Optim. Appl. 60, 141–150 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  14. Brito, A.S., da Cruz Neto, J.X., Lopes, J.O., Oliveira, P.R.: Interior proximal algorithm for quasiconvex programming problems and variational inequalities with linear constraints. J. Optim. Theory Appl. 154, 217–234 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  15. Langenberg, N.: An interior proximal method for a class of quasimonotone variational inequalities. J. Optim. Theory Appl. 155, 902–922 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  16. Liu, H., Yang, J.: Weak convergence of iterative methods for solving quasimonotone variational inequalities. Comput. Optim. Appl. 77, 491–508 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  17. Ogwo, G.N., Izuchukwu, C., Shehu, Y., Mewomo, O.T.: Convergence of relaxed inertial subgradient extragradient methods for quasimonotone variational inequality problems. J. Sci. Comput. 90, 1–35 (2022)

    Article  MathSciNet  MATH  Google Scholar 

  18. Ye, M.L.: An infeasible projection type algorithm for nonmonotone variational inequalities. Numer. Algorithms. 89, 1723–1742 (2022)

    Article  MathSciNet  MATH  Google Scholar 

  19. Konnov, I.V.: Combined relaxation methods for finding equilibrium points and solving related problems. Russ. Math. (Iz VUZ) 37, 44–51 (1993)

    MATH  Google Scholar 

  20. Lei, M., He, Y.R.: An extragradient method for solving variational inequalities without monotonicity. J. Optim. Theory Appl. 188, 432–446 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  21. Van Dinh, B., Manh, H.D., Thanh, T.T.H.: A modified Solodov-Svaiter method for solving nonmonotone variational inequality problems. Numer. Algorithms. 90, 1715–1734 (2022)

    Article  MathSciNet  MATH  Google Scholar 

  22. Thong, D.V., Shehu, Y., Iyiola, O.S.: Weak and strong convergence theorems for solving pseudo-monotone variational inequalities with non-Lipschitz mappings. Numer. Algorithms. 84, 795–823 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  23. Tseng, P.: A modified forward-backward splitting method for maximal monotone mappings. SIAM J. Control. Optim. 38, 431–446 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  24. Huang, Z.J., Zhang, Y.L., He, Y.R.: A class modified projection algorithms for nonmonotone variational inequalities with continuity. Optimization (2024). https://doi.org/10.1080/02331934.2024.2371041

    Article  MATH  Google Scholar 

  25. Huang, K., Zhang, S.: Beyond monotone variational inequalities: Solution methods and iteration complexities. arXiv:2304.04153 (2023)

  26. Lin, T., Jordan, M.I.: Perseus: A simple and optimal high-order method for variational inequalities. Math. Program. (2024). https://doi.org/10.1007/s10107-024-02075-2

    Article  MATH  Google Scholar 

  27. Tuyen, B.T., Manh, H.D., Van Dinh, B.: Inertial algorithms for solving nonmonotone variational inequality problems. Taiwan. J. Math. 28, 397–421 (2024)

    Article  MathSciNet  MATH  Google Scholar 

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

    Book  MATH  Google Scholar 

  29. Denisov, S.V., Semenov, V.V., Chabak, L.M.: Convergence of the modified extragradient method for variational inequalities with non-Lipschitz operators. Cybernet. Syst. Anal. 51, 757–765 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  30. Marcotte, P., Zhu, D.L.: A cutting plane method for solving quasimonotone variational inequalities. Comput. Optim. Appl. 20, 317–324 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  31. Nagurney, A., Zhang, D.: Projected Dynamical Systems and Variational Inequalities with Applications. Springer, New York (1996)

    Book  MATH  Google Scholar 

  32. Tu, K., Zhang, H.B., Xia, F.Q.: A new alternating projection-based prediction-correction method for structured variational inequalities. Optim. Method. Softw. 34, 707–730 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  33. Boyd, S., Boyd, S.P., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)

    Book  MATH  Google Scholar 

Download references

Acknowledgements

The authors thank Professor Haisen Zhang for his valuable suggestions. The authors appreciate the valuable comments of anonymous referees which helped to improve the quality of this paper.

Funding

The first two authors are supported by the National Natural Science Foundation of China (No. 12071324).

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, Sichuan Normal University, Chengdu, 610066, Sichuan, People’s Republic of China

    Jiaxin Chen, Zunjie Huang & Yongle Zhang

Authors
  1. Jiaxin Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Zunjie Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yongle Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yongle Zhang.

Ethics declarations

Conflict of interest

The authors declare no Conflict of interest.

Consent for publication

Not applicable.

Ethics approval

Not applicable.

Additional information

Publisher's Note

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

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chen, J., Huang, Z. & Zhang, Y. Extension of the subgradient extragradient algorithm for solving variational inequalities without monotonicity. J. Appl. Math. Comput. 71, 103–131 (2025). https://doi.org/10.1007/s12190-024-02219-9

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12190-024-02219-9

Keywords