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

-精选财经经济类资料- -最新财经经济资料-感谢阅读- 1 求解广义纳什均衡问题的指数型惩 罚函数方法 摘 要：本文利用指数型惩罚函 数部分地惩罚耦合约束，从而将广义纳 什均衡问题（GNEP）的求解转化为求 解一系列光滑的惩罚纳什均衡问题 （NEP） 。我们证明了若光滑的惩罚 NEP 序列的解序列的聚点处 EMFCQ 成 立，则此聚点是 GNEP 的一个解。进一 步，我们把惩罚 NEP 的 KKT 条件转化 为一个非光滑方程系统，然后应用带有 Armijo 线搜索的半光滑牛顿法来求解此 系统。最后，数值结果表明我们的指数 型惩罚函数方法是有效的。 中国论文网 /3/view-12987483.htm 关键词：运筹学；指数型惩罚函 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 2 数；半光滑牛顿法；广义纳什均衡 中图分类号：0225 文章标识码：A 文章编号：1007-3221（2015） 01-0081-08 引言 广义纳什均衡问题（generalized Nash equilibrium problem 简记为 CNEP）是标准的纳什均衡问题 （NEP）的推广，它允许每个参与人的 目标函数和策略集都可以依赖于竞争者 的策略.这使得 GNFP 较 NEP 更适合于 描述实际的竞争市场.GNEP 的研究起源 于 1952 年的经典文献。1965 年文献考 虑了所有参与人的决策都满足共享凸约 束的 GNEP；随后，1991 年文献将 GNEP 变型为一个拟变分不等式（QVI） ， 但是关于 QVI 的有效算法仍很少.近期 以来 GNEP 越来越多地被应用于建模经 济、工程、交通运输、电力、计算机、 通信和环境等领域中的问题（见综述文 章） ，可是对 GNEP 数值方法的研究却 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 3 远不如对经典 NEP 研究的那样完善。 求解 GNEP 的数值方法，因问题 的不同背景及目标的不同而各有差异。 主要包括基于 QVI 变型、基于正则化 Nikaido-Isoda 函数的优化问题变型、松 弛方法、参数化变分不等式（VI）方法 （见综述文章 14，5-） 。但是这些方法 主要是处理标准的 NEP 或者共享凸约 束的 GNEP。尽管如此，对于无特殊结 构的 GNEP 而言，惩罚方法和使用 KKT 条件的方法大概是最有效的两类 方法。特别地，文献提出了一个序列惩 罚方法，其中序列中的每个惩罚问题都 是 SC2 光滑的惩罚 NEP。文献给出了 一个求解 GNEP 的障碍函数惩罚方法。 本文的主要工作是，利用指数型 惩罚函数提出一种新的求解一般形式的 CNEP 的序列惩罚方法，其中序列中的 每个惩罚问题都是光滑的 C2 惩罚 NEP。我们证明了若光滑的惩罚 NEP 序 列的解序列的聚点处 EMFCQ 成立，则 此聚点是 GNEP 的一个解。进一步，我 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 4 们把惩罚 NEP 的 KKT 条件转化为一个 非光滑方程系统，然后再用带有 Armijo 线搜索的半光滑牛顿法来求解此系统。 最后，数值结果表明我们的指数型惩罚 函数方法是有效的。lGNEP 的定义及预 备知识 GNEP 是标准的 NEP 的推广。具 体地说，设有个参与人，特每个参与 人 VE1，N的决策变量记为是由 这个决策变量构成的向量，其中为了 强调第 v 个参与人的决策变量，有时我 们也将 x 写成，这里表示 x 中除了第 v 个决策变量之外的其余所有决策变量按 照原来顺序构成的向量，其中设参与人 v 的效用函数为，策略集依赖于其余参 与人的决策变量。第 v 个参与人的目的 就是，在给定其余参与人的决策变量之 后，选择自己的决策变量使它满足如下 极小化问题： GNEP 就是这样的问题，找一个 向量 x，使得对所有的 v=l， 每个参与人 v 的策略都满足（在给定其 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 5 余参与人的决策变量条件下）： 如此一个向量 x 被叫做一个广义 纳什均衡（简记为 GNE） ，或称为广义 纳什均衡问题的一个解。特别地，如果 每个参与人的策略集不依赖于其余参与 人的决策变量，等价于其中是某一个给 定的集合，那么 GNEP 就退化成为标准 的 NEP。在 NEP 与 GNEP 之间的一种 特殊情形便是所谓的共享凸约束 GNEP，其中为一个非空闭凸集合， 下面介绍本文需要的两个概念： Clarke 广义次微分、向量值函数的半光 滑性。 令 X，y 是有限维向量空间，0 是 X 中的一个开集，是一个定义在 0 上 的局部 Lipschitz 连续函数，由 Rademacher 定理我们知道， 在集合 O 上几乎处处 Frechet 可微。用表示 在 0 上所有 Frechet 可微点构成的集合，则 函数 在 xE0 处的 Bouligand 次微分 （B-次微分）定义为 其中为 在处的 Jacobian。 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 6 在 x 处的 Clarke 意义下广义次 微分定义为的凸包，即，下面要介绍的 半光滑性的概念最初由 Mifflin 提出， 之后由 Qi 和 Sun推广到了向量值函数。 定义 1 令是开集 0 上的局部 Lipschitz 连续函数，则称 在处半光滑， 若 （i） 在 x 处方向可微； （ii）对任意和有。 进一步，我们称 在处强半光滑， 若 在 x 处半光滑，并且对于任意和 x） ，有 （ x +x）- （x）-V（x） =。 在求解一个由半光滑方程构成的 系统时，下面给出的强 BD-正则性条件 在算法中所起的作用类似于求解一个由 光滑方程构成的系统时用到的 Jacobian 矩阵非奇异性条件。 定义 2 设在 x 处是局部 Lipschitz 连续，我们称 在处是强 BD-正则的， 若对任意的，都满足 H 是非奇异的。进 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 7 一步，若 x 满足系统 （x）=0 且 在 x 处是强 BD-正则的，那么我们称 x 是 该系统的强 BD-正则解。 2 GNEP 的指数型惩罚函数方法 在本文中，我们假设第 v 个参与 人的策略集的表达形式如下： 其中，是依赖于其他参与人的决 策变量的，因此它被称为 GNEP 的耦合 约束只依赖于第 v 个参与人的决策变量， 因此它被称为 GNEP 的自身约束。 那么，GNEP 的第 v 个参与人面 临的优化问题如下： 对于每个参与人 v=l，N， 我们做以下假设： 假设 1 设对于每个参与人 v=l，都是二次连续可微的，并且 对于每个向量和都是凸的，都是凸的。 注：上述关于 GNEP 的凸性的假设在 GNEP 的文献中是标准的假设，而关于 目标函数和约束函数的光滑性的假设是 为了设计局部超线性收敛算法的需要 （见综述文章） 。 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 8 由假设 1 可以知道，每一个参与 人 v 面临的优化问题（2）都是一个凸 规划，因此是 （2）式的解当且仅当那么，第 v 个参与人面临的优化问题（2）也可以 写为 众所周知，求解一个经典 NEP 要比求解一个 GNEP 容易得多，因此我 们求解 GNEP 的指数型惩罚函数方法的 想法就是通过部分地惩罚 GNEP 中的那 些困难的耦合约束，使得求解 GNEP 等 价于求解一列经典 NEP。 这文样得到的 NEP 中的第 v 个 参与人面临的优化问题为：接下来我们 要证明，通过求解一列经典 NEP（6） 可以得到原 GNEP（2）的解。对于向 量我们定义映射为 并称（9）为原 CNEP（2）的惩 罚 NEP。很显然由假设 1 知，任意给定， 对应于每个参与人的子问题（9）都是 凸的、C2 光滑的优化问题，并且 XEX 是惩罚 NEP 的解当且仅当对于每个 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 9 v=1，N ， 下面我们给出广义 Mangasarian- Fromovitz 约束规范（EMFCQ ）的定义， 这个定义在证明 GNEP 的指数型惩罚函 数方法的收敛性时会用到。 定义 3 我们称 QVI（F，G，H） 在它的可行点 x 处满足广义 Mangasarian-Fromovitz 约束规范 （EMFCQ） ，如果下式成立： 其中，和是拉格朗日乘子。令和 是第个参与人的拉格朗日乘子向量，我 们将个参与人的 KKT 条件联合起来， 得到 QVI（F，G，H）的 KKT 系统， 即 下面一个引理证明了在恰当的条 件下， （15）可以用来求解 QVI（F，G，H） 。 引理 2 令 QVI（F，G，H）在处 满足 EMFCQ，则 x 是 QVI（F，G，H）的解当且仅当存在 （，） ，并且（x， ，）满足 KKT 系统（15） 。 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 10 证明 由假设 1，我们知道，是拟 变分不等式 QVI（F，G，H）的解当且 仅当 下面给出我们的指数型惩罚函数 方法的收敛性定理。 定理 1 令是趋于+的正数序列， 对于每是当时惩罚 NEP（9）的解。令 x 是序列的一个聚点，且在 x 处 EMFCQ（12）成立，则 x 是 GNEP（2）的解。 证明 由 x 是序列的一个聚点， 则存在的一个子列，记为，满足为了证 明 x 是 GNEP 的解，由（4）式知，我 们只需证 x 是 QVI（F，G，H）的解。 首先我们来证明对于充分大的 i，惩罚 NEP （9）的等价问题（11）的 MFCQ 在处成立。令，显然，对于充分 大的 i，有。由反证法，我们假设存在 一个无穷指标集，满足对于任意，都有 下式成立 显然，这与在 x 处 EMFCQ 成立 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 11 的定理条件相矛盾。因此由反证法知， 对于充分大的 i，问题（11）的 MFCQ 在处成立，即有于是我们得到，对于充 分大的 i，存在满足 3 半光滑牛顿法求解惩罚 NEP 及数值结果 接着，我们应用半光滑牛顿法来 求解惩罚 NEP（9） 。首先我们将与惩罚 问题（9）等价的问题（11）的 KKT 系 统等价地写成一个非光滑方程组的形式， 然后应用带有 Arm