（运筹学与控制论专业论文）变分不等式的超梯度算法及其改进算法.pdf

变分不等式的超梯度算法及其改进算法 运筹学与控制论 研究生晏萍指导教师何诣然教授 论文摘要：本文主要对交分不等式的超梯度算法及它的改进算法进行分析和讨论 第二章将w a n g ，x i u 和z h a n g 1 1 改进的超梯度算法推广到无穷维希尔伯特空间， 并讨论改进后的超梯度算法所产生的迭代序列的收敛性质第三章在有限维空间 中，采用与文献【1 】不同的阿米霍线性搜索方法及有利方向，改进了超梯度算法，并 用实例论证了改进算法的优越性第四章运用新的有利方向，改进了 a n ，h a n 和 s u n 2 1 的投影算法 关键词：变分不等式问题；超梯度算法；希尔伯特空间；弱收敛；强收敛； 伪单调；余强制 第i 页，共3 7 页 t h ee x t r a g r a d i e n tm e t h o da n di t sm o d i f i c a t i o nf o r v a r i a t i o n a li n e q u a l i t y m a j o r ：o p e r a t i o n a lr e s e a r c ha n dc y b e r n e t i c s p o s t g r a d u a t e ：y a hp i n gs u p e r v i s o r ：p r o f e s s o rh ey i - r a n a b s t r a c t ：t h i sp a p e rp r e s e n t st h ee x t r a g r a d i e n tm e t h o da n di t sm o d i f i c a t i o n f o rv a r i a t i o n a li n e q u a l i t yp r o b l e m i nc h a p t e rt w o ，w ee x t e n dt h em o d i f i e d e x t r a g r a d i e n tm e t h o dw h i c h i s p r o p o s e db yw a n g ，x i ua n dz h a n g 1 t o i n f i n i t e - d i m e n s i o n a lh i l b e r ts p a c e a n dd i s c u s sc o n v e r g e n c eo fam o d i f l e d e x t r a g r a d i e n tm e t h o df o rp s e u d o m o n o t o n ev a r i a t i o n a li n e q u a l i t yi ni v _ f i n i t e - d i m e n s i o n a lh i l b e r ts p a c e i nc h a p t e rt h r e e ，w em o d i f ye x t r a g r a d i e n tm e t h o d w i t hd i f f e r e n ta r m i j o - t y p el i n e s e a r c ha n dp r o f i t a b l ed i r e c t i o nf r o mp a p e rli n t h ef i n i t e - d i m e n s i o n a ls p a c e ，t h e nw eu s en u m e r i c a le x p e r i m e n t st oc o m p a r eo u r m e t h o dw i t ha l g o r i t h m 【1 t os e ei t sa d v a n t a g e s i nc h a p t e rf o u r ，w ei m p r o v e t h ep r o j e c t i o na l g o r i t h mp r o p o s e db yy a h ，h a na n ds u n 2 k e yw o r d s ：v a r i a t i o n a li n e q u a l i t yp r o b l e m s ；e x t r a g r a d i e n tm e t h o d ；h i l b e r t s p a c e ；w e a kc o n v e r g e n c e ；s t r o n gc o n v e r g e n c e ；p s e u d o m o n o t o n e ；c o - c o e r c i v e 第i i 页，共3 7 页 四川师范大学学位论文独创性及 使用授权声明 本人声明：所呈交学位论文，是本人在导师指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外， 本论文不含任何其他个人或集体已经发表或撰写过的作品或成 果。对本文的研究做出重要贡献的个人和集体，均已在文中以明 确方式标明。本声明的法律结果由本人承担。 本人承诺：已提交的学位论文电子版与论文纸本的内容一致。 如因不符而引起的学术声誉上的损失由本人自负。 本人同意所撰写学位论文的使用授权遵照学校的管理规定： 学校作为申请学位的条件之一，学位论文著作权拥有者须授权 所在大学拥有学位论文的部分使用权，即：1 ) 已获学位的研究生 必须按学校规定提交印刷版和电子版学位论文，可以将学位论文 的全部或部分内容编入有关数据库供检索；2 ) 为教学、科研和学 术交流目的，学校可以将公开的学位论文或解密后的学位论文作 为资料在图书馆、资料室等场所或在有关网络上供阅读、浏览。 本人授权中国科学技术信息研究所将本学位论文收录到中 国学位论文全文数据库，并通过网络向社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字日期j年 月日 翩躲铴。物仫 签字日期：乃解9 。月夕目 引言 变分不等式在经济学，力学，微分方程，控制论，对策理论等理论和应用学 科等领域都起着非常重要的作用许多学者对其进行了深入研究 3 7 】变分不 等式算法更是备受关注 本文讨论的是经典的变分不等式问题：假设日是无穷维希尔伯特空间， xc 日是非空闭凸子集，f ：h _ 日是从希尔伯特空间到其自身上的连续映 射，存在z + x 使得 ( y ( x + ) ，y z + ) 0 ，对所有的y x 成立 关于变分不等式解的存在性结论f 4 - 9 ，可以归纳为两种方法：第一种为构 造法假设适当的条件，提出一种算法迭代产生变分不等式的解第二种为解析 法将变分不等式问题等价转换为更加容易研究的( 实际) 数学问题( 如不动点 问题，约束或无约束的控制问题) ，再利用解的存在性定理加以证明众所周知， 利用改进的超梯度算法产生的序列具备有界性，s u n 9 1 运用构造法建立该有界 性与变分不等式解的存在性之间的等价关系 1 0 ，1 1 上述结论不仅给出了变分 不等式解集非空的充分必要条件，并且暗示了改进后的超梯度算法具有更好的 收敛性 早在二十世纪七十年代，b a k u s i u s k j i 和p o l y a k 1 2 ，s i b o n y 1 3 】就已经开始 研究上述问题，现在仍然有很多学者投身此项研究【1 4 - 2 1 这其中的研究方法 大同小异，主要结构可由下面的迭代关系表达：+ 1 = 反【护一伉d k ，其中妒 是当前迭代点，k 是舻中的非空闭凸集，觑是受约束的迭代步长，也是有利 的搜索方向，( ) 是到非空闭凸集k 上的投影在x i u 和z h a n g 2 2 曾深入细 致的讨论过投影型算法的细节假设由这样的迭代方式产生的序列为 i ，倘 若变分不等式至少有一个解z + ，则对所有的k n 有i f z 1 一矿| f i i 矿一矿| l 成立，且有l i m 。扩= z + 那么称由该投影方法产生的迭代序列具有收敛 性，且收敛到解z + 几乎所有的投影型算法都具备该性质，如超梯度算法f 1 0 】 以及其改进算法 9 ，1 1 ，1 4 2 1 】文献 9 中采用与上类似的方法证明如果一种投 影型算法具有收敛性，则迭代序列的有界性与变分不等式解的存在性足等价的 第1 页，共3 7 页 目前有很多算法能解决v i ( f , x ) 问题，关于超梯度算法中的有利搜索方向 及迭代序列收敛时f 需要满足的条件有如下发展： ( 1 ) 由k o r p e l e v i c h 1 0 提出的超梯度算法，其迭代表达式为：铲= & 扩一 k f ( x 七) 】，x k + 1 = 取 扩一凤f ( 舻) 】算法产生的迭代序列的收敛需要f 具有 l i p s c h i t z 连续性当f 不是l i p s c h i t z 连续或者l i p s c h i t z 常数不确定时，这种 超梯度算法及其变形需要a r m i j o 线性搜索计算每个新实验点的投影步长，导致 计算量过大耗时过长f 1l ，1 4 ，1 5 ，1 8 ，2 3 - 2 5 ( 2 ) 由h e 1 5 ，s o l o d o v 和t s e n g 1 4 ，s u n 9 】和t s e n g 2 6 】提出的方向： z 七一铲一j 3 k ( f ( x 七) 一f ( 铲) ) ； ( 3 ) 由n o o r 2 7 提出的方向：z 七一护一f ( x 南) ； ( 4 ) 由i u s e m 和s v a i t e r 1 6 ，s o l o d o v 和s v a i t e r 1 7 】提出的方向：f ( y 七) 此 方向克服了k o r p e l e v i c h 1 0 】算法的缺陷，i u s e m 和s v a i t e r 1 6 】提出了对于伪单 调变分不等式改进的超梯度算法，此算法需要两次在x 上作投影后来此算法 再次被s o l o d o v 和s v a i t e r 1 7 改进此次改进需要在x 和xn 凰上作两次投 影，凰是由当前迭代点确定的超平面，这样迭代速度更快 ( 5 ) 由w a n g 2 0 等人提出的方向：l ( x 七一y 七+ f ( y ) ) 以上算法无一例外的建立在变分不等式的解集非空的基础上 ( 6 ) w a n g ，x i u 和z h a n g 1 提出了另一改进算法，此算法运用第一种构造法 解决伪单调变分不等式问题，优点在于不用假设伪单调变分不等式的解集非空， 可以利用算法产生的点列的收敛性检验变分不等式解的存在性当变分不等式 的解集非空时，算法产生的序列收敛到变分不等式的解；当变分不等式解集为 空集时，算法产生的序列发散 ( 7 ) 后来h a n - l o 2 8 构建了新的有利方向，d ( x 七，凤) = r ( x 七，威) + 卢k f ( x 七一 r ( x 七，仇) ) ，并在这种方向上提出了关于变分不等式的新算法 ( 8 ) l i 2 9 又提出了另一种新的算法：初始点z o 彤，7 ( 0 ，2 ) ，0 ( 0 ，2 ) ， 砂= 玖 扩一o q p - ( x ，反) 】，其中q ；= 1 一尝 z 七+ 1 = p k 【z 七一7 ( z 七一- z k ) 】； ( 9 ) 不久y a n ，h a n 和s u n 2 】对l i 2 9 提出的算法作了改进：初始点 第2 页，共3 7 页 z o k ，一y ( 0 ，2 ) ，口( 0 ，2 ) ， 砂= 淼渺一0 嚷r ( x 七，仇) 】，其中q ；= 1 一笔， x 1 = 玖 一，y ( 吭r ( ，仇) + ( 矿一砂) ) 】 本文第二章中，把w a n g ，x i u 和z h a n g 改进的超梯度算法推广到无穷维希 尔伯特空间，并讨论算法产生的序列在无穷维希尔伯特空间的收敛性质 本文第三章中，运用h e 3 0 1 的二次投影算法中的阿米霍线性搜索方法及有 利方向，改进了w a n g ，x i u 和z h a n g 的超梯度算法，运用不同的阿米霍线性搜 索得到区分当前迭代序列和变分不等式解集的超平面，证明算法产生的序列全 局收敛于变分不等式的解最后用实例论证了改进算法的优越性 本文第四章中，当f 具有余强制性，r ( 扩，仇) ，x 七一砂和g ( x 詹，仇) 都是有 利方向，易得当叩 0 ，7 - 0 时，r l r ( x 七，觑) + t ( x 。一护) + 9 ( 5 七，凤) 也为有利方 向，其中g ( x 七，仇) = r ( x 南，仇) 一伉 f ( 矿) 一f ( 一r ( x ，觑) ) 】改进了y a n ，h a n 和s u n 2 】的投影算法，证明改进后算法产生的迭代序列同样能收敛到变分不等 式的解 第3 页，共3 7 页 第一章预备知识 1 1常用记号 本文如无特殊说明，日是无穷维希尔伯特空间，舻是有限维空间，x 和k 分别是日和彤中的非空闭凸子集，f 是从日到自身的映射，( ，) 表示内积运 算用| | | i 表示范数 变分不等式问题( 简记为：v i p ( x ，f ) ) ：假设日是无穷维希尔伯特空间， xc 日是非空闭凸子集，f ：h _ 日是从希尔伯特空间到其自身上的连续映 射，找出x + x 使得 ( f ( z + ) ，y x + ) 0 ，对所有的y x 成立( 1 1 1 ) 用s o l ( x ，f ) 表示变分不等式的解集，简记为s 1 2 基本知识 定义1 2 1x 是希尔伯特空间日上的非空闭凸子集，向量z h ，定义 尸i x ( z ) = a r g m i n l l y z | i i y x ) 是x 到x 上的投影 定义1 2 2x 是希尔伯特空间日上的非空闭凸子集，任意x 1 ，x 2 x 有 ( f ( z 1 ) ，x 2 一x 1 ) 0 令( f ( x 2 ) ，x 2 一x 1 ) 0 则称f 是x 上的k 伪单调映射 定义1 2 3x 是希尔伯特空间日上的非空闭凸子集，如果映射f ( z ) 满足： ( 1 ) 对于每一个z x ，f ( x ) 是x 非空闭凸子集； ( 2 ) 若 z 知) cx - z x ，x 七一虿，且l i m s u p 七。( f ( z 七) ，x 七一y ) 0 ， 则对任意y x ，f ( - ) 满足( f ( - ) ，虿一y ) l i m i n f k - - 4 0 0 ( f ( 矿) ，x 七一秒) ，则称f 是b r e z i s 伪单调映射简记b 伪单调 注1 2 1 本文中如无特殊声明，第二章“伪单调”同时包含k 伪单调和 b 一伪单调的性质，第三章“伪单调”表示k 一伪单调 第4 页，共3 7 页 定义1 2 4x 是希尔伯特空间h 上的非空闭凸子集，如果存在e 0 ，对 任意的z 1 ，z 2 x ，有 ( f 1 ) ，z 2 一z 1 ) o 号( f ( z 2 ) ，z 2 一。1 ) 面1f l f ( 勋) 一f ( 。1 ) f f 2 则称f 在x 上具有p s e u d o - d u n n 性质 定义1 2 5k 是有限维空间形上的非空闭凸子集，任意z l ，z 2 k ，存在 c 0 ，有 ( f ( x 1 ) 一f ( z 2 ) ，x l x 2 ) t i l e ( x 1 ) 一f ( z 2 ) i i 则称f 在k 上具有余强制性 定义1 2 6 对于z h ，定义 r ( x ，a ) = z 一尸支( z a f ( z ) ) 为投影剩余记r ( x ，1 ) = r ) 引理1 2 1x 是希尔伯特空间日上的非空闭凸子集，对任意z ，y h 和 z x ，以下式子成立： ( 1 ) ( 取( z ) 一z ，z p x ( z ) ) 0 ( 2 ) i i p x ( z ) 一p x ( y ) lj 2 i | z y i f 2 一l i p x ( x ) 一z + y p x ( y ) 1 1 2 ( 3 ) l i p x ( z ) 一p x ( y ) j j i | z 一引1 事实上，由引理1 2 1 可得到，对任意z 在x 上的投影向量u ；等价于 u = 取x ) 当且仅当 0 一z ，z u ) 0 对所有的z x 成立 引理1 2 2z + 为v i ( f , x ) 的解，当且仅当t ( x ) = 0 以上的定义和引理由文献 3 1 中给出 引理1 2 3 ( 5 】f 是非空闭凸集x 上的伪单调映射，z 。s ，当且仅当 ( f ( z ) ，z z 4 ) 0 ，v x x 因此，伪单调变分不等式的解集可以看成由一簇半平面的交构成，也即s 是闭凸集 第5 页，共3 7 页 定义1 2 7x 是希尔伯特空间日上的非空子集，x ，如果存在虿x ， 使得i i 扩一虿i | _ 0 ，则称 】强收敛于虿记作 一) _ 虿如果对任意连续 线性泛函，都有( x 七) 一，( 虿) ，则称 x k ) 弱收敛于虿记作 舻) jz 定义1 2 8 ( 【2 ，d e f i n i t i o n2 1 】) 常数c 0 ，妒( z ) ：形一r 为连续泛函，如 果妒( z ) 满足 妒( z ) c i l r ( x ，p ) 1 1 2 ，且r ( x ，p ) = 0 妒( z ) = 0 ， 则称妒( z ) 为一个测量误差函数 定义1 2 9 ( 2 ，d e f i n i t i o n2 2 】) k 是有限维空间形上的非空闭凸子集， d ( x ) ：i t _ 舻满足：伍一x + ，d ( z ) ) 妒( z ) ，比k ，其中妒( z ) 为一个测量误 差函数，则称d ( x ) 为v i ( ex ) 的有利方向 引理1 2 4 【3 2 】对任意x 形，且p p 0 ，则 i j r ( z ，z ) i i ( z ，z ) i i 引理1 2 5 【3 3 】对任意z k ，且p p 0 ，则 m z ，驯、m z ，z ) i i 88 第6 页，共3 7 页 第二章改进的超梯度算法在无穷维空间中收敛 2 1问题来源 本章如无特殊说明，总假设日是无穷维希尔伯特空间，xch 是非空闭凸 子集 因为x 是闭凸集，所以对任意的z h ，投影映射： 取( z ) = a r g m i n i l y z l i l y x ) 是非空单值的 文献【1 ，在有限维空间中，当变分不等式解集非空，改进的超梯度算法产生 的迭代序列 有界，则有收敛子序列，从而可得算法产生的序列收敛至变 分不等式的解；反之，当变分不等式解集为空集时，序列h m 知- + l l 一x 0 f i = 。 但在无穷维空间中，当变分不等式解集非空，其它条件不变，迭代序列有界不能 推出序列收敛到变分不等式的解 本章主要是将w a n g ，x i u 和z h a n g 改进的超梯度算法推广到无穷维希尔 伯特空间，并证明在无穷维希尔伯特空间中算法的收敛性仍然成立 2 2 改进的超梯度算法 本节给出关于伪单调变分不等式改进的超梯度算法，并证明其在无穷维希 尔伯特空间中有意义 算法2 2 1 选择任意盯，y ( 0 ，1 ) ， 第0 步：x 0 x ，k = 0 ； 第k 步：对扩x ，计算z 南：= p x ( z 七一f ( z 七) ) 如果 0 ) l i = 0 ，停止； 否则，计算y 七：= ( 1 一吼) 扩+ r k z 七，其中r k = 7 舭，m k 是满足下式的最小的非 负整数m ： ( f ( x 七一, 7 m r ( 矿) ) ，r ( 矿) ) o l l r ( z 七) 1 1 2 ( 2 2 1 ) 第7 页，共3 7 页 令z 七+ 1 ：= p x i 畔n x ( x o ) ，其中 上珐：= z 日l ( z y 七，f ( y 奄) ) o ) ，( 2 2 2 ) 日2 ：= ( z h i ( x z ，z o z 膏) o ( 2 2 3 ) 此算法引用文献【1 ，且知此算法的迭代点在有限维空间中收敛到伪单调变 分不等式的解 接下来，我们讨论算法在无穷维空间的可行性如果由算法2 2 1 迭代产生 序列 ) ，使得i i r ( x 七) i | = 0 ，则z 七s ；否则从引理1 2 1 ，可得到 ( f ( x 七) ，r ( 扩) ) i i r ( x 七1 1 2 0 ( 2 2 4 ) 不难推出，如果s d ，超平面 a 月量：= z h l ( x y 静，f ( y 七) ) = 0 )( 2 2 5 ) 严格划分了 z 知 和s 1 7 接下来介绍的引理讨论在无穷维希尔伯特空间中，如果s 0 ，有s 硪n 磺a x ；如果s = 仍，但磁n 磺n x 0 ，说明此算法在无穷维希尔伯 特空间中有意义 引理2 2 1 ( 【1 ，l e m m a3 1 】) x 是希尔伯特空间日上的非空闭凸子集，f 是 x 上连续k 一伪单调映射如果s 仍，则对任意k 0 ，有s 硪n 磁n x 引理2 2 2 ( 1 ，l e m m a3 3 】) x 是希尔伯特空间日上的非空有界闭凸子 集，f 是x 上连续k 一伪单调映射则v i ( f , x ) 的解集非空 引理2 2 3 ( 【1 ，l e m m a3 2 1 ) x 是希尔伯特空间日上的非空闭凸子集，f 是 x 上连续k 一伪单调映射如果s = 仍，则对任意k ，有硪n 磁nx 0 证明：反正，假设存在k o 1 ，使得硪。n 硪nx = 毋，则存在整数m ， 使得 z 后i o k k o b ( x o ，m ) ， 并且 z 七一f ( x 七) 1 0 k k o b ( z o ，m ) ， 第8 y i ，共3 7 页 其中b ( z o ，m ) = z h i | i z z 0 0 m ) 当y = x n b ( z o ，2 m ) ，讨论变分不等式v i ( f y ) 从引理2 2 2 可得v i ( f , y ) 的解集蹄仍为避免与序列 h 1 ) ， 磁) ， ) 混淆，记 玩) ， 百； ， 萨 为算法应用到v i ( f , y ) 产生的相应的序列，可知 ( 1 ) 集合孝至少有+ 1 个元素； ( 2 ) 对任意0 k k o ，都有硪= 玩，磁= 玩，= 萨； ( 3 ) x k o 不是v i ( 只y ) 的解 因为o ，由引理2 2 1 知砭n 玩ny d ，所以砚n 硫nx 函， 与假设矛盾 由引理2 2 1 和引理2 2 3 ，在无穷维希尔伯特空间中，即使v i ( f , x ) 解集 为空集，算法也是有意义的，这就不用假设v i ( f , x ) 的解集非空 2 3 改进的超梯度算法在无穷维空间中的收敛分析 本节讨论在无穷维空间中算法产生的序列 矿) 关于伪单调变分不等式的 解集的收敛情况 引理2 3 1 假设算法2 2 1 产生的无限序列 扩) k 一伪单调映射f 在x 上一致连续且有界，如果s 0 ，则 矿) 有界，并且l i m k 。讯l l r ( x ) 1 1 2 = 0 证明：首先假设s d ，因为扩+ 1 ：= 辟礁n 壤n x ( 护) ，则 i l z 七+ 1 一x 0 l | | f z 4 一x o i j ，x + s ， 所以 扩】有界 因为z 七+ 1 ：= 嘞( z 抖1 ) ，扩：= 镌( 护) ，由引理1 2 1 可得 i l p ( z m ) 一( z o ) 1 1 2 剑z m x 0 肛i i ( z 1 ) 一z 1 + z o 一岛) 1 1 2 等价于 i i z 七+ 1 一x 0 l | 2 i i x 七一扩1 1 2 + i i x 七+ 1 一x k i l 2 ， ( 2 3 6 ) 可知删一扩吣递增，有上界，则收敛，因此可知： 胪+ 1 一z 奄酽= ( 7 ) 第9 页，共3 7 页 另一方面，因为z 七+ 1 硪，并且 啦p ) = x k - - 措芦f ( y k ) ， 所以 i i x k - x k + 1 l l2 i 矽一铂卅l = 掣币卵k l l r 而( x k ) 1 1 2 由( 2 3 7 ) 可得 熙省群一o 因为 扩) 有界，且f 具有界，则 ) 有界，这样 秒七) 和 f ( y 七) ) 都有界， 因此 1 i m 饥l l r ( x 奄) 1 1 2 = 0 引理2 3 2 假设算法2 2 1 产生的无限序列 扩) k - 伪单调映射f 在x 上一致连续，有界且具有p s e u d o - d u n n 性质，如果s 0 ，它的每个弱收敛点都 属于s ；否则s = 0 ，于是u i 。i i x 七一x o i i = o o 证明：由引理2 3 1 知【扩 有界，不失一般性，假设 ) 弱收敛到虿因 为x 为闭凸集，所以x 为弱闭集，则虿x 由引理2 3 1 不失一般性，假设 讯) 极限存在，则 1 i r ai i r ( x 七) 1 1 2 = 0 ，( 2 3 8 ) 或者 1 i r a 饥= 0 ( 2 3 9 ) 第一种情况l i m k 。i i r ( x 七) 1 1 2 = 0 因为 r ( x 岛) = 扩一取( 扩一f ( x 七) ) ， 利用投影变分不等式，推出 ( f ( x 七) ，y z 知) ( r ( x 知) ，y z 七+ r ( x 七) 一f ( x 七) ) ，v y x ， ( 2 3 1 0 ) 取下极限得到 l i r a i n f ( f ( x ) ，y 一扩) 0 ( 2 3 1 1 ) 第1 0 页，共3 7 页 假设f ( 虿) 0 ，令 畦扎筹蹴 ( 2 3 1 2 ) 则 i i t 2 一扩l i 一0 ， 由f 的一致连续性，得 f i f ( 矿) 一f ( x 七) i f _ 0 ( 2 3 1 3 ) 因为( f ( - ) ，t 七一虿) = 0 ，f 具有p s e u d o - d u n n 性质，则 ( f ( t 七) ，护一_ ) 击l i f ( t 七) 一f ( 虿) 1 1 2 由( 2 3 1 2 ) ，有 ( f ( t 七) ，t 知一动= ( g ( x 詹) ，z 七一虿) + ( f ( t 七) 一f ( x 奄) ，t 忌一虿) + 躐紫( f ( z ) ，f ( 虿) ) ( 2 3 1 4 ) i f ( z ) i i 2 、“，、“， 因为 熙瞀( 一- ) ) = 恕紫l i m ( m ，f ( _ ) ) = 0 且由( 2 3 1 3 ) 和 南 的有界性，可得 。l i m ( f ( 扩) 一f ( x 七) ，t 磨一- ) = 0 ， 因此。 l i ms u p ( f ( t 南) ，t 七一- ) l i r as u p ( f ( x 七) ，z 知一z ) = 一l i i n f ( f ( x 摩) ，虿一z 七) 0 当上面第二个不等式由( 2 3 1 1 ) 得出， 这样可得 i i f ( t 七) 一f ( 虿) l l 一0 ( 2 3 1 5 ) 第1 1 页，共3 7 页 由( 2 3 1 3 ) 和( 2 3 1 5 ) ，得 f i f ( x 七) 一f ( 习| | _ 0 ( 2 3 1 6 ) 由( 2 3 1 1 ) 和( 2 3 1 6 ) ，得 ( f ( 虿) ，z 一- ) 0 ，v 。x ， 所以虿s 第二种情况，l i m 奄。饥= 0 由吼在算法中的选取，可得 ( f ( 矿一孚r ( 矿) ) ，r ( 矿) ) ( 1 一盯) i i r ( z 七) 1 1 2 由一致连续性，有 0 ( 1 一盯) l i ms u pi i r ( x 七) 1 1 2 k - - - , o ( ) 则 1 i mi i r ( x 斥) f f = 0 下面的证明同上 接着，讨论s = o 如果l i m k 。i l 扩一x o l i o 。，则 h m 桫+ 1 一扩1 1 2 = 0 ， 这样每个弱收敛点都属于s ，矛盾 引理2 3 3 去掉了p s e u d o - d u n n 性质，是对引理2 3 2 的改进 引理2 3 3 假设算法2 2 1 产生的无限序列 扩】- 伪单调映射f 在x 一 致连续且有界，如果s d ，它的每个弱收敛点都属于s ；否则s = 谚，于是 l i m k 。i i x 七一x 0 l i = o 。 证明：由引理2 3 1 可得，第一种情况l i m k _ + o 。i i r ( x 知) 1 1 2 = 0 ，有 l i r a i n f 0 时，算法产生的迭代序列即可收敛到变分不等式的解 本章主要是将i - i e 3 0 二次投影算法中的阿米霍线性搜索方法及有利方向： d k = 叩k r ( z 庠，p ) + f ( y 詹) 运用于w a n g ，x i u 和z h a n g 的超梯度算法 3 2 新的超梯度算法 算法3 2 1 选择任意仃 o ，p ( 0 ，；1 ) 和，y ( 0 ，1 ) ， 第0 步选择x o k ，k = 0 ； 第k 步对扩k ，计算：= 玖( 一p f ( 扩) ) 如果盯( 矿，u ) l i = 0 ，停 止；否则，计算y 知：- - - ( 1 一吼) 矿+ y k z 七，其中讯= 7 舭，m k 是满足下式的最小 的非负整数m ( f ( x 七) 一f ( z 一，y m r ( z 知，肛) ) ，r ( x k ，p ) ) 盯l i r ( z ) 1 1 2( 3 2 3 ) 令z 岛+ 1 ：= 昂 n 哦n k ( z o ) ，其中 硪：= z r n l h k ( x ) o 】， ( 3 2 4 ) 磁= 【z 钟i ( z z ，z o z 七) o ) ( 3 2 5 ) 第1 4 页，共3 7 页 忍七( z ) ：= ( 叩七r ( z 知，肛) + f ( 3 ) ，z y 。) + 吼( 1 一讯) i l r ( z 奄，肛) 0 2 一p 啦( f ( z ? ) ，r ( x k , p ) ) ( 3 2 6 ) 引理3 2 1 ( 3 0 ，l e m m a2 1 】) 对任意z k ，都有 ( f ( z ) ，r ( x ，p ) ) p l l r ( x ，i , ) 1 1 2( 3 2 7 ) 引理3 2 2 ( 3 0 ，l e m m a2 2 】) 假设x 是变分不等式1 1 1 的解，映射h k ( x ) 由3 2 6 定义有h h ( x 七) 仇( 肛一o ) l l r ( z 七，p ) 1 1 2 且h k ( z + ) 0 引理3 2 3k 是有限维空间i 7 上的非空闭凸子集，f 是k 上连续伪单调 映射如果s 函，对任意七0 ，有s 磁n 磁n k 证明：由上面分析，可得对任意k 0 ，都有sc 磁 显然，sc 瑶= 形 假设任意矿sc 磁，由z 抖1 ：= b 瑶n 哦n k ( 护) ，可得 ( z + 一z 七+ 1 ，z o z 七+ 1 ) 盯i i r ( z b ，p ) i | 2 不等号两边同时取极限，得到l i m j 盯咿( z b ，肛) 1 1 2 0 则| i r ( - ) | | = 0 ，这 样虿为v i ( f , k 1 的解 第一种情况l i m j - o 。”( z b ，p ) 1 1 2 = 0 ，不难看出 x k j 的收敛点虿是 v i ( f , k ) 的解 现在，考虑v i ( f , k ) 的解集为空集的情况因为不等式序列硎扩一z o 腑为 递增序列，可知l i m k i i x 知一x o i l = 否则， 扩) 有界并且 l i m 桫+ 1 一剖2 ：0 由3 3 8 ，同上讨论结果相同，所有 扩) 的收敛点都为v i ( e k ) 的解，与 v i ( fk ) 的解集非空矛盾 定理3 3 1f 是在上连续伪单调映射假设 是算法3 3 1 产生的无 穷序列如果v i ( 只k ) 的解集非空，则 z 七) 收敛到v i ( 只k ) 的解z ，并且 x + = p s ( z o ) ；否则，l i m 忙七一x 0 | | = 。v i ( f , k ) 的解集为空当且仅当算 法产生的序列发散到无穷 证明：由引理3 3 1 ，假设扩收敛到x + s 令虿= p s ( z o ) ，贝0 虿s ，所以虿u 2n 月署nk 因为z 知+ 1 ：= p u ：n 日2 n k ( z o ) ，所以 i i z 七+ 1 一扩l | j i 虿一z o l l 所以 i | z 知+ 1 一虿i i i | z 惫+ 1 一x o i i + l i 扩一虿0 + 2 ( z + 1 一z o ，x 0 一虿) 2 i i z o 一虿| i + 2 ( z 七+ 1 一z o ，z o 一动 第1 7 页，共3 7 页 = 2 伍+ 1 一虿，z o 一) 因此， l i r a s u p | | z 七+ 1 一_ i l 2 ( z + 一- ，z o 一_ ) k - - - * o o 因为z = e s ( z o ) 和矿s ，所以有引理1 2 。1 f f z + 一万| | ( z 一_ x o 一_ ) 0 ， 所以 虿= z = p s ( x o ) ， 因此p s ( x o ) 是 一) 唯一收敛点 s = d 的情况，结论由引理3 3 1 可得 3 4 实验数据 本节将实例论证改进的算法能有效地减少迭代次数和c p u 使用时 间用m a t l a b 作为分析工具，求解变分不等式问题，并比较算法3 3 1 和【1 】a l g o r i t h m3 1 】 例3 4 1 选取从p a n g 和g a b r i e l 3 4 ，m a n g a s a r i a n 和s o l o d o v 【3 5 ，k a n z o n 3 6 】的非线性互补问题的与四个变量相关的映射f 令 f ( x l ，x 2 ，x 3 ，x 4 ) = 3 z ；+ 2 x l x 2 + 2 x ；+ x 3 + 3 x 4 6 2 z + x l + + l o x s + 2 x 4 2 3 z ；+ z ；十2 x ；+ 2 x s + 9 x a 一9 碹+ 3 z ；+ 3 x 3 + 3 x 4 3 可行域为x = z 群i x i + x 2 + x 3 + + z 佗= 佗) 算法3 3 。1 应用到v i ( f ，x ) 问题的初始点为z o = ( 1 ，2 ，0 ，1 ) ，序列收敛到 变分不等式的解z + = ( 0 ，4 ，0 ，o ) ，迭代在1 3 步后终止 表3 - 1 呈现了i i z 。一x o i i ，i i 一矿| i 和i i r ( x 七，p ) i | 的每一步迭代的数据结 果选取i i r ( x ，弘) 0 1 0 7 作为终j k r - j 限选取常数7 = 0 5 ，仃= 4 和p = 0 2 第1 8 页，共3 7 页 表3 1 一一一 ! 渺一z o i f缈一z + l i m ，u ) l l 一一 00 2 4 4 9 5 0 9 0 9 2 1 0 7 8 9 8 2 1 7 1 7 8 3 2 2 0 4 6 4 2 4 0 1 8 5 2 4 4 0 0 6 2 4 4 7 6 7 2 4 4 9 1 82 4 4 9 7 9 2 4 4 9 5 1 0 2 4 4 9 5 1 1 2 4 4 9 5 1 2 2 4 4 9 5 2 3 3 2 2 0 9 0 5 4 0 2 8 5 1 0 0 5 5 2 0 0 1 1 0 0 0 0 2 2 1 1 4 8 3 0 7 3 3 0 0 2 8 5 1 0 0 5 5 2 0 0 1 1 0 0 0 0 2 2 4 3 9 0 7 x1 0 4 4 3 9 0 7 x1 0 4 8 7 8 1 0 x1 0 5 8 7 8 1 0 x1 0 5 1 7 5 6 2 x1 0 5 1 7 5 6 2 x1 0 5 3 5 1 2 4 x1 0 6 3 5 1 2 4 1 0 6 7 0 2 4 7 x1 0 7 7 0 2 4 7 1 0 7 1 4 0 4 9 x1 0 7 1 4 0 4 9 x1 0 7 1 3 2 4 4 9 5 2 0 8 9 9 x1 0 8 2 0 8 9 9 x1 0 8 一 例3 4 2 本例来源【3 7 ，当 f ( z ) = f 1 ( z ) + f 2 ( z ) ， 日( z ) = ( ( z ) ，y 2 ( z ) ，厶( z ) ) ， b ( z ) = d x + c ， 五( z ) = 2 1 + 巧2 + x i 一1 z i + z i z i + 1 ， i ：1 ，2 ，凡， z o = z ，善+ 1 = 0 ， d 为非对称矩阵 第1 9 页，共3 7 页 d = 4 2 14 2 14 2 4 2 14 c = ( 一1 ，一1 ，一1 ) ? 为一向量可行域为k = 1 b ，u 6 ，当i b = ( 0 ，0 ，o ) t 和i b = ( 1 ，1 ，1 ) t ，选取忪( 扩) 1 1 2 1 0 6 作为终止门限用1 1 f 表示选取f 的全部迭代次数取7 = 0 5 ，盯= 9 和肛= 0 1 选取初始点x o = ( 0 ，0 ，o ) t 和z o = ( 1 ，1 ，1 ) ? 分别当n = 5 和n = 1 0 时；【 1 a l g o r i t h m3 1 】盯= 0 5 ， ，y = 0 8 表3 - 2 呈现了算法3 3 1 和 1 】a l g o r i t h m3 1 】的数据比较 表3 - 2 第2 0 页，共3 7 页 第四章变分不等式的一种新有利方向的投影算法 4 1问题来源 l i 2 9 】提出了一种新的变分不等式算法：初始点x o 舻，- y ( 0 ，2 ) ，0 ( 0 ，2 ) ， 砂= r x k _ p ；r ( z ，风) 】，当口；= 1 - 金 z 缸 1 = f k z 七一一y ( z 南一砂) 】， = 毪辫 并证明当f 具有余强制性质时，r ( 扩，成) 和x 一砂都为有利方向，且算法全 局收敛 y a h ，h a n 和s u n 2 1 对l i 2 9 1 提出的算法作了改进：初始点护k ，7 ( 0 ，2 ) ，0 ( 0 ，2 ) ， 砂= r x k _ 9 q ；r ( z 七，仇) ，当口；= 1 一笔 x 十1 = f k i x