×
Han, Deren; Zhang, Hongchao; Qian, Gang; Xu, Lingling

An improved two-step method for solving generalized Nash equilibrium problems. (English) Zbl 1252.90081

Eur. J. Oper. Res. 216, No. 3, 613-623 (2012).
Summary: The generalized Nash equilibrium problem (GNEP) is a noncooperative game in which the strategy set of each player, as well as his pay-off function, depend on the rival players strategies. As a generalization of the standard Nash equilibrium problem (NEP), the GNEP has recently drawn much attention due to its capability of modeling a number of interesting conflict situations in, for example, an electricity market and an international pollution control. In this paper, we propose an improved two-step (a prediction step and a correction step) method for solving the quasi-variational inequality (QVI) formulation of the GNEP. Per iteration, we first do a projection onto the feasible set defined by the current iterate (prediction) to get a trial point; then, we perform another projection step (correction) to obtain the new iterate. Under certain assumptions, we prove the global convergence of the new algorithm. We also present some numerical results to illustrate the ability of our method, which indicate that our method outperforms the most recent projection-like methods of J. Zhang, B. Qu and N. Xiu [Comput. Optim. Appl. 45, No. 1, 89–109 (2010; Zbl 1198.91026)].

Cited in 17 Documents

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
91A10 Noncooperative games
90C25 Convex programming

Keywords:

generalized Nash equilibrium; quasi-variational inequality problems; two-step methods; projection methods

Citations:

Zbl 1198.91026
PDF BibTeX XML Cite
\textit{D. Han} et al., Eur. J. Oper. Res. 216, No. 3, 613--623 (2012; Zbl 1252.90081)
Full Text: DOI

References:

[1] Arrow, K.; Debreu, G., Existence of an equilibrium for a competitive economy, Econometrica, 22, 265-290 (1954) · Zbl 0055.38007
[2] Bensoussan, A., Points de Nash dans le cas de fonctionnelles quadratiques et jeux differentiels linéaires a \(N\) personnes, SIAM Journal on Control, 12, 460-499 (1974) · Zbl 0254.90066
[3] Bertsekas, D.; Gafni, E., Projection method for variational inequalities with applications to the traffic assignment problem, Mathematical Programming Study, 17, 139-159 (1987)
[4] Bertsekas, D.; Tsitsiklis, J., Parallel and Distributed Computation: Numerical Methods (1989), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0743.65107
[5] Breton, M.; Zaccour, G.; Zahaf, M., A game-theoretic formulation of joint implementation of environmental projects, European Journal of Operational Research, 168, 221-239 (2006) · Zbl 1131.91370
[6] Contreras, J.; Klusch, M.; Krawczyk, J., Numerical solutions to Nash-Cournot equilibria in coupled constraint electricity markets, IEEE Transactions on Power Systems, 19, 195-206 (2004)
[7] Debreu, G., A social equilibrium existence theorem, Proceedings of the National Academy of Sciences of the United States, 38, 886-893 (1952) · Zbl 0047.38804
[8] Facchinei, F.; Kanzow, C., Penalty methods for the solution of generalized Nash equilibrium problems, SIAM Journal on Optimization, 20, 2228-2253 (2010) · Zbl 1211.90228
[9] Facchinei, F.; Pang, J., Finite-Dimensional Variational Inequalities and Complementarity Problems, vols. I and II. (2003), Springer Verlag: Springer Verlag Berlin
[10] Facchinei, F.; Fischer, A.; Piccialli, V., On generalized Nash games and variational inequalities, Operations Research Letters, 35, 159-164 (2007) · Zbl 1303.91020
[11] Facchinei, F.; Fischer, A.; Piccialli, V., Generalized Nash equilibrium problems and Newton methods, Mathematical Programming, 117, 163-194 (2009) · Zbl 1166.90015
[12] Ferris, M.; Pang, J., Engineering and economic applications of complementarity problems, SIAM Review, 39, 669-713 (1997) · Zbl 0891.90158
[13] Fukushima, M., Restricted generalized Nash equilibria and controlled penalty algorithm, Computational Management Science, 8, 201-218 (2011) · Zbl 1253.91010
[14] Goldstein, A., Convex programming in Hilbert space, Bulletin of the American Mathematical Society, 70, 709-710 (1964) · Zbl 0142.17101
[15] Han, D.; Lo, H., Two new self-adaptive projection methods for variational inequality problems, Computers and Mathematics with Applications, 43, 1529-1537 (2002) · Zbl 1012.65064
[16] Han, D.; Sun, W., A new modified Goldstein-Levitin-Polyak projection method for variational inequality problems, Computers and Mathematics with Applications, 47, 1817-1825 (2004) · Zbl 1057.49011
[17] Harker, P., Generalized Nash games and quasi-variational inequalities, European Journal of Operational Research, 54, 81-94 (1991) · Zbl 0754.90070
[18] He, B., A class of projection and contraction methods for monotone variational inequalities, Applied Mathematics and Optimization, 35, 69-76 (1997) · Zbl 0865.90119
[19] He, B.; Yang, H.; Meng, Q.; Han, D., Modified Goldstein-Levitin-Polyak projection method for asymmetric strongly monotone variational inequalities, Journal of Optimization Theory and Applications, 112, 129-143 (2002) · Zbl 0998.65066
[20] Hobbs, B.; Pang, J., Nash-Cournot equilibrium in electric power markets with piecewise linear demand functions and joint constraints, Operations Research, 55, 113-127 (2007) · Zbl 1167.91356
[22] Khobotov, E., Modification of the extragradient method for solving variational inequalities and certain optimization problems, USSR, Computational Mathematics and Mathematical Physics, 27, 120-127 (1987) · Zbl 0665.90078
[23] Kocvara, M.; Outrata, J., On a class of quasi-variational inequalities, Optimization Methods and Software, 5, 275-295 (1995)
[24] Korpelevich, G., The extragradient method for finding saddle points and other problems, Matecon, 12, 747-756 (1976) · Zbl 0342.90044
[25] Krawczyk, J., Numerical solutions to coupled-constraint (or generalised Nash) equilibrium problems, Computational Management Science, 4, 183-204 (2007) · Zbl 1134.91303
[26] Krawczyk, J.; Uryasev, S., Relaxation algorithms to find Nash equilibria with economic applications, Environmental Modeling and Assessment, 5, 63-73 (2000)
[27] Kubota, K.; Fukushima, M., Gap function approach to the generalized Nash equilibrium problem, Journal of Optimization, Theory and Applications, 144, 511-531 (2010) · Zbl 1188.91021
[28] Levitin, E.; Polyak, B., Constrained minimization problems, USSR. Computational Mathematics and Mathematical Physics, 6, 1-50 (1966)
[29] Nabetani, K.; Tseng, P.; Fukushima, M., Parametrized variational inequality approaches to generalized Nash equilibrium problems with shared constraints, Computational Optimization and Applications, 48, 423-452 (2011) · Zbl 1220.90136
[30] Nagurney, A., Network Economics: A Variational Inequality Approach (1999), Kluwer Academics Publishers: Kluwer Academics Publishers Dordrecht, MA
[31] Noor, M., Some recent advances in variational inequalities, Part I: Basic concepts, New Zealand Journal of Mathematics, 26, 53-80 (1997) · Zbl 0886.49004
[32] Outrata, J.; Zowe, J., A Newton method for a class of quasi-variational inequalities, Computational Optimization and Applications, 4, 5-21 (1995) · Zbl 0827.49007
[33] Pang, J.; Fukushima, M., Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games, Computational Management Science, 2, 21-56 (2005) · Zbl 1115.90059
[34] Pang, J.; Fukushima, M., Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games, Computational Management Science, 6, 373-375 (2009) · Zbl 1168.90618
[35] Pang, J.; Scutari, G.; Facchinei, F.; Wang, C., Distributed power allocation with rate constraints in Gaussian parallel interference channels, IEEE Transaction on Information Theory, 54, 3471-3489 (2008) · Zbl 1329.94006
[36] Panicucci, B.; Pappalardo, M.; Passacantando, M., On solving generalized Nash equilibrium problems via optimization, Optimization Letters, 3, 419-435 (2009) · Zbl 1187.91011
[37] Robinson, S., Shadow prices for measures of effectiveness. I: Linear model, Operations Research, 41, 518-535 (1993) · Zbl 0800.90666
[38] Robinson, S., Shadow prices for measures of effectiveness. II: General model, Operations Research, 41, 536-548 (1993) · Zbl 0800.90667
[39] Rosen, J., Existence and uniqueness of equilibrium points for concave N-person games, Econometrica, 33, 520-534 (1965) · Zbl 0142.17603
[40] Solodov, M.; Svaiter, B., A new projection method for variational inequality problems, SIAM Journal on Control and Optimization, 37, 765-776 (1999) · Zbl 0959.49007
[41] Solodov, M.; Tseng, P., Modified projection-type methods for monotone variational inequalities, SIAM Journal on Control and Optimization, 34, 1814-1830 (1996) · Zbl 0866.49018
[42] Sun, D., A class of iterative methods for solving nonlinear projection equations, Journal of Optimization Theory and Applications, 91, 123-140 (1996) · Zbl 0871.90091
[43] Uryasev, S.; Rubinstein, R., On relaxation algorithms in computation of noncooperative equilibria, IEEE Transaction on Automatic Control, 39, 1263-1267 (1994) · Zbl 0811.90117
[44] von Heusinger, A.; Kanzow, C., Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-type functions, Computational Optimization and Applications, 43, 353-377 (2009) · Zbl 1170.90495
[45] von Heusinger, A.; Fukushima, M.; Kanzow, C., Newton’s method for computing a normalized equilibrium in the generalized Nash game through fixed point formulation, Mathematical Programming (2010)
[46] Wang, Y.; Xiu, N.; Wang, C., A new version of extragradient method for variational inequality problems, Computers and Mathematics with Applications, 42, 969-979 (2001) · Zbl 0993.49005
[47] Wei, J.; Smeers, Y., Spatial oligopolistic electricity models with Cournot generators and regulated transmission prices, Operations Research, 47, 102-112 (1999) · Zbl 1175.91080
[48] Yang, H.; Huang, H., Mathematical and Economic Theory of Road Pricing (2005), Elsevier Science
[49] Zarantonello, E., Projections on convex sets in Hilbert space and spectral theory, (Zarantonello, E. H., Contributions to Nonlinear Functional Analysis (1971), Academic Press: Academic Press New York) · Zbl 0463.47042
[50] Zhang, J.; Qu, B.; Xiu, N., Some projection-like methods for the generalized Nash equilibria, Computational Optimization and Applications, 45, 89-109 (2010) · Zbl 1198.91026
[51] Zhu, T.; Yu, Z., A simple proof for some important properties of the projection mapping, Mathematical Inequalities and Applications, 7, 453-456 (2004) · Zbl 1086.49007
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.