×

A new class of hybrid extragradient algorithms for solving quasi-equilibrium problems. (English) Zbl 1269.49013

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

MSC:

49J40 Variational inequalities
65K10 Numerical optimization and variational techniques
91A12 Cooperative games
PDFBibTeX XMLCite
Full Text: DOI

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) · Zbl 0254.90066 · doi:10.1137/0312037
[2] Blum E., Oettli W.: From optimization and variational inequalities to equilibrium problems. Math. Stud. 63, 123-145 (1994) · Zbl 0888.49007
[3] Chinchuluun, A., Pardalos, P.M., Migdalas, A., Pitsoulis, L. (eds): Pareto Optimality, Game Theory and Equilibria. Springer, New York (2008) · Zbl 1143.91004
[4] Facchinei F., Kanzow C.: Generalized Nash equilibrium problems. Ann. Oper. Res. 175, 177-211 (2010) · Zbl 1185.91016 · doi:10.1007/s10479-009-0653-x
[5] Facchinei F., Pang J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003) · Zbl 1062.90002
[6] Fukushima M.: A class of gap functions for quasi-variational inequality problems. J. Ind. Manag. Optim. 3, 165-171 (2007) · Zbl 1170.90487 · doi:10.3934/jimo.2007.3.165
[7] Gianessi, F., Maugeri, A., Pardalos, P.M. (eds): Equilibrium Problems: Nonsmooth Optimization and Variational Inequality Models. Kluwer, New York (2002)
[8] Harker P.T.: Generalized Nash games and quasi-variational inequalities. Eur. J. Oper. Res. 54, 81-94 (1991) · Zbl 0754.90070 · doi:10.1016/0377-2217(91)90325-P
[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) · Zbl 0891.90135 · doi:10.1080/02331939708844365
[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) · Zbl 0665.90078 · doi:10.1016/0041-5553(87)90058-9
[11] Konnov I.V.: Equilibrium Models and Variational Inequalities. Mathematics in Science and Engineering. Elsevier, Amsterdam (2007) · Zbl 1140.91056
[12] Korpelevich G.M.: The extragradient method for finding saddle points and other problems. Matekon 12, 747-756 (1976) · Zbl 0342.90044
[13] Kubota K., Fukushima M.: Gap function approach to the generalized Nash equilibrium problem. J. Optim. Theory Appl. 144, 511-531 (2010) · Zbl 1188.91021 · doi:10.1007/s10957-009-9614-4
[14] Noor M.A.: A modified extragradient method for general monotone variational inequalities. Comput. Math. Appl. 38, 19-24 (1999) · Zbl 0939.47055 · doi:10.1016/S0898-1221(99)00164-9
[15] Noor M.A.: On merit functions for quasivariational inequalities. J. Math. Inequal. 1, 259-268 (2007) · Zbl 1129.49015 · doi:10.7153/jmi-01-23
[16] Palomar, D.P., Eldar, Y.C. (eds): Convex Optimization in Signal Processing and Communications. Cambridge University Press, Cambridge (2010) · Zbl 1200.90009
[17] Pang J.-S., Fukushima M.: Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games. Comput. Manag. Sci. 2, 21-56 (2005) · Zbl 1115.90059 · doi:10.1007/s10287-004-0010-0
[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) · Zbl 1168.90618 · doi:10.1007/s10287-009-0093-8
[19] Pardalos, P.M., Rassias, T.M., Khan, A.A. (eds): Nonlinear Analysis and Variational Problems. Springer, New York (2010) · Zbl 1178.49001
[20] Rockafellar R.T.: Convex Analysis. Princeton University Press, Princeton (1970) · Zbl 0193.18401
[21] Solodov M.V., Svaiter B.F.: A new projection method for variational inequality problems. SIAM J. Control Optim. 37, 765-776 (1999) · Zbl 0959.49007 · doi:10.1137/S0363012997317475
[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) · Zbl 1332.91082
[23] Taji, K.: On gap functions for quasi-variational inequalities. Abstract and Applied Analysis 2008, Article ID 531361, 7 pages (2008) · Zbl 1357.49046
[24] Tran D.Q., Le Dung M., Nguyen V.H.: Extragradient algorithms extended to equilibrium problems. Optimization 57, 749-776 (2008) · Zbl 1152.90564 · doi:10.1080/02331930601122876
[25] von Heusinger, A.: Numerical Methods for the Solution of the Generalized Nash Equilibrium Problem. PhD Thesis, University of Wuerzburg, Germany (2009) · Zbl 1170.90495
[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) · Zbl 1039.49014 · doi:10.1023/A:1012606212823
[27] Wang Y., Xiu N., Wang C.: A new version of extragradient method for variational inequality problems. Comput. Math. Appl. 42, 969-979 (2001) · Zbl 0993.49005 · doi:10.1016/S0898-1221(01)00213-9
[28] Wei J.Y., Smeers Y.: Spatial oligopolistic electricity models with Cournot generators and regulated transmission prices. Oper. Res. 47, 102-112 (1999) · Zbl 1175.91080 · doi:10.1287/opre.47.1.102
[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) · Zbl 1057.49013 · doi:10.1016/S0898-1221(04)90075-2
[30] Xiu N., Zhang J.: Some recent advances in projection-type methods for variational inequalities. J. Comput. Appl. Math. 152, 559-585 (2003) · Zbl 1018.65083 · doi:10.1016/S0377-0427(02)00730-6
[31] Zhang J., Qu B., Xiu N.: Some projection-like methods for the generalized Nash equilibria. Comput. Optim. Appl. 45, 89-109 (2010) · Zbl 1198.91026 · doi:10.1007/s10589-008-9173-x
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.