基于Peaceman-Rachford分裂的广义纳什均衡问题的分布式算法

doi:10.15960/j.cnki.issn.1007-6093.2026.03.005

运筹学学报（中英文） ›› 2026, Vol. 30 ›› Issue (3): 73-98.doi: 10.15960/j.cnki.issn.1007-6093.2026.03.005

所属专题：运筹与管理前沿：模型、算法及其应用专辑

• 运筹与管理前沿：模型、算法及其应用专辑 • 上一篇下一篇

基于Peaceman-Rachford分裂的广义纳什均衡问题的分布式算法

金柱石¹, 甘涛^2,3, 徐玲玲^2,3†

1. 江苏大学数学科学学院, 江苏镇江 212013;
2. 南京师范大学数学科学学院, 江苏南京 210023;
3. 大规模复杂系统数值模拟教育部重点实验室 (南京师范大学), 江苏南京 210023

收稿日期:2026-07-29 发布日期:2026-09-12
通讯作者: 徐玲玲 E-mail:xulingling@njnu.edu.cn
基金资助:
国家重点研发计划(No.2023YFA1009300)

Distributed algorithms for generalized Nash equilibrium problems based on Peaceman-Rachford splitting

JIN Zhushi¹, GAN Tao^2,3, XU Lingling^2,3†

1. School of Mathematical Sciences, Jiangsu University, Zhenjiang 212013, Jiangsu, China;
2. School of Mathematical Sciences, Nanjing Normal University, Nanjing 210023, Jiangsu, China;
3. Key Laboratory of Numerical Simulation for Large Scale Complex Systems (Nanjing Normal University), Ministry of Education, Nanjing 210023, Jiangsu, China

Received:2026-07-29 Published:2026-09-12

摘要/Abstract

摘要： 本文研究带线性耦合约束的广义纳什均衡问题,提出两类基于算子分裂的分布式算法。通过引入各玩家对其他玩家决策的局部估计,将变分广义纳什均衡点的求解转化为双增广算子的零点问题。在此基础上,分别构造了带惯性的松弛Douglas-Rachford分裂算法和基于Peaceman-Rachford分裂的分布式算法。在线性耦合约束、凸可行集以及伪梯度映射强单调且Lipschitz连续的条件下,证明了所提算法的收敛性。数值实验验证了算法的有效性。

关键词: 广义纳什均衡问题, Peaceman-Rachford分裂, 惯性, 收敛性分析

Abstract: This paper studies generalized Nash equilibrium problems with linear coupling constraints and proposes two distributed algorithms based on operator splitting. By introducing local estimates of other players' decisions for each player, the computation of variational generalized Nash equilibria is reformulated as a zero-finding problem of a double-augmented operator. Based on this reformulation, an inertial relaxed Douglas-Rachford splitting algorithm and a distributed algorithm based on Peaceman-Rachford splitting are constructed. Under linear coupling constraints, convex feasible sets, and the strong monotonicity and Lipschitz continuity of the pseudo-gradient mapping, the convergence of the proposed algorithms is established. Numerical experiments verify the effectiveness of the algorithms.

Key words: generalized Nash equilibrium problem, Peaceman-Rachford splitting method, inertial, convergence analysis

中图分类号:

O221.2

金柱石, 甘涛, 徐玲玲. 基于Peaceman-Rachford分裂的广义纳什均衡问题的分布式算法[J]. 运筹学学报（中英文）, 2026, 30(3): 73-98.

JIN Zhushi, GAN Tao, XU Lingling. Distributed algorithms for generalized Nash equilibrium problems based on Peaceman-Rachford splitting[J]. Operations Research Transactions, 2026, 30(3): 73-98.

[1] Ye M J, Hu G Q. Distributed Nash equilibrium seeking by a consensus based approach [J]. IEEE Transactions on Automatic Control, 2017, 62(9): 4811-4818.
[2] Zhu M H, Frazzoli E. Distributed robust adaptive equilibrium computation for generalized convex games [J]. Automatica, 2016, 63: 82-91.
[3] Pan Y, Pavel L. Games with coupled propagated constraints in optical networks with multi-link topologies [J]. Automatica, 2009, 45(4): 871-880.
[4] Pavel L. An extension of duality to a game-theoretic framework [J]. Automatica, 2007, 43(2): 226-237.
[5] Alpcan T, Bąsar T. Distributed algorithms for Nash equilibria of flow control games [M]//Nowak A S, Szajowski K. (eds.) Advances in dynamic games: applications to economics; finance; optimization; and stochastic control, Boston: Birkhäuser, 2005: 473-498.
[6] Yin H B, Shanbhag U V, Mehta P G. Nash equilibrium problems with scaled congestion costs and shared constraints [J]. IEEE Transactions on Automatic Control, 2011, 56(7): 1702-1708.
[7] Ozdaglar A, Menache I. Network games: theory; models; and dynamics [M]. San Rafael: Morgan & Claypool Publishers, 2011.
[8] Grammatico S. Dynamic control of agents playing aggregative games with coupling constraints [J]. IEEE Transactions on Automatic Control, 2017, 62(9): 4537-4548.
[9] Facchinei F, Kanzow C. Generalized Nash equilibrium problems [J]. Annals of Operations Research, 2010, 175(1): 177-211.
[10] Salehisadaghiani F, Pavel L. Distributed Nash equilibrium seeking: a gossip-based algorithm [J]. Automatica, 2016, 72: 209-216.
[11] Tatarenko T, Shi W, Nedić A. Geometric convergence of gradient play algorithms for distributed Nash equilibrium seeking [J]. IEEE Transactions on Automatic Control, 2021, 66(11): 5342-5353.
[12] Koshal J, Nedić A, Shanbhag U V. Distributed algorithms for aggregative games on graphs [J]. Operations Research, 2016, 64(3): 680-704.
[13] Ye M, Han Q L, Ding L, et al. Distributed Nash equilibrium seeking in games with partial decision information: a survey [J]. Proceedings of the IEEE, 2023, 111(2): 140-157.
[14] Pavel L. On operator theory and applications in game theory [J]. Annual Review of Control, Robotics, and Autonomous Systems, 2025, 9: 99-122.
[15] Pavel L. Distributed GNE seeking under partial-decision information over networks via a doubly-augmented operator splitting approach [J]. IEEE Transactions on Automatic Control, 2020, 65(4): 1584-1597.
[16] Yi P, Pavel L. Distributed generalized Nash equilibria computation of monotone games via double-layer preconditioned proximal-point algorithms [J]. IEEE Transactions on Control of Network Systems, 2018, 6(1): 299-311.
[17] Bianchi M, Belgioioso G, Grammatico S. Fast generalized Nash equilibrium seeking under partial-decision information [J]. Automatica, 2022, 136: 110080.
[18] Huang Y H, Hu J H. Distributed solution of GNEP over networks via the Douglas-Rachford splitting method [C]//Proceedings of the 60th IEEE Conference on Decision and Control, 2021: 3110-3116.
[19] Zheng Z Q, Li H Q, Niu Y et al. Distributed generalized Nash equilibrium seeking: a backward-reflected-forward-backward-based algorithm [J]. Journal of the Franklin Institute, 2024, 361(1): 150-163.
[20] Ran L, Li H Q, Zheng L F, et al. Distributed generalized Nash equilibria computation of noncooperative games via novel primal-dual splitting algorithms [J]. IEEE Transactions on Signal and Information Processing over Networks, 2024, 10: 179-194.
[21] Belgioioso G, Grammatico S. Semi-decentralized generalized Nash equilibrium seeking in monotone aggregative games [J]. IEEE Transactions on Automatic Control, 2021, 68(1): 140-155.
[22] Shi L Y, He W L. Generalized Nash equilibrium seeking for networked noncooperative games with a dynamic event-triggered mechanism [J]. Applied Mathematical Modelling, 2023, 118: 39-52.
[23] Wang M X, Chen J N, Wen C Y, et al. Adaptive generalized Nash equilibrium seeking algorithm for nonsmooth aggregative game under dynamic event-triggered mechanism [J]. Automatica, 2024, 169: 111835.
[24] Li H Q, Li J, Ran L, et al. A survey of distributed algorithms for aggregative games [J]. IEEE/CAA Journal of Automatica Sinica, 2025, 12(5): 859-871.
[25] Bauschke H H, Combettes P L. Convex analysis and monotone operator theory in Hilbert spaces [M]. New York: Springer, 2011.
[26] Paccagnan D, Gentile B, Parise F, et al. Distributed computation of generalized Nash equilibria in quadratic aggregative games with affine coupling constraints [C]//2016 IEEE 55th Conference on Decision and Control, 2016: 6123-6128.
[27] Belgioioso G, Grammatico S. Projected-gradient algorithms for generalized equilibrium seeking in aggregative games are preconditioned forward-backward methods [C]//2018 European Control Conference, 2018: 2188-2193.
[28] Facchinei F, Pang J S. Finite-dimensional variational inequalities and complementarity problems [M]. New York: Springer, 2003.
[29] Bianchi M, Grammatico S. A continuous-time distributed generalized Nash equilibrium seeking algorithm over networks for double-integrator agents [C]//2020 European Control Conference, 2020: 1474-1479.
[30] Lions P L, Mercier B. Splitting algorithms for the sum of two nonlinear operators [J]. SIAM Journal on Numerical Analysis, 1979, 16(6): 964-979.
[31] Bell H E. Gershgorin’s theorem and the zeros of polynomials [J]. The American Mathematical Monthly, 1965, 72(3): 292-295.
[32] Robbins H, Siegmund D. A convergence theorem for non-negative almost supermartingales and some applications [M]//Rustagi J S. (ed.) Optimizing Methods in Statistics, New York: Academic Press, 1971: 233-257.
[33] Salehisadaghiani F, Pavel L. Distributed Nash equilibrium seeking via the alternating direction method of multipliers [J]. IFAC-PapersOnLine, 2017, 50(1): 6166-6171.
[34] Facchinei F, Pang J S. Nash equilibria: The variational approach [M]//Palomar D P, Eldar Y C. (eds.) Convex optimization in signal processing and communications, Cambridge: Cambridge University Press, 2010: 443-493.
[35] Schneeweiss C. Distributed decision making [M]. Berlin: Springer, 2012.

基于Peaceman-Rachford分裂的广义纳什均衡问题的分布式算法

Distributed algorithms for generalized Nash equilibrium problems based on Peaceman-Rachford splitting

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 7

编辑推荐

Metrics

本文评价

[1]	贾泽慧, 李丹丹, 肖玉娇, 岳素云. 一种基于方差缩减的联邦对称交替方向乘子法[J]. 运筹学学报（中英文）, 2026, 30(3): 116-132.
[2]	王庆阳, 袁梓航, 杨嘉玟, 孔翔玉, 陈彩华. 非凸优化中交替方向乘子法的收敛性研究[J]. 运筹学学报（中英文）, 2026, 30(3): 99-115.
[3]	闫喜红, 唐晓妮. 一种求解低秩矩阵补全的惯性加速交替方向法[J]. 运筹学学报（中英文）, 2025, 29(1): 172-184.
[4]	陈梓妍, 乔云, 汪毅. 负惯性指数为1的混合图[J]. 运筹学学报（中英文）, 2024, 28(4): 152-161.
[5]	叶明露, 黄明. 连续非单调变分不等式的一种惯性投影算法[J]. 运筹学学报（中英文）, 2024, 28(2): 81-92.
[6]	党亚峥, 薛中会. 凸可行问题的平行近似次梯度投影算法[J]. 运筹学学报, 2015, 19(1): 117-124.
[7]	钱小燕, 施庆生, 刘浩, 石岿然. 大规模无约束优化的一族有限存储LBFGS类算法[J]. 运筹学学报, 2011, 15(3): 9-18.