（运筹学与控制论专业论文）nash均衡问题的二阶最优性条件.pdf

大连理工大学硕士学位论文 摘要 非合作多领导博弈问题可以转化为一类决策凸的广义n a s h 均衡问题。基于n a s h 均 衡均衡问题的一阶最优性条件，本文提出并证明广义n a s h 均衡问题的二阶必要性条件 和二阶充分性条件，并具体化到经典n a s h 均衡问题的二阶必要性条件和二阶充分性条 件 基于得到的n a s h 均衡问题的二阶最优性条件，可以用于证明光滑n e w t o n 法的收敛 速度 关键词：经典n as h 均衡问题；广义n a s h 均衡问题；二阶增长条件；拟变分不等式；外 二阶切集 n a s h 均衡问题的二阶最优性条件 a b s t r a c t i ti sk n o w nn l a tt h cn o n - c o o p c r a t em u l t i 1 e a d e r - f o l l o w e rg a m e sc a nb cf o r m u l a t e da sa p l a y e r - c o n v e xg e n e r a l i z e dn a s he q u i l i b r i u mp r o b l e m b a s i n go nt h ef i r s to r d e r o p t i m a l i t y c o n d i t i o n sf o rn a s he q u i l i b r i u mp r o b l e m ，w ep r o p o s e das e c o n do r d e rn e c e s s a r yc o n d i t i o na n d as e c o n do r d e rs u f f i c i e n tc o n d i t i o nf o r t h et h eg e n e r a l i z e dn a s he q u i l i b r i u mp r o b l e r d 酏e p r o p o s e dc o n d i t i o n sa r e 也e na p p l i e dt od e r i v et h et h es e c o n do r d e rn e c e s s a r yc o n d i t i o na n d t h es e c o n do r d e rs u f 五c i e n tc o n d i t i o nf o rt h ec l a s s i c a ln a s he q u i l i b r i u mp r o b l e m t h es e c o n d o r d e ro p t i m a l i t yc o n d i t i o n so nn a s he q u i l i b r i u mp r o b l e r n s c a nb cu s e dt o d e m o n s t r a t et h ec o n v e r g e n c es p e e do ft h es m o o t h i n gn e w t o nm e t h o d s k e yw o r d sc l a s s i c a ln a s he q u i l i b r i ap r o b l e m sg e n e r a l i z e dn a s he q u i l i b r i o r d e rg r o w t hc o n d i t i o n ；q u a s iv 1 一1 1 一 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究工 作所取得的成果尽我所知，除文中已经注明引用内容和致谢的地方外，本 论文不包含其他个人或集体已经发表的研究成果，也不包含其他己申请学 位或其他用途使用过的成果与我一同工作的同志对本研究所做的贡献均 已在论文中做了明确的说明并表示了谢意 若有不实之处，本人愿意承担相关法律责任 学位论文题目：n a s h 均衡问题的二阶最优性条件 作者签名：张r j 、媚日期：2 0 d 7 年6 月2 1 日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅学校有权 保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将本 学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印、或扫描等复制手段保存和汇编本学位论文 学位论文题目： 作者签名： 导师签名： n a s h 均衡问题的二阶最优性条件 弓长小娟日期：2 0 0 ? 年 日期：矽哆年 6 月1 2 - 日 占其 弓日 大连理工大学硕士学位论文 引言 纳什均衡名称来源及简介： 纳什均衡, n a s he q u i l i b r i u m ，又称为非合作博弈均衡是博弈论的一个重要术语以约 翰纳什命名约翰纳什1 9 4 8 年作为年轻数学博士生进入普林斯顿大学其研究成果见 于题为非合作博弈( 1 9 5 0 ) 的博士论文该博士论文导致了n 人博弈中的均衡点 ( 1 9 5 0 ) 和题为非合作博弈( 1 9 5 1 ) 两篇论文的发表纳什在上述论文中，介绍了合 作博弈与非合作博弈的区别他对非合作博弈的最重要贡献是阐明了包含任意人数局中 人和任意偏好的一种通用解概念也就是不限于两人零和博弈该解概念后来被称为纳什 均衡 纳什均衡定义： 假设有个局中人( p l a y e r s ) 参与博弈，给定其他人策略的条件下，每个局中人选择 自己的最优策略( 个人最优策略可能依赖于也可能不依赖于他人的战略) ，从而使自己效 用最大化。所有局中人策略构成一个策略组合( s t r a t e g yp r o f i l e ) 纳什均衡指的是这样一 种战略组合，这种策略组合由所有参与人最优策略组成即在给定别人策略的情况下没有 人有足够理由打破这种均衡 纳什均衡经典案例：囚徒困境 ( 1 9 5 0 年，数学家塔克任斯坦福大学客座教授，在给一些心理学家作讲演时，讲到两 个囚犯的故事) 假设有两个小偷a 和b 联合犯事、私入民宅被警察抓住警方将两人分别置于不同 的两个房间内进行审讯，对每一个犯罪嫌疑人，警方给出的政策是：如果一个犯罪嫌疑人坦 白了罪行，交出了赃物，于是证据确凿，两人都被判有罪如果另一个犯罪嫌疑人也作了坦 白，则两人各被判刑8 年；如果另一个犯罪嫌人没有坦白而是抵赖，则以妨碍公务罪( 因已 有证据表明其有罪) 再加刑2 年，而坦白者有功被减刑8 年，立即释放如果两人都抵赖， 则警方因证据不足不能判两人的偷窃罪，但可以私入民宅的罪名将两人各判入狱1 年表 l 给出了这个博弈的支付矩阵 表1 囚徒困境博弈 、 o ，存在& 的邻域圪，满足对所有的x o kn 圪，下述不等式成立： 0 0 ( x o ，己) 吼( 磊，- - ) + c d i s t ( x o ，瓯) r ( 2 1 ) 尤其，若t = 1 ，称一阶增长条件成立，若y = 2 ，称第二阶( 或二阶) 增长条件成立 很显然，若存在y 0 ，y - 阶增长条件在上成立，则瓦是最优化问题( 1 3 ) 的局部最 优解集尤其，若。s o = 式 是单点集，条件( 2 1 ) 具有下述形式： 眈( ，；呻) 吼( i ，- - u ) + c i i - x ：l l , 耽x on v o ， 其中圪是式的邻域 定义2 4 设是问题( 1 3 ) 的一个可行点，集合 c p ( ) ：= 吃( 毛) ：v 而g p ( ，；一u ) 丸( g o ( ，一x 呻) ) ，v 吼( ，；呻) 死o = 伟( 式) l v 毛o o ( x ：，；呻) 吃o 被称为最优化问题( 1 3 ) 在处的临界锥 一9 一 n a s h 均衡问题的二阶最优性条件 定义2 5 口1 令吼和矿都是连续可微的函数，称九吼f p 是问题( 1 3 ) 在点式e k 处的 l a g r a n g e 乘子，若它满足条件 一v l ( ，；呻，丸) k ( ) ，九人k 鱼( g o ( ，；呻) ) ， 用a o ( ) 记处所有l a g r a n g e 乘子的集合 定义2 6 f 3 】 设sc 孵”是非空集，x s ， 集合极限 瓦( z ) 一1 叩_ s - x 称为集合s 在点x 处的切锥； 集合极限 t 。, i , 2 碜= 咿等= w 战如f ( 枷+ j 1 旭s ) 邓归) ， 2 。 孙纠引t 甲掌= ) 成立。则对所有的办x 与任意的 序歹0 = 乙) ， 瑶2 万( ，| j i ) = d g ( x o ) - 1 礞2 _ 口( g ( ) ，d g ( x o ) h ) - d 2 g ( x o ) ( 乃，而) 。 引理2 6 1 6 】设x 是有限维的h i l b e r t 空间，以) c 是收敛到的可行点序列且满足 厂( 而) 厂( ) + d ( 0 毛一x 。0 ) 。 则存在一非零的临界方向办c ( ) 及序列 吒) 的子序列 ( t ) ) 满足( t ) = + 气办+ d ( & ) 对某一序y o t , 上0 ，如 0 成立。 n a s h 均衡问题的二阶最优性条件 2 4 负卦限锥的切锥与二阶切集嘲 考虑偶是空间贸”的负卦限吼： 孵! 声 y 贸。l y , o ，i = 1 ，m 。 令 缈( y ) = m ，a ，x y l ， 则, c o 是凸函数，锨! 可以表示为如下的凸函数的水平集 孵! = y 孵胛：伊( y ) o ) ， 其中 j ( y ) = i ：只= 9 ( y ) ，1 i 册) ，( y ，d ) = f ，( y ) ：谚= 伊【y ；d ) ) 。 不难看到，s l a t e r 条件对函数伊( ) 是成立的。设伊( y ) = 0 ，y 孵二， ( y ) = 孵”：z o ，i ，( y ) ) ， 再设汐( y ；d ) = 0 ，则 乙；( j ，d ) = w 贸胛：w ，o ? f ( y ，d ) ) 定义集合 k = o ， 贸f 矿， 我们可以得到k 的切锥与外二阶切集公式。对y k ，如果m a x y i ：f = g + 1 ，p ) = 0 有 瓦( y ) = d 贸，：4 = 0 ，i = 1 ，g ；4 0 ，i ，( y ) ) ， 且对d 瓦( 少) ，如果m a x d , ：f ，( y ) - 0 ，有 砭( y ，d ) = w 孵，：嵋= o , i = 1 ，g ；w o ，i ( y ，d ) 其中 ( y ) ：= i ：只= o ，i = q + l , - - - , p ) ，( y ，d ) ：= f ，( y ) ：z = 0 ) 。 3 一阶最优性条件 3 。1 一阶最优性条件 定理3 l ( 基本的一阶最优性条件) 聊可微函数吼( ，；u ) 在集合k ( ；呻) c 锨上的极小 化问题，如果式是局部极小点，则 ( v 吼( ，x 呻) ，w ) o ，对于所有的w 强艮) ( ) 或等价地，一v 气吃( ，x u ) 艮1 ( ) ，这可推出 o 0 - - ) ( ) + v 毛吃( ，l ) ( 3 1 ) 司见上式是f 述的变分不等式： w ( 五( 王”) ，c ( 五，；一u ) ) ，其中，e ( # ，王。) = v 毛吼( ，；呻) 。 将l ，从1 到n 这个n 个局中人的形式为( 3 1 ) 的一阶最优性条件合并得到g n e p 的一阶最优性条件： o ，( 工) + 以“z + ) 。 在彳( x ) 是闭凸集时，g n e p 的一阶最优性条件等价于下述拟变分不等式： q 玎( x ( ) ，) ， 其中x ( x 。) ：垂k ( p ) ，f ( x 。) 2 fv 而t 卜。 。 i v h 钆( x ) j 3 2k k t 条件 我们现在考虑问题( 1 3 ) 的l a g r a n g e 函数 乞( 毛，i 岫，九) ：= 吃( z ，一x 呻) + g ”( 毛，己) t 九， ( 3 1 ) 其中：a ，孵乇 n a s h 均衡问题的二阶最优性条件 根据【4 】，若式是问题( 1 3 ) 的局部最优解，对于第u 个局中人满足一适当的约束规 范( 例如m a n g a s a r i a n f r o m o v i t z 约束规范) ，则存在一个l a g r a n g e 乘子向量元孵七，使 得经典的k k t 条件 v l ( 矗如九) ( 3 2 ) 0 九上- g ”i ，x u ) 0 在( ，元) 处成立 将u 从1 到n 这个n 个局中人的k k t 条件合并在一起在x 是g n e p 的一个解，并 且对于所有的局中人都满足一定的约束规范的情况下，则存在一个l a g r a n g e 乘子允贸7 使得系统 三( 而a ) = ( 3 3 ) 0 a 上一g ( x ) 0 在( x ，石) 处成立其中 九：= 三 ，g c x ，：= 三暑 ，工c x ，允，：= v 而厶( x ，a 1 ) v 却( x ，a ) 在一定的约束规范下，系统( 3 3 ) 可以被认为是g n e p 的一阶必要性条件，并且系统 ( 3 3 ) 是一个k k t 系统在更近一步的凸假设下，系统( 3 3 ) 的解x 部分是一个广义n a s h 均衡点( q 姬) ，那么系统( 3 3 ) 同时是g n e p 的一个充分性条件 命题3 2 t 2 】令g n e p 是决策凸的，那么对于系统( 3 3 ) 的每一个解( f ，石1 ，向量x 是g n e p 的解 证明：由于g n e p 是决策凸的，由定义可知，对于给定的x 一。，第u 个局中人的最小值问题就 是凸的，那么系统( 3 3 ) 的解的分量就是此最小值问题( 1 3 ) 的最优解 对于d = l ，n ，综合起来可知，向量z 是g n e p 的最优解 口 3 3 拟变分不等式 我们记f o ( x ) ：= v 玉，o o ( x ) ，则系统( 3 2 ) 可描述如下： 大连理工大学硕士学位论文 咖心黑麓斟。 4 ， 易证，式( 3 2 ) 是变分不等式v ( 鼍，f o ) 的k k t 系统，即寻找戈满足： 一v 而皖( ，一x u ) ，。乙，( ) 即 ( v 而见( 式，；一。) ，y 一式) o ，v y x o ( x p ) 显然系统( 3 3 ) 是拟变分不等式q v ( x ，f ) 的k k t 系统，也就是说x 是一个广义n a s h 均衡点当且仅当 ( y 一工+ ) 1r ( x ) 0 v y x ( x ) ， 其中x ( x ) = 兀n 。k ( t p ) ，( x ) 兰( v 吃( x ) ) 二，贸”。 一 大连理工大学硕士学位论文 。二二- 一一 4 二阶最优性条件 4 1 g n e p 的二阶最优性条件 4 1 1g n e p 耵二澎r 必要性条件 对于问题( 1 3 ) ，我们可以写出其在瓦( ；一p ) 处的l a 鲫1 9 e 乘子集合 人。( ) 2 九贸i v 厶( ，己，九) 心( 式) ，九( g o ( 毛，一x 呻) ) = 九孵i v 乞( 毛，己，九) = o ，九( 旷( # ，己) ) 根据命题2 2 ，若在可行点式处，人u ( ) 非空，那么临界锥可表示为： c ”( ) 2 丸( ) ：v 而g p ( ，一x u ) 九( g 。( ，；呻) ) ，v 毛吼( ，；呻) 吃= o = 吃( b ) ( ) l v 南吼( ，；一。) 吃= o 2 毛( 叫( 毫) n v 毛吼( 式，；一) 上 对办，w 孵”，其中厅= ( o ，0 ，吃，0 ，o ) t ，w = ( o ，o , w o ，0 ，o ) t ，考虑路径 五。( ) ：孵_ 孵它具有下述形式： 纯) = + 乞吃+ 三k + y ( ，u ) ， ( 4 1 ) 满足厂( 气) = d ( ) 记x ( o ) = ( 化) ，一x 叫) ，则由g ”在处的二阶t a y l o r 展式得 g o ( x ( 乙) ) = g ”( ，一x u + t o y 毛g p ( ，一x 一。) + 主 r g ( ，；呻) + 2g p ( ，；呻) ( ，丸) + d ( 引 由外二阶切集的定义，存在乙一$ 0 满f f ：d i s t ( g ”( x ( 乙，。) ) ，孵! ) = 。( 叠。) 当且仅当 v g ”( 若，；一t ，) + v 毛( 式，- - p ) ( 吃，吃) t 虻2 ( g o ( ，x 一一。) ，o g 。( 毛，；呻) 丸) ， ( 4 2 ) 其中瑶( g o ( 式，；一u ) ，v ( 式，；叫) 丸) 是贸! 在矿( 巧，x 一呻) 沿方向v 毛g ”( ，；呻) 吃的外 n a s h 均衡问题的二阶最优性条件 引理4 1 巾1 设是问题( 1 3 ) 的局部最优解且r o b i n s o n 约束规范成立在处是成立的 则对每一吃c 。( ) 及满足( 4 2 ) 的所有k 锨屯，成立着 v 吼( ，一x 一。) + v 毛乱( ，；呻) ( 吃，) o ( 4 3 ) 证明：考虑办p c p ( 若) 及满足( 4 2 ) 的k 则存在乙，上。满足 d i s t ( g ”( x ( ，p ，。) ) ，锨! ) = 。( ，。) 因此，由定理2 1 ，( 4 1 ) 中的项y ( 乙川) 可以取得使 ( o ，。) 托( ；一u ) ，即x o ( t o ，) 是可行的，且，( ，叩) = 。( t 。) 进一步，由吼在式处的二阶 t a y l o r 展式有 吼( 工( 乙，。) ) = 吼( 式，- - 。) + ，u ，。v 吼( ，；一。) + 知 v 而见( 茸，；呻) + 叱见( ，一x 呻) ( 吃，) + d ( 白) 。 由于c 。( ) ，v o o ( x ：，；呻) 吃= o 因为吒( 乙，) 是可行的，对充分大的咒有 见( x ( 乙。) ) 吼( ，；一u ) ，因而得( 4 3 ) 式成立 在临界方向九的定义中，其满足v g ”( ，；一p ) 死( g v ( 菇，；。) ) ，因为，否则外二 阶切集t 贸2 刍( g v ( ，1 x u ) ，v g 。( ，x 1 一。) 吃) 是空集。那么引理4 1 可以用一最优化问题来 描述。即，对任何吃p ( 毛) ，下述问题 n f i 娟n v 而见( 巧，1 x u ) + v 乏而吼( ，；叩) ( 丸，) “4 ) s j v 毛g ”( ，；一u ) 。+ v 乏矿( ，己) ( 吃，吃) t 弛2 ( g v ( 式，；叫) ，v 毛矿( ，；呻) 丸) 、。 的最优值是非负的 由2 4 节关于负卦限的切锥与二阶切集公式，得到 k ( l ) ( 菇) = m k ( 珀：v 而酽( ，；叫) o ，川( ，一x 呻) ) ， 其中 砥，珀= f ：矿( 葛，叫= 0 记在点起作用的不等式约束集合。 设m a n g a s a r i a n f r o m o v i t z 约束规范在处成立，即 大连理工大学硕士学位论文 ( i ) d g i ( x o )i = 1 ，q 是线性尢夭趵， ( i i ) 3 h x ：o g , ( x o ) h = 0 ，i = 1 ，q ，三吕( x o ) 办 o ， ( 4 。l o ) i 己x ( x ) = 五( t 。) 置( 艺) k ( z ) ， j ；l = ( 九) ：，c ( z + ) = c ( i ) c 2 ( ) c ( ) ，五= ( 屯，a ( x ) = 人，( i ) x - - x 人( ) ， 三( x ，五) = ( 厶( 工，五) 厶( x ，如) 厶( x ，厶) ) 。 定理4 3 设二阶充分条件( 4 1 0 ) 成立，则二阶增长条件在点x 处成立 证明：易知二阶增长条件在点x 处成立等价于对任意的u = 1 ，二阶增长条件在点戈 处成立 首先我们证明( 4 1 0 ) 式等价于对任意的d = 1 ，n ，都有下式成立： v 叭2 ，l ( x ，屯) ( 九，h o ) o ，v 九c ”( ) 0 ( 4 1 1 ) 充分性 对于任意的且h 0 ，由( 4 1 0 ) 成立可知， x ，a ) 0 0 v ；2 l 2 ( x ，t ) 0 0 ；。； 0 v 乏瓢三( 工+ ，厶) 是正定的，贝= j v u = 1 ，v i l ( x ，九) o 由厅c ( x ) 且办o 可知， v 。= 1 ，n ，九c ”( ) o ，v 2 厶( x ，凡) ( ，钆) 0 必要性 对于式( 4 1 0 ) ，我们可以将办= ( 九) ：。带入到不等式左边，便可得到下式 ( 曩) v 知厶( x ，a ) 0 0 0 v 厶( x ，五) 0 0 i；。； 00 v m 2 厶( x ，厶) n a s h 均衡问题的二阶最优性条件 ( 4 1 2 ) ，v 2 ，厶( x ， ) 扛4 - - + v 毛厶( x ，厶) k ， 由v 九ec ”( x ：) o ) ，v 聪2 乞( x ，九) ( ，吃) o ，显然( 4 1 2 ) 大于0 下面证明若v 吃c ”( ) o ) ，v 毛，厶( x ，九) ( 九，九) o ，则二阶增长条件在点 处成立 用反证法来证明设二阶增长条件在点处不成立。则存在序列k 。以( 疋。) ，具 有形式。= 瓦+ f m h o 吃。i i - - 1 ，t v ，。上o ， o ，满足 见( 虻p ) + 。( ( 乙。) 2 ) 色( 扎。) ， ( 4 1 3 ) 由引理2 6 ，存在九ec ”( 式) n 6 咖b ，存在序列 体) 满足： 净乌= 吃，m 专办 赢习吨以刚 则由( 4 1 1 ) 知，存在 o ，存在屯人。( 毛) 满足 v 矾2 ，l ( 了，九) ( 丸，九) ( 4 1 4 ) 由v b 厶( x ，九) = o 及屯是有界的，得到 l ( h h ，。，五) 一l ( x ，旯) = ( r u 以) 2v & 乙( x ，九) ( ，吃) + 。( ( ，。) 2 ) ， 由式( 4 1 4 ) ，j j 充分大时，厶( 吒机，p ，五) 一厶( x ，允) t o m ) 2 + 。( ( 乙) 2 ) 则由( 丸，g o ( 砖，。) 一g ”( x ) ) o 得到 眈( k z 。) 一包( ，z 。) l ( 矗嘞，z 。，五) 一l ( x ，五) t o ) 2 + 。( ( 乙) 2 ) ， 与( 4 1 3 ) 矛盾 假设不成立即若v 九e c ”( ) o ) ，v 乏耳t o ( x ，乃) ( 吃，九) o ，则二阶增长条件在点艺 处成立 口 命题4 4 1 6 令k - y ：g ( y ) o ) ，其中g ：y 一页是一下半连续的凸函数。设存在歹满 足g ( 歹) o ，v h c ( x ) o ) 丑e ( r ) 是在点x 处二阶增长条件成立的充分必要条件。 证明：易知二阶增长条件在点，处成立等价于对任意的u = 1 ，二阶增长条件在点 处成立。 用反证法证明在点处的二阶增长条件成立。假设二阶增长条件在虻处不成立。 则存在一可行点序列毛。咒( z 。) 收敛到葛，满足 a o ( x v 。) s 眈( 艺，。) + 。( ( ，) 2 ) ， ( 4 1 6 ) 其中乙。= 0 矗。一毛 1 1 。由近似临界锥条件紧致性，若有必要可取一子列，可设 九。- - ( x o 川- x ：) , o 。收敛到向量九c ”( 式) 。显然，l m - , ，因而死0 。 由g ”( z 。) 在处的二阶t a y l o r 展式，有 g o ( x o 。) = e + t v 。d + 专e 。 v 耳g ”( 艺，。) 。+ 吒 g ”( 艺，z 。) ( ，九) + 口( t 。) n a s h 均衡问题的二阶最优性条件 其中k 。= t - ，：( x o ，。一式一乙，。吃) 。注意到矗，。一z 一，p ，。九= o f f 附) ，有乙，。k ，。_ 0 。 由例4 1 知贸! 是二阶正则的，且r ( 厅) = 礓( g ( x ) ，v ，g ( 了+ ) 厅) 是凸的，结合外 二阶正则性的定义，可以得到 v x , , g ”( ，t 。) k ，。+ v 轰，g p ( ，。) ( 吃，九) r ( 九) + d ( 1 ) 马：， ( 4 1 7 ) 也有 o o ( x z p ) = 吼( x ) + 乙，。v ，o v ( x ) 九+ _ ，lt 叫2v 耳o o ( x ) 。+ v m 2 ，e c x ) ( 丸，九) + 。( t 。) 因此，用( 4 1 6 ) 与( 4 1 7 ) ，可找到一序列气。一0 满足 2 7 品_ 耳吼( x ：吃+ ( v ，吃( x ，。，一+ 了i 眈( x ) ( ，丸) ) 巳，一 ( 4 1 8 ) it x g ”( ，t 。) m o 。+ v 三 g p ( 虻，t 。) ( 吃，h o ) r ( h o ) + c o 。吣： 由( 4 1 0 ) ，存在九人。) 满足 v l l ( x , 旯) ( 乃，h ) k ， 其中r 0 是一数，由( 4 18 ) 的第二条件得 ( 凡，v ，g ”( z p ) m o 。+ v i ，g “( ，。) ( ，吃) ) 气。i i 九i l 。 则存在一l a g r a n g e 乘子，有v l 见( x ) = 0 。因此，由( 4 1 7 ) 与( 4 1 8 ) 可得 o 2 已v “眈 ) 吃+ ( v ，见( x ) m o 。+ v i 乱( z ) ( 九，h o ) ) - 占o 。 + ( 九，v 而g ”( ，u ) m o 。+ v 2 ，g ”( ，t p ) ( 吮，丸) ) ) 一气，0 九0 = v 三三( x ，力) ( 办，h ) r 一气。( 1 + l l 九i i ) 因为气。一0 ，得到一矛盾。 对于在x 处m f 约束规范成立情况的结论，充分性由上述推导得到，必要性由定 理4 2 得到 口 4 2o n e p 的二阶最优性条件 4 2 1o n e p 的二阶必要性条件 首先，对于经典n a s h 均衡问题第u 个局中人的最优化问题( 1 1 ) ，我们先写出其 l a g r a n g e 函数： 大连理工大学硕士学位论文 l a x ，。，a o ) = o o ( r o ，p ) + ( 九，) ， 及在式k 处的乘子集合 人p ( ) = 乃孵- v 而l ( x ，气) 以即( z ：) ，乃吆，( ) ) = 九贸珥7i 屯+ v 玉，眈( x ) = o ，五k ，( ) 根据命题2 2 ，若在可行点式处，人。( ) 非空，那么临界锥可表示为： c ”( 式) = 乇，( 虻) ：毛，( ) ，v ，眈( 工) 死= o ) = 死乙。，( 式) l v 0 0 ( x ) 九= 0 = & ，( ) n r 见( x ) 工 推论4 6 ( 二阶必要条件) 设x 是c n e p 的局部最优解，在x 处m a n g a s a r i a n f r o m o v i t z ( 简记为m f ) 约束规范成立，则v 乃c ( 工) ，五a ( x ) ， s u ，p 、 v 三三( 工，力) ( 办，办) o ( 4 。1 9 ) e p l 、 、 。 记工( x ，五) = ( 厶( x ，五) 厶( x , 2 2 ) 厶( ，氐) ) 1 ，办= ( 丸) ：，五= ( 乃) ：， c ( x ) - - c 1 ( i ) c 2 ( ) c ( x ；：，) ，人( 工) = 人。( i ) 人( ) 。 4 2 2o n e p 的二阶充分性条件 定义4 2 称二阶充分条件在可行点工x 处成立，若对于任意的| i z c ( 工) 且办0 ， 2 e a ( x ) ， v 三三( x ，五) ( 办，办) o ， ( 4 2 0 ) 记彳= 五x 2 蜀，乃= ( 九) ：，c ( x ) = c 1 ( i ) c 2 ( x ：) c ( ) ，五= ( 丸) ：， a ( 工) = 人，( i ) 人( ) ，三( x ，五) = ( 厶( x ，a ) 厶( x ，如) 厶( 工，厶) ) 1 。 推论4 7 设二阶充分条件( 4 1 7 ) 成立，则二阶增长条件在点x 处成立 推论4 8 设x 是c n e p 的可行点，该点上的l a g r a n g e 乘子集合是非空的，设对每一 乃c ( x ) ，集合贸! 在g ( x ) 处沿方向v ，g ( x ) 办相对于映射m = v ，g ( x ) 是外二阶正 则的。则二阶条件( 4 2 0 ) 可推出在点x + 出的二阶增长条件。 若在x 处m f 约束规范成立，且对任何而c ( x ) ，五人( x ) ，则二阶条件 n a s h 均衡问题的二阶最优性条件 s u p v 三三( x ，力) ( 办，| l ，) o ，v h c ( x ) 1 0 l 五e ( t ) 、 是在点j 。处二阶增长条件成立的充分必要条件。 大连理工大学硕士学位论文 5 光滑n e w t o n 算法 5 1 非线性互补问题 l ( x ，a ) = o 在c x ，石，处成立其中允：= 三 ，g c x ，：= g g 二： ，三c x ，a ，；l 九ji ( x ) j 线性互补问题( 简写为n c p ) ，本章我们将讨论其算法 v 而厶( x ， ) ； v h 厶( x ，扎) ( 5 1 ) 这是一个非 首先我们将n c p ( f ) 转化为方程组形式，然后利用解决方程组的方法去解决这个非 线性互补问题n c p ( f ) 在本文中，我们用f i s h e r - b t m m e i s t e r 函数( 简称f b 函数) ： ：吼2 一婀 矽( 口，b ) = 4 a 2 + 6 2 一( 口+ 6 ) 显然地， 咖( 口，6 ) = o 口0 ，b 0 那么( 5 1 ) 等价于下述方程： 日( a ，x ) = v 南厶( x ， ) j v ，。厶( x ，丸) 妒( 丑j ，科( x ) ) 咖( ”一盛( 工) ) i ( k ”一( x ) ) 妒( 丸以，一g 名( x ) ) = 0 我们令a _ ( 知) t = ( a ，五， 扎。“) 丁= ( a z i l ， 一2 9 n a s h 均衡问题的二阶最优性条件 g ( x ) ：= ( 9 1 ( x ) g n ( x ) ) 1 = ( g ) g , l ( x ) g ，( x ) ( x ) ) 。= ( 彰( x ) ) j ： 我们知道：f b 函数在( 0 ，0 ) 处是不可微的，所以我们不能用传统的方法去求解h ( z ，x ) ， 为此我们考虑它的如下光滑形式： 丸( 口，b ) = 4 a 2 + b 2 + 占2 一( 口+ 6 ) ，g 0 显然地，对于任意的s 0 ，我们可以得到： 九( 口，6 ) = 0 车口0 ，b 0 ，a b = s 2 2 因此我们我们可以解决下述方程组： h ( e ，九，功= v 屯厶( x ， ) ； v h l n ( x ，扎) 屯( 九1 ，一g l ( x ) ) 九( a 7 ，一岛( x ) ) = 0 特别地指出：当s = 0 ，九( 口，b ) = ( 口，b ) 对于每一对( 口，b ) 婀2 ，l 咖屯( 口，6 ) = ( 口，b ) 为 了简便起见，记z = ( s ，a ，x ) 选择；婀+ ，( o ，1 ) 满足：州s l l o ，函数 纯( ) 在任意点( 五，x ) 暇7x 贸”处都是连续可微的 由日( 占，五，x ) 的表达式可知，对于任意的s 0 ，日( ) 是连续可微的，其j a c o b i a n 矩阵如 下： ，( ，五，石) ：。1 。( ：孑。召i x n 【c dej 其中：c 吼7 ，b ，d 和z 都是对角矩阵，且： a = v ，g l o 。 那么可得日( z ) 是非奇异的。 当元= 0 时，则 n a s h 均衡问题的二阶最优性条件 lv g ：( x ) 7 7 ，l + + “+ 2 + v 玉g ：( x ) 7 7 l + + “+ 3 + + v 彰( x ) 仍l + - 斗+ l + v i 薯厶( 丑，x ) r , + + 1 = o 1，+ ( ( 赫一卜斗州= 。 ( 5 3 ) 由( 5 3 ) 的第二个方程我们得到：当占一0 时，r , + l = 0 由于刁= ( 仍，7 2 ，r 2 + 1 ) t o ，则必存在一个约束蜀似) = o 。 一3 4 一 口 大连理工大学硕士学位论文 结论 ( 1 ) 本文得到了广义n a s h 均衡i 司题的二阶必要性条件：设r 是广义n a s h 均衡问题的局 部最优解，在工处m a n g a s a r i a n f r o m o v i t z ( 简记为m f ) 约束规范成立，则 v h c ( z 。) ，旯a ( 工) ，s 黑、 v ( z + ，五) ( 蛐) o 。 e i j l 。 和二阶充分性条件：称二阶充分条件在可行点工+ x ( x ) 处成立，若对于任意的办c ( x + 1 且力0 ，a e a ( x ) ，v 三三( x ，五) ( 办，办) o 。 并且推广到经典n a s h 均衡问题的二阶必要性条件和二阶充分性条件。进而证明了：设x 是g n e p 的可行点，该点上的l a g r a n g e 乘子集合是非空的，设对每一办c ( x ) ，集合孵! 在g ( x ) 处沿方向v ，g ( x ) 玉相对于映射必= v ，g ( x ) 是外二阶正则的。则二阶条件 v h c ( x ) o ，3 2 e a ( x ) 满足v 三三( x ，五) ( 乃，厅) o 。 可推出在点，出的二阶增长条件。 若在x 处m f 约束规范成立，且对任何办c ( 工) ，2 a ( x ) ，则二阶条件 s u p v ：三( x ，五) ( 而，h ) 0 , v h c ( 了) o 丑e l r ) 是在点工处二阶增长条件成立的充分必要条件。 ( 2 ) 根据我们得到的n a s h 均衡问题的二阶条件，我们根据【8 】可得到光滑n e w t o n 法的收 敛性：z 是由光滑n e w t o n 算法产生的有限序列 z ) 的聚点，假定日在z 是半光滑的，并 且所有v o h ( z ) 都非奇异的。那么这个序列) 收敛于z ， l k + 1 一z + 0 = 。( 0 z 。一z 8 ) 且 s = o ( s ：、) n 同时，若丑在z 处是强半光滑的，则： 0 z i + l z i l = d ( 0 z i z 1 1 2 ) 且 占j + 1 = d ( 占? ) 2f n 大连理工大学硕士学位论文 参考文献 【l 】j o n g - s h ip a n ga n df u k u s h i m & q u a s i - v a r i a t i o n a li n e q u a l i t i e s ，g e n e r a l i z e dn a s he q u i l i b r i a , a n d m u l t i - l e a d e rf o l l o w e rg a m e s c m s2 ：21 - 5 6 ( 2 0 0 5 ) 【2 】f r a n c i s c of a c c h i n e i a n d r e a sf i s c h e r g e n e r a l i z e dn a s he q u i l i b r i ap r o b l e m sa n dn e w t o nm e t h o d s m a t h p r o g r a m ，s e t b ( 2 0 0 9 ) 11 7 ：1 6 3 - 1 9 4 f 3 j f 博南，a 夏皮罗著，张立卫译最优化问题的扰动分析北京：科学出版社，2 0 0 8 - 0 6 f 4 】f a c c h i n e i ，f ，p a n g ，j 一s ：f i n i t e - d i m e n s i o n a lv a r i a t i o n a li n e q u a l i t i e sa n dc o m p l e m e n t a r i t y p r o b l e m s s p r i n g e r ，n e wy o r k ( 2 0 0 3 ) 【5 r o b i n s o n ，s m ：s t a b i l i t yt h e o r yf o rs y s t e m so fi n e q u a l i t i e s p a r ti i ：d i f f e r e n t i a b l en o n l i n e a r s y s t e m s s l a mj n u m e r a n a l 1 3 ( 1 9 7 6 ) ，4 9 7 - 5 1 3 【6 】b o n n a n sf a n ds h a p i r oa ，p e r t u r b a t i o na n a l y s i so fo p t i m i z a t i o np r o b l e m s s p r i n g e r - v e r l a g ! n e wy o r k , 2 0 0 0 【7 】j o u r a n i ，a ：c o n s t r a i n tq u a l i f