利用拟变分不等式罚方法来求解广义纳什均衡问题

Using Quasi-variational Inequalities Penalty Method to Solve the Generalized Nash Equilibrium Problems

由于非合作主从博弈可以转化为一个广义纳什均衡问题,其中每个局中人解决一个带均衡约束的非凸数学规划。这样的转化存在两个主要的缺点:一个是纳什均衡点可能不存在,这是由于每个局中人问题具有非凸性;另一个是这样一个非凸的纳什博弈是难以计算的。现假设得到了可行的转换,将多主从博弈转化为带凸约束集的纳什均衡问题,并且转化有实用的解,而后者反过来转化为拟变分不等式,对此提出一个迭代罚方法,并给出这种方法的收敛性。

The noncooperative multi-leader-follower game can be formulated as a generalized Nash equilibrium problem where each player solves a nonconvex mathematical program with equilibrium constraints.Two major disadvantages exist with such a formulation:One is that the Nash equilibrium may not exist because of the nonconvexity in each player’s problem;the other is that such a nonconvex Nash game is computationally intractable.In order to obtain a viable formulation that is amenable to practical solution,we introduce a class of remedial models for the multi-leader-follower game that can be formulated as generalized Nash games with convexified strategy sets.In turn,a game of the latter kind can be formulated as a quasi-variational inequality for whose solution we develop an iterative penalty method.We establish the convergence of the method,which involves solving a sequence of penalized variational inequalities,under a set of modest assumptions.