论文标题
非线性广义NASH平衡问题的一阶算法
First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems
论文作者
论文摘要
我们考虑在一类\ textIt {非线性通用纳什均衡问题（NGNEPS）}中计算平衡的问题，其中每个玩家的策略设置由平等和不平等约束定义，这些策略可能取决于竞争对手的选择。尽管已经对解决此问题的算法的渐近全局收敛和局部收敛速率进行了广泛的研究，但对非催化性迭代复杂性的分析仍处于起步阶段。本文分别基于二次惩罚方法（qpm）和增强拉格朗日方法（ALM）提出了两种一阶算法 - 用加速的镜像 - prox算法作为每个内部环中的求解器。我们为求解单调和强烈单调的NGNEPS建立了全球收敛保证，并提供了以梯度评估数量表示的非肌电复杂性界限。实验结果证明了我们算法在实践中的效率。
We consider the problem of computing an equilibrium in a class of \textit{nonlinear generalized Nash equilibrium problems (NGNEPs)} in which the strategy sets for each player are defined by equality and inequality constraints that may depend on the choices of rival players. While the asymptotic global convergence and local convergence rates of algorithms to solve this problem have been extensively investigated, the analysis of nonasymptotic iteration complexity is still in its infancy. This paper presents two first-order algorithms -- based on the quadratic penalty method (QPM) and augmented Lagrangian method (ALM), respectively -- with an accelerated mirror-prox algorithm as the solver in each inner loop. We establish a global convergence guarantee for solving monotone and strongly monotone NGNEPs and provide nonasymptotic complexity bounds expressed in terms of the number of gradient evaluations. Experimental results demonstrate the efficiency of our algorithms in practice.
