Exponential Penalty Function Method for Generalized Nash Equilibrium Problem

doi:10.12005/orms.2015.0011

Operations Research and Management Science ›› 2015, Vol. 24 ›› Issue (1): 81-88.DOI: 10.12005/orms.2015.0011

• Theory Analysis and Methodology Study • Previous Articles Next Articles

Exponential Penalty Function Method for Generalized Nash Equilibrium Problem

XU Ji-xiang^1,2, HOU Jian^1,3, TAN Yan-hua⁴, FENG En-min¹

1.School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China;
2.School of Sciences, Tianjin University of Technology and Education, Tianjin 300222, China;
3.Management College, Inner Mongolia University of Technology, Hohhot 010051, China;
4.School of Sciences, Hebei University of Technology, Tianjin 300130, China

Received:2013-01-08 Online:2015-02-12

求解广义纳什均衡问题的指数型惩罚函数方法

许吉祥^1,2, 侯剑^1,3, 谭彦华⁴, 冯恩民¹

1.大连理工大学数学科学学院,辽宁大连 116024;
2.天津职业技术师范大学理学院,天津 300222;
3.内蒙古工业大学管理学院,内蒙古呼和浩特 010051;
4.河北工业大学理学院,天津 300130

作者简介:许吉祥(1982-),男,博士,助教。
基金资助:
863项目(2007AA02Z208);973项目(2007CB714304);国家自然科学基金项目(10871033,11171050)

Abstract

Abstract: This paper reformulates the generalized Nash equilibrium problem(GNEP)as a sequence of smoothing penalized NEPs by means of a partial penalization of the coupling constraints where the exponential penalty functions are used. We demonstrate that the limit point is a solution to the GNEP under the EMFCQ at a limit point of solutions to smoothing penalized NEPs. Further more, we formulate the Karush-Kuhn-Tucker(KKT)conditions for smoothing penalized NEPs into a system of nonsmooth equations, and then apply the semismooth Newton method with Armijo line search to solve the system. Finally, the numerical results show that our exponential penalty function method for GNEP is effective.

Key words: operational research, the exponential penalty function, semismooth Newton method, generalized Nash equilibrium problem

摘要： 本文利用指数型惩罚函数部分地惩罚耦合约束,从而将广义纳什均衡问题(GNEP)的求解转化为求解一系列光滑的惩罚纳什均衡问题 (NEP)。我们证明了若光滑的惩罚NEP序列的解序列的聚点处EMFCQ成立,则此聚点是 GNEP的一个解。进一步,我们把惩罚 NEP的KKT条件转化为一个非光滑方程系统,然后应用带有 Armijo 线搜索的半光滑牛顿法来求解此系统。最后,数值结果表明我们的指数型惩罚函数方法是有效的。

关键词: 运筹学, 指数型惩罚函数, 半光滑牛顿法, 广义纳什均衡

CLC Number:

O225

XU Ji-xiang, HOU Jian, TAN Yan-hua, FENG En-min. Exponential Penalty Function Method for Generalized Nash Equilibrium Problem[J]. Operations Research and Management Science, 2015, 24(1): 81-88.

许吉祥, 侯剑, 谭彦华, 冯恩民. 求解广义纳什均衡问题的指数型惩罚函数方法[J]. 运筹与管理, 2015, 24(1): 81-88.

References

[1] Debreu G. A social equilibrium existence theorem[J]. Proceedings of the National Academy of Sciences, 1952, 38: 886-893.
[2] Rosen J B. Existence and uniqueness of equilibrium points for concave n-person games[J]. Econometrica, 1965, 33: 520-534.
[3] Harker P T. Generalized nash games and quasi-variational inequalities[J]. European Journal of Operational Research, 1991, 54: 81-94.
[4] Facchinei F, Kanzow C. Generalized nash equilibrium problems[J]. Annals of Operations Research, 2010, 175: 177-211.
[5] Krawczyk J. Numerical solutions to coupled-constraint(or generalised Nash)equilibrium problems[J]. Computational Management Science, 2007, 4: 183-204.
[6] Cominetti R, Facchinei F, Lasserre J B. Modern optimization modelling techniques[M]. New York: Birkhuser, 2012. 151-188.
[7] Fukushima M, Pang J S. Quasi-variational inequalities, generalized nash equilibria, and multi-leader-follower games[J]. Computational Management Science, 2005, 2: 21-56.
[8] Hou J, Lai J F. A penalty approach for generalized nash equilibrium problem[J]. Communications In Mathematical Research, 2012, 28: 181-192.
[9] Clarke F H. Optimization and nonsmooth analysis[M]. New York: John Wiley, 1983.
[10] Mifflin R. Semismooth and semiconvex functions in constrained optimization[J]. SIAM Journal on Control and Optimization, 1977, 15: 959-972.
[11] Qi L, Sun J. A nonsmooth version of newton’s method[J]. Mathematical Programming, Ser.A, 1993, 58: 353-368.
[12] Rockafellar R T, Wets R J B. Variational analysis[M]. Springer, 1998.
[13] Luca T D, Facchinei F, Kanzow C. A semismooth equation approach to the solution of nonlinear complementarity problems[J]. Mathematical Programming, 1996, 75: 407-439.
[14] Hou J, Zhang L W. A barrier function method for generalized Nash equilibrium problems[J]. Journal of Industrial and Management Optimization, 2014, 10: 1091-1108.
[15] Kesselman A, Leonardi S, Bonifaci V. Game-theoretic analysis of internet switching with selfish users[A]. Deng X T, Ye Y Y. Lecture Notes in Computer Science[C]. Springer, 2005, 3828: 236-245.
[16] Facchinei F, Kanzow C. Penalty methods for the solution of generalized nash equilibrium problems[J]. SIAM Journal on Optimization, 2010, 20: 2228-2253.
[17] Contreras J, Klusch M, Krawczyk J B. Numerical solutions to nash-cournot equilibria in coupled constraint electricity markets[J]. IEEE Transactions on Power Systems, 2004, 19: 195-206.

Exponential Penalty Function Method for Generalized Nash Equilibrium Problem

求解广义纳什均衡问题的指数型惩罚函数方法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	CHEN Jiang-tao, LV Jian-qiu. Research on the Present Situation and Tendency of Operational Research Based on Knowledge Map [J]. Operations Research and Management Science, 2019, 28(1): 194-199.
[2]	ZHANG Meng, WANG Neng-min. Research on Vehicle Routing for Hazardous Materials Transportation Based on Catastrophe Avoidance [J]. Operations Research and Management Science, 2018, 27(8): 1-9.
[3]	DONG Feng, SHU Lin, LI Jing-yun, QIAO Jun. Evaluation and Promotion Path of Industry- University-ResearchCollaborative Innovation Efficiency [J]. Operations Research and Management Science, 2018, 27(10): 185-192.
[4]	WANG Dao-ping, XU Zhan, YANG Cen. Study on Location-routing Problem of Logistics Distribution Based on Two-stage Heuristic Algorithm [J]. Operations Research and Management Science, 2017, 26(4): 70-75.
[5]	LIN Gui-hua, WANG Yan-ru, ZHU Xi-de. Supply Chain Management with Time-Sensitive Products and Multiple Manufacturers [J]. Operations Research and Management Science, 2017, 26(3): 1-6.
[6]	CUI Wei, WANG San-ying. PDA Model Decomposing of Driving Forces of CO₂ Emissions of Urban Non-agricultural Land from the Perspective of the Production System [J]. Operations Research and Management Science, 2016, 25(2): 156-164.
[7]	GUO Qing-e, SU Bing. Fuzzy Multi-attribute Decision Making Method Based on Maximizing Deviation and Cross-Evaluation [J]. Operations Research and Management Science, 2015, 24(5): 75-81.
[8]	WANG Yan-qiu,YE Yong-sheng. The Pebbling Number of Multi-fan Graphs and Graham’s Conjecture [J]. Operations Research and Management Science, 2015, 24(4): 137-140.
[9]	YANG De-quan, XUE Yun-xia. Study on Logistics Performance Evaluation Based on Cross-efficiency DEA and Entropy IAHP Method [J]. Operations Research and Management Science, 2015, 24(3): 172-178.
[10]	YANG De-quan, WANG Jia. Inverse Optimal Value Method to Judge and Solve the More-for-less Paradox in Linear Programming [J]. Operations Research and Management Science, 2015, 24(1): 75-80.
[11]	ZHANG Hao, YANG Jia-ni, SU Xiang, GE Shi-lun. Network DEA-based Efficiency Measurement and Analysis of a Relational Two-stage Manufacturing System with Exogenous Inputs [J]. Operations Research and Management Science, 2014, 23(5): 160-167.
[12]	DONG Feng, LIU Xiao-yan, LONG Ru-yin, ZHOU De-qun. Analysis of Carbon Emission Efficiency in China Based on Three-Stage DEA Model [J]. Operations Research and Management Science, 2014, 23(4): 196-205.
[13]	SU Bing, ZHANG Meng, JI Hao. Research on Vehicle Routing for Scarce Emergency Relief Supply Dispatching in a Emergency [J]. Operations Research and Management Science, 2013, 22(6): 57-64.
[14]	GAO Jing, ZHANG Qiang. Research on Imputation for Cooperative Games with Fuzzy Coalitions [J]. Operations Research and Management Science, 2013, 22(6): 65-70.
[15]	CHEN Jin-xia, LI Wen-dong, FAN Lin-xian, YU Fang. Mechanism Design and Modeling Study for Purchasing and Inventory Optimization of China Daqing Oilfield Materials [J]. Operations Research and Management Science, 2013, 22(6): 132-139.