Skip to main content
SpringerLink
Log in

A new class of hybrid extragradient algorithms for solving quasi-equilibrium problems

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

Abstract

Generalized Nash equilibrium problems are important examples of quasi-equilibrium problems. The aim of this paper is to study a general class of algorithms for solving such problems. The method is a hybrid extragradient method whose second step consists in finding a descent direction for the distance function to the solution set. This is done thanks to a linesearch. Two descent directions are studied and for each one several steplengths are proposed to obtain the next iterate. A general convergence theorem applicable to each algorithm of the class is presented. It is obtained under weak assumptions: the pseudomonotonicity of the equilibrium function and the continuity of the multivalued mapping defining the constraint set of the quasi-equilibrium problem. Finally some preliminary numerical results are displayed to show the behavior of each algorithm of the class on generalized Nash equilibrium problems.

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. Bensoussan A.: Points de Nash dans le cas de fonctionnelles quadratiques et jeux différentiels linéaires à N personnes. SIAM J. Control 12, 460–499 (1974)

    Article  Google Scholar 

  2. Blum E., Oettli W.: From optimization and variational inequalities to equilibrium problems. Math. Stud. 63, 123–145 (1994)

    Google Scholar 

  3. Chinchuluun, A., Pardalos, P.M., Migdalas, A., Pitsoulis, L. (eds): Pareto Optimality, Game Theory and Equilibria. Springer, New York (2008)

    Google Scholar 

  4. Facchinei F., Kanzow C.: Generalized Nash equilibrium problems. Ann. Oper. Res. 175, 177–211 (2010)

    Article  Google Scholar 

  5. Facchinei F., Pang J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003)

    Google Scholar 

  6. Fukushima M.: A class of gap functions for quasi-variational inequality problems. J. Ind. Manag. Optim. 3, 165–171 (2007)

    Article  Google Scholar 

  7. Gianessi, F., Maugeri, A., Pardalos, P.M. (eds): Equilibrium Problems: Nonsmooth Optimization and Variational Inequality Models. Kluwer, New York (2002)

    Google Scholar 

  8. Harker P.T.: Generalized Nash games and quasi-variational inequalities. Eur. J. Oper. Res. 54, 81–94 (1991)

    Article  Google Scholar 

  9. Iusem A.N., Svaiter B.F.: A variant of Korpelevich’s method for variational inequalities with a new search strategy. Optimization 42, 309–321 (1997)

    Article  Google Scholar 

  10. Khobotov E.N.: Modification of the extragradient method for solving variational inequalities and certain optimization problems. USSR Comput. Math. Phys. 27, 120–127 (1987)

    Article  Google Scholar 

  11. Konnov I.V.: Equilibrium Models and Variational Inequalities. Mathematics in Science and Engineering. Elsevier, Amsterdam (2007)

    Google Scholar 

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

    Google Scholar 

  13. Kubota K., Fukushima M.: Gap function approach to the generalized Nash equilibrium problem. J. Optim. Theory Appl. 144, 511–531 (2010)

    Article  Google Scholar 

  14. Noor M.A.: A modified extragradient method for general monotone variational inequalities. Comput. Math. Appl. 38, 19–24 (1999)

    Article  Google Scholar 

  15. Noor M.A.: On merit functions for quasivariational inequalities. J. Math. Inequal. 1, 259–268 (2007)

    Article  Google Scholar 

  16. Palomar, D.P., Eldar, Y.C. (eds): Convex Optimization in Signal Processing and Communications. Cambridge University Press, Cambridge (2010)

    Google Scholar 

  17. Pang J.-S., Fukushima M.: Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games. Comput. Manag. Sci. 2, 21–56 (2005)

    Article  Google Scholar 

  18. Pang J.-S., Fukushima M.: Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games. Erratum. Comput. Manag. Sci. 6, 373–375 (2009)

    Article  Google Scholar 

  19. Pardalos, P.M., Rassias, T.M., Khan, A.A. (eds): Nonlinear Analysis and Variational Problems. Springer, New York (2010)

    Google Scholar 

  20. Rockafellar R.T.: Convex Analysis. Princeton University Press, Princeton (1970)

    Google Scholar 

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

    Article  Google Scholar 

  22. Smeers, Y., Oggioni, G., Allevi, E., Schaible, S.: Generalized Nash equilibrium and market coupling in the European power system. EPRG Working Paper 1016, Cambridge Working Paper in Economics 1034 (2010)

  23. Taji, K.: On gap functions for quasi-variational inequalities. Abstract and Applied Analysis 2008, Article ID 531361, 7 pages (2008)

  24. Tran D.Q., Le Dung M., Nguyen V.H.: Extragradient algorithms extended to equilibrium problems. Optimization 57, 749–776 (2008)

    Article  Google Scholar 

  25. von Heusinger, A.: Numerical Methods for the Solution of the Generalized Nash Equilibrium Problem. PhD Thesis, University of Wuerzburg, Germany (2009)

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

    Article  Google Scholar 

  27. Wang Y., Xiu N., Wang C.: A new version of extragradient method for variational inequality problems. Comput. Math. Appl. 42, 969–979 (2001)

    Article  Google Scholar 

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

    Article  Google Scholar 

  29. Xiu N., Wang Y., Zhang X.: Modified fixed-point equations and related iterative methods for variational inequalities. Comput. Math. Appl. 47, 913–920 (2004)

    Article  Google Scholar 

  30. Xiu N., Zhang J.: Some recent advances in projection-type methods for variational inequalities. J. Comput. Appl. Math. 152, 559–585 (2003)

    Article  Google Scholar 

  31. Zhang J., Qu B., Xiu N.: Some projection-like methods for the generalized Nash equilibria. Comput. Optim. Appl. 45, 89–109 (2010)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute for Computational Science and Technology, Ho Chi Minh City, Vietnam

    Jean Jacques Strodiot, Thi Thu Van Nguyen & Van Hien Nguyen

  2. Department of Mathematics, University of Namur, Namur, Belgium

    Jean Jacques Strodiot & Van Hien Nguyen

Authors
  1. Jean Jacques Strodiot
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Thi Thu Van Nguyen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Van Hien Nguyen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jean Jacques Strodiot.

Additional information

This research was supported by the Institute for Computational Science and Technology at Ho Chi Minh City, Vietnam (ICST HCMC).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Strodiot, J.J., Nguyen, T.T.V. & Nguyen, V.H. A new class of hybrid extragradient algorithms for solving quasi-equilibrium problems. J Glob Optim 56, 373–397 (2013). https://doi.org/10.1007/s10898-011-9814-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-011-9814-y

Keywords

Mathematics Subject Classification (2000)

Search

Navigation