广义Nash均衡问题的算法及应用研究
|
摘要
本文主要研究广义Nash均衡问题的算法及应用.文中,我们给出了求解该问题的两种算法并对其应用进行了研究.全文共分为四章.
第一章是序言,主要介绍了广义Nash均衡问题的研究现状以及本文的主要研究工作.
第二章我们给出了求解广义Nash均衡问题的一种混合算法.首先,我们将广义Nash均衡问题转化为一个无约束最优化问题,然后给出一种混合算法来求解这个无约束优化问题,并证明了该算法的全局收敛性.
第三章研究了拟变分不等式问题的一种投影算法及其收敛性.由于广义Nash均衡问题可等价转化为一个拟变分不等式问题,因此,该算法也可用于求解广义Nash均衡问题.与文献[18]Noor的算法相比,该算法的优点在于:修正了Noor的算法用于解决一般的拟变分不等式问题,适用范围更广,在更弱的条件下保证了算法的收敛性,而且迭代公式的结构也更为简易.
第四章主要对广义Nash均衡问题的应用进行研究.介绍了广义Nash均衡问题在经济、网络切换、环境污染治理、以及交通网络等模型中的应用.
In this diss(?)rtation, wo mainly investigate the algorithms and applications of the generalized Nash equilibrium problem. We design two methods for solving the generalized Nash equilibrium problem(GNEP). Also the applications of it are listed in this paper. Four main chapters are included as follows:
Chapter 1 is the introduction. We describe the research situations of the generalized Nash equilibrium problem. The main contributions of this paper are also stated briefly.
In Chapter 2,we present a new hybrid method for GNEP . At first, we reformulate generalized Nash equilibrium problem into an unconstrained optimization problem ,and then propose a new method for the unconstrained optimization problems and prove the global convergence.
In Chapter 3, we design a projection algorithm for quasi-variational Inequalities and prove the global convergence of the algorithms.Due to generalized Nash equilibrium problem can be reformulated into a quasi-variational Inequality,so the method also can be applied to solve the generalized Nash equilibrium. Comparing with Noor's methods, the superiority of this method is that the application scope of it is more broader.Under a weaker condition the global convergence is guaranteed.And the iterative form is relatively simple.
In Chapter 4,we mainly investigate the applications of the generalized Nash equilibrium problem. We introduce the specific applications of the generalized Nash equilibrium problem in abstract economy by Arrow and Dcbrcu,intcrnctswitching,environmental pollution control , the traffic internet switching and so on.
第一章是序言,主要介绍了广义Nash均衡问题的研究现状以及本文的主要研究工作.
第二章我们给出了求解广义Nash均衡问题的一种混合算法.首先,我们将广义Nash均衡问题转化为一个无约束最优化问题,然后给出一种混合算法来求解这个无约束优化问题,并证明了该算法的全局收敛性.
第三章研究了拟变分不等式问题的一种投影算法及其收敛性.由于广义Nash均衡问题可等价转化为一个拟变分不等式问题,因此,该算法也可用于求解广义Nash均衡问题.与文献[18]Noor的算法相比,该算法的优点在于:修正了Noor的算法用于解决一般的拟变分不等式问题,适用范围更广,在更弱的条件下保证了算法的收敛性,而且迭代公式的结构也更为简易.
第四章主要对广义Nash均衡问题的应用进行研究.介绍了广义Nash均衡问题在经济、网络切换、环境污染治理、以及交通网络等模型中的应用.
In this diss(?)rtation, wo mainly investigate the algorithms and applications of the generalized Nash equilibrium problem. We design two methods for solving the generalized Nash equilibrium problem(GNEP). Also the applications of it are listed in this paper. Four main chapters are included as follows:
Chapter 1 is the introduction. We describe the research situations of the generalized Nash equilibrium problem. The main contributions of this paper are also stated briefly.
In Chapter 2,we present a new hybrid method for GNEP . At first, we reformulate generalized Nash equilibrium problem into an unconstrained optimization problem ,and then propose a new method for the unconstrained optimization problems and prove the global convergence.
In Chapter 3, we design a projection algorithm for quasi-variational Inequalities and prove the global convergence of the algorithms.Due to generalized Nash equilibrium problem can be reformulated into a quasi-variational Inequality,so the method also can be applied to solve the generalized Nash equilibrium. Comparing with Noor's methods, the superiority of this method is that the application scope of it is more broader.Under a weaker condition the global convergence is guaranteed.And the iterative form is relatively simple.
In Chapter 4,we mainly investigate the applications of the generalized Nash equilibrium problem. We introduce the specific applications of the generalized Nash equilibrium problem in abstract economy by Arrow and Dcbrcu,intcrnctswitching,environmental pollution control , the traffic internet switching and so on.
引文
[1]Friedman J..Game Theory with Applications to Economics[M].Oxford University Press,1990.
[2]Harker P.T..Generalized Nash games and quasi-variational inequalities[J].European Journal of Operational Research,1991,54:81-94.
[3]Josef Cach.Solution set in a special case of generalized nash equilibrium games [J].Kybernetika,2001,37(1):21-37.
[4]Facchinei F.,Fischer A.,Piccialli V..On generalized Nash games and Variational Inequalities[J].Oper.Res.Lett,2007,35:159-164.
[5]Heusinger A.Von,Kanzow C..Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-Type functions[J].Preprint 269,Institute of Mathematics,University of Wurzburg,Germany,July 2006.
[6]Jian Yu,Hui Yang,chao Yu..Well-posed ky Fans Point,quasi-variational inequality and Nash equilibrium problems[J].Nonlinear Analysis,2007,66;777-790.
[7]Facchinei F.,Fischer A.,Piccialli V..Generalized Nash equilibrium problems and Newton methods[J].Technical Report,Department of Computer and System Sciences"A.Ruberti",Universita di Roma"La Sapienza",Rome,Italy,February 2007.
[8]Anna von Heusinger,Christian Kanzow.SC~1 Optimization reformulations of the Generalized Nash Equilibrium Problem[J].Technical Report,Institute of Mathematics,University of Wurzburg,Germany 2007.
[9]Fukushima M..A class of gap functions for quasi-variational inequality problems[J].Journal of Operational Industrial and Management Optimization,2007,3(2):165-171.
[10]Pang J.S.,Fukushima M..Quasi-variational inequalities,generalized Nash equibria and multi-leader-follower games.Computational Management Science,2005,2:21-56.
[11]Pang J.S..Computing generalized Nash equilibria,Mathematical Programming,Series A,in revision.
[12]Bensoussan,A..Points de Nash dans le cas de fontionnelles quadratiques et jeux differentiels lineaires a N persons[J].SIAM Journal of Control,1974,12:460-499.
[13]Robinson,S.M..Shadow prices for measures of effectiveness.I.Linear model.[J].Operations Reasearch,1993,41:518-535.
[14]Robinson,S.M..Shadow prices for measures of effectiveness.Ⅱ.General model[J].Operations Reasearch,1993,41:536-548.
[15]Kocara,M,Outrata,J.V..On a class of quasi-variational inequalities[J].Optimization Methods and Software.Optim.,1995,5:275-295.
[16]Wei,J.Y.Smeers,Y..Spatial oligopolistic electricity models with Coournot generators and regulated transmission prices[J].Operations Research,1999,47:102-112.
[17]Pang,J.S..Computing generalized Nash equilibria,manuscript,Department of Mathematical sciences[J].The Johns Hopkins University,2002
[18]Muhammad Aslam Noor.An Iterative Scheme for a class of Quasi Variational Inequalities[J].J.Math.Anal.Appl,1985,463-467.
[19]Biao Qu,Xiu N H.A note on the CQ algorithm for the split feasibility problem[J].Inverse Problem,2005,21:1655-1665.
[20]王宜举,修乃华.非线性规划理论与算法[M].陕西.陕西科学技术出版社,2004.
[21]Muhammad Aslam Noor.On Merit functions for quasivariational inequalities[J].Journal of Mathematical Inequalities,2007,1(2):259-268.
[22]Arrow K.J.,Debreu G..Existence of an equilibrium for a competitive economy[J].Econometria,1954,22:265-290.
[23]Breton M.,Zaccour G.,Zahaf M..A game-theoretic formulation of joint implemenration of enviromental projects[J].Eur.J.Oper.Res,2005,168:221-239.
[24]周晶,徐晏.公共交通网络系统的经营模型模型[J].系统工程学报,2001,16(4):261-267.
[25]Pang J.,Scutari G.,Facchinei F..Distributed power allocation with rate containts in Gaussian frequency-selective interference channels[D[.DIS Technical Report 05-07,"Sapienza" Universita di Rome,Italt,2007.
[26]Mu,L.L.Ma,J.H.Game theory analysis of price decision in real estate industry.[J].International Journal of Nonlinear science,2007,3(2):83-97.
[27]Nash,J.F.Equilibrium points in n-person games[J].Proceedings of National Academy of Sciences,1950,U.S.A.36:48-49.
[28]袁亚湘.非线性规划数值方法[M].上海科学技术出版社,1993.
[29]Facchinei F.,Pang J.S..Finite-Dimensional Variational inequality and complementarity problems[J].Springer-Verlag,New York,2003.
[30]P.T.Harker.A Variational inequality approach for the determination of oligopolistic market equilibrium.Mathematical Programming,1984,30:105-111.
[31]Chan D.,Pang J.S..The generalized quasi-variational inequality problem[J].Mathematics of Operations Research,1982,7:211-222.
[32]Pang J.S.,Yao J.C..On generalizational of a normal map and equation[J].SIAM J.on Control and Opetimization,1995,33:168-184.
[33]Yao J.C.,The generalized quasi-variational inequality problem with applications[J].J.Of Mathematical Analysis and Applications,1991,158:139-160.
[34]Baiocchi C.,Capelo A..Variational and quasi-variational inequalities[M].J.Wiley and Sons,New York,1984.
[35]Kocvara M.,Outrata J.V..On a class of quasi-variational inequalities[J].Optimization methods and Software,1995,5:275-295.
[36]Outrata J.V.,Zowe J.,A newton method for a class of quasi-variational inequalities[J].Computational Optimization and applications,1995,4:5-21.
[37]Noor M.A..Mixed quasi-variational inequalities[J].Appl.Math.Comput.,2003,146:553-578.
[38]Noor M.A..Implicit dynamical systems for quasi-variational inequalities[J].Appl.Math.Comput,2002,134:69-81.
[39]J.B.Rosen.Existence and uniqueness of equilibrium point for concave n-person games[J].Econometrica,1965,33:520-534.
[2]Harker P.T..Generalized Nash games and quasi-variational inequalities[J].European Journal of Operational Research,1991,54:81-94.
[3]Josef Cach.Solution set in a special case of generalized nash equilibrium games [J].Kybernetika,2001,37(1):21-37.
[4]Facchinei F.,Fischer A.,Piccialli V..On generalized Nash games and Variational Inequalities[J].Oper.Res.Lett,2007,35:159-164.
[5]Heusinger A.Von,Kanzow C..Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-Type functions[J].Preprint 269,Institute of Mathematics,University of Wurzburg,Germany,July 2006.
[6]Jian Yu,Hui Yang,chao Yu..Well-posed ky Fans Point,quasi-variational inequality and Nash equilibrium problems[J].Nonlinear Analysis,2007,66;777-790.
[7]Facchinei F.,Fischer A.,Piccialli V..Generalized Nash equilibrium problems and Newton methods[J].Technical Report,Department of Computer and System Sciences"A.Ruberti",Universita di Roma"La Sapienza",Rome,Italy,February 2007.
[8]Anna von Heusinger,Christian Kanzow.SC~1 Optimization reformulations of the Generalized Nash Equilibrium Problem[J].Technical Report,Institute of Mathematics,University of Wurzburg,Germany 2007.
[9]Fukushima M..A class of gap functions for quasi-variational inequality problems[J].Journal of Operational Industrial and Management Optimization,2007,3(2):165-171.
[10]Pang J.S.,Fukushima M..Quasi-variational inequalities,generalized Nash equibria and multi-leader-follower games.Computational Management Science,2005,2:21-56.
[11]Pang J.S..Computing generalized Nash equilibria,Mathematical Programming,Series A,in revision.
[12]Bensoussan,A..Points de Nash dans le cas de fontionnelles quadratiques et jeux differentiels lineaires a N persons[J].SIAM Journal of Control,1974,12:460-499.
[13]Robinson,S.M..Shadow prices for measures of effectiveness.I.Linear model.[J].Operations Reasearch,1993,41:518-535.
[14]Robinson,S.M..Shadow prices for measures of effectiveness.Ⅱ.General model[J].Operations Reasearch,1993,41:536-548.
[15]Kocara,M,Outrata,J.V..On a class of quasi-variational inequalities[J].Optimization Methods and Software.Optim.,1995,5:275-295.
[16]Wei,J.Y.Smeers,Y..Spatial oligopolistic electricity models with Coournot generators and regulated transmission prices[J].Operations Research,1999,47:102-112.
[17]Pang,J.S..Computing generalized Nash equilibria,manuscript,Department of Mathematical sciences[J].The Johns Hopkins University,2002
[18]Muhammad Aslam Noor.An Iterative Scheme for a class of Quasi Variational Inequalities[J].J.Math.Anal.Appl,1985,463-467.
[19]Biao Qu,Xiu N H.A note on the CQ algorithm for the split feasibility problem[J].Inverse Problem,2005,21:1655-1665.
[20]王宜举,修乃华.非线性规划理论与算法[M].陕西.陕西科学技术出版社,2004.
[21]Muhammad Aslam Noor.On Merit functions for quasivariational inequalities[J].Journal of Mathematical Inequalities,2007,1(2):259-268.
[22]Arrow K.J.,Debreu G..Existence of an equilibrium for a competitive economy[J].Econometria,1954,22:265-290.
[23]Breton M.,Zaccour G.,Zahaf M..A game-theoretic formulation of joint implemenration of enviromental projects[J].Eur.J.Oper.Res,2005,168:221-239.
[24]周晶,徐晏.公共交通网络系统的经营模型模型[J].系统工程学报,2001,16(4):261-267.
[25]Pang J.,Scutari G.,Facchinei F..Distributed power allocation with rate containts in Gaussian frequency-selective interference channels[D[.DIS Technical Report 05-07,"Sapienza" Universita di Rome,Italt,2007.
[26]Mu,L.L.Ma,J.H.Game theory analysis of price decision in real estate industry.[J].International Journal of Nonlinear science,2007,3(2):83-97.
[27]Nash,J.F.Equilibrium points in n-person games[J].Proceedings of National Academy of Sciences,1950,U.S.A.36:48-49.
[28]袁亚湘.非线性规划数值方法[M].上海科学技术出版社,1993.
[29]Facchinei F.,Pang J.S..Finite-Dimensional Variational inequality and complementarity problems[J].Springer-Verlag,New York,2003.
[30]P.T.Harker.A Variational inequality approach for the determination of oligopolistic market equilibrium.Mathematical Programming,1984,30:105-111.
[31]Chan D.,Pang J.S..The generalized quasi-variational inequality problem[J].Mathematics of Operations Research,1982,7:211-222.
[32]Pang J.S.,Yao J.C..On generalizational of a normal map and equation[J].SIAM J.on Control and Opetimization,1995,33:168-184.
[33]Yao J.C.,The generalized quasi-variational inequality problem with applications[J].J.Of Mathematical Analysis and Applications,1991,158:139-160.
[34]Baiocchi C.,Capelo A..Variational and quasi-variational inequalities[M].J.Wiley and Sons,New York,1984.
[35]Kocvara M.,Outrata J.V..On a class of quasi-variational inequalities[J].Optimization methods and Software,1995,5:275-295.
[36]Outrata J.V.,Zowe J.,A newton method for a class of quasi-variational inequalities[J].Computational Optimization and applications,1995,4:5-21.
[37]Noor M.A..Mixed quasi-variational inequalities[J].Appl.Math.Comput.,2003,146:553-578.
[38]Noor M.A..Implicit dynamical systems for quasi-variational inequalities[J].Appl.Math.Comput,2002,134:69-81.
[39]J.B.Rosen.Existence and uniqueness of equilibrium point for concave n-person games[J].Econometrica,1965,33:520-534.