[1]毕培培,徐玲玲,韩德仁.带BB步长的自适应投影法解广义纳什均衡问题[J].南京师大学报(自然科学版),2014,37(04):31.
　Bi Peipei,Xu Lingling,Han Deren.A Self-Adaptive Projection Method with the BB-Step Sizes forSolving Generalized Nash Equilibrium Problems[J].Journal of Nanjing Normal University(Natural Science Edition),2014,37(04):31.
点击复制

带BB步长的自适应投影法解广义纳什均衡问题()
分享到：

《南京师大学报（自然科学版）》[ISSN:1001-4616/CN:32-1239/N]

卷:
第37卷
期数:
2014年04期
页码:
31
栏目:
数学
出版日期:
2014-12-31

文章信息/Info

Title:
A Self-Adaptive Projection Method with the BB-Step Sizes forSolving Generalized Nash Equilibrium Problems
作者:
毕培培; 徐玲玲; 韩德仁
南京师范大学数学科学学院,江苏省大规模复杂系统数值模拟重点实验室,南京 210023
Author(s):
Bi Peipei; Xu Lingling; Han Deren
Jiangsu Key Laboratory for NSLSCS,School of Mathematical Sciences,Nanjing Normal University,Nanjing 210023,China
关键词:
广义纳什均衡问题; 拟变分不等式; 投影法; BB步长; 收敛性
Keywords:
generalized nash equilibrium problem; quasi-variational inequality(QVI); projection method; BB-step sizes; convergence
分类号:
O242
文献标志码:
A
摘要:
广义纳什均衡问题是一种非合作博弈,其每个竞争者的策略集和目标函数都要依靠其他竞争者的策略.它在经济学、管理科学及交通运输等领域都有广泛的应用,但如何有效地求解广义纳什均衡问题仍然是备受关注的课题.本文提出了带有BB步长的自适应投影法求解广义纳什均衡问题:首先,把广义纳什均衡问题转化成拟变分不等式问题,然后把BB步长推广到求解拟变分不等式问题上,并在函数余强制条件下证明了算法的全局收敛性.数值结果进一步说明该方法的有效性.
Abstract:
The generalized Nash equilibrium problem(GNEP)is a noncooperative game in which the strategy set of each player,as well as his payoff function,depend on the rival players’ strategies.It can be widely used in economics,management sciences and traffic assignment,but how to effective solve the generalized Nash equilibrium problem is still a subject of concern.In this paper,we present a self-adaptive projection method with the BB-step sizes for solving generalized Nash equilibrium problems:First,we give the reformulation of a generalized Nash equilibrium.Then,we extend the BB-step sizes to the QVI formulation of the GNEP,we adopt them in projection methods,and prove that under the condition that the underlying function is co-coercive,the sequence generated by the method converges to a solution of the quasi-variational inequality problem globally.Some preliminary computational results are reported,which illustrate that the new method is efficient.

参考文献/References:

[1] Harker P.Generalized Nash games and quasi-variationalinequalities[J].Eur J Oper Res,1991,54(1):81-94.
[2]Zhang J Z,Qu B,Xiu N H.Some projection-like methods for the generalized Nash equilibria[J].Comput Optim Appl,2010,45(1):89-109.
[3]Contreras J,Krawczyk J,Klusch M.Numerical solutions to Nash-Cournotequilibria in coupledconstraint electricity markets[J].IEEE Trans Power Syst,2004,19(1):195-206.
[4]刘肇军,刘宗谦,冯素芬.有限策略型博弈中的相关策略与具有合约的博弈及其均衡[J].南京师大学报:自然科学版,2008,31(3):33-38.
[5]Facchinei F,Pang J S.Finite-Dimensional Variational Inequality and Complementarity Problems[M].New York:Springer.2003.
[6]Fukushima M,Pang J S.Quasi-variational inequalities,generalized Nash equilibria,and multieader-follower games[J].Comput Manag Sci,2005,2(1):21-56.
[7]Kubota K,Fukushim M.Gap function approach to the generalized Nash equilibrium problem[J].J Opt Theory Appl,2010,144(3):511-531.
[8]Heusinger A Von,Kanzow C.Optimization reformulations of the generalized Nash equilibriumproblem using Nikaido-Isoda-type functions[J].Comput Optim Appl,2009,43(3):353-377.
[9]Fukushima M.Restricted generalized Nash equilibria and controlled penalty algorithm[J].Comput Manag Sci,2011,8(3):201-218.
[10]Nabetani K,Tseng P,Fukushima M.Parametrized variational inequality approaches to generalized Nash equilibrium problems with shared constraints[J].Comput Optim Appl,2011,48(3):423-452.
[11]Dreves A,Kanzow C.Nonsmooth optimization reformulations characterizing all solutions of jointly convexgeneralized Nash equilibrium problems[J].Comput Optim Appl,2011,50(1):23-48.
[12]Heusinger A Von,Kanzow C,Fukushima M.Newton’s method for computing a normalized equilibrium in the generalized Nash game through fixed point formulation[J].Math Program,2012,132(1/2):99-123.
[13]Goldstein A.Convex programming in Hilbert space[J].Bull Amer Math Soc,1964,70:709-710.

[14]Khobotov E.Modification of the extragradient method for solving variational inequalities and certain optimization problems[J].USSR Comput Math Math Phys,1987,27(5):120-127.
[15]Barzilai J,Borwein J M.Two point step size gradient method[J].IMAJ Numer Anal,1988,8(1):141-148.
[16]Dai Y H,Liao L Z.R-linear convergence of the Barzilai and Borwein gradient method[J].IMAJ Numer Anal,2002,22(1):1-10.
[17]Marcos R.On the Barzilai and Borwein choice of steplength for the gradient method[J].IMAJ Numer Anal,1993,13(3):321-326.
[18]Han D R,Zhang H C,Gang Q,et al.An improved two-step method for solving generalized Nash equilibrium problems[J].Eur J Oper Res,2012,216:613-623.

备注/Memo

备注/Memo:
收稿日期:2013-09-16.
基金项目:国家自然科学基金(11071122)、江苏省自然科学基金(BK2009397)、江苏省高校自然科学研究项目(13KJD110007).
通讯联系人:徐玲玲,博士,讲师,研究方向:最优化理论与算法.E-mail:xulingling@njnu.edu.cn
更新日期/Last Update: 2014-12-31