广义Nash均衡问题的分解算法研究及应用

Generalized Nash equilibrium problem is one of the most popular research topics among the field of numerical optimization. It originates from economics, while has many applications in various fields such as transportation, communication, environment, computer science, etc. On the other hand, decomposition methods get great progresses in recent years, and show their great advantages in image processing and signal processing. In this project, based on theories and algorithms for optimization, we study decomposition algorithms for the generalized Nash equilibrium problems. Using the techniques as duality, introducing new variables, linearization, we transform the generalized Nash equilibrium problem into optimization problems or quasi-variational inequality problems with separable structures. Then, we analyze the structures of the new forms of the problems, and develop efficient numerical methods with fully using the advantage structures. Under resonable conditions, we prove the global convergence and analyze the local rate of convergence of the new algorithms. We apply our models and algorithms to some concrete problems such as traffic equilibrium problems and transportation congestion control problems. The research not only can give insight on the intersections between the generalized Nash equilibrium problems and hot research topics of numerical optimization, but also can have impact on a large range of application fields, especially on transportation research.

广义Nash均衡问题是优化领域近年研究的一个热点问题. 它是一个根源于经济、在很多领域中有重要应用的一个模型，如交通、通讯、环境、计算机科学等. 另一方面，分解算法近些年取得重要进展，在图像、信号处理等领域显示出巨大的优势. 在本项目中，我们将基于数值优化理论和算法，展开对广义Nash均衡问题分解算法的研究：首先，通过对偶、引入新变量、线性化等技术，将广义纳什均衡问题转化成具有"可分"结构的优化问题或者拟变分不等式问题；然后对所产生的优化或者拟变分不等式问题进行结构分析，设计高效的数值方法，在合理的假设条件下证明算法的全局收敛性和局部收敛速度；通过大规模的数值实验验证算法的有效性； 最后，将我们的模型和算法应用到交通均衡、交通拥堵调节等具体问题. 该研究不仅推动广义Nash均衡问题与数值优化研究热点的交叉融合，而且在众多应用领域，特别是交通问题中，有重要的应用价值.

在过去的四年中，围绕着项目申请书内容，课题组对广义纳什均衡问题、最优化理论与算法开展研究工作，发表了学术论文30余篇，其中绝大多数被SCI/SSCI等学术榜收录。我们的研究成果主要有以下几个方面：.1..对广义Nash均衡问题进行研究，设计了交替方向法、惩罚算法等有效算法。.2..对交通、管理等领域的一些问题进行研究，给出了衡量由自由竞争所造成的系统效率缺失的界，进而能为管理者提供改进方案。.3..对交通均衡问题继续进行研究，提出了一些新的广义纳什均衡模型并设计了求解方法。.4..充分利用实际应用问题优化模型的“可分结构”，设计出一系列解决可分凸规划问题的算法，并分析了算法的全局收敛性和局部或全局线性收敛率、以及计算复杂性等。.5..对医疗张量成像等张量分解问题进行研究，设计了求解磁共振成像问题中张量分解的有效算法。.6..对非凸规划进行研究，为后续项目打下基础。.总之，我们对项目申请书的部分研究内容进行了深入的探讨和研究，并进行了其他的研究工作，为今后的研究工作打下了坚实的基础。