（基础数学专业论文）变分不等式的算法及其扰动分析.pdf

变分不等式的算法及其扰动分析 基础数学 研究生邱涛指导教师何诣然教授 论文摘要：本文主要讨论变分不等式的算法及其扰动分析变分不等式的投影 算法被学者广泛研究而二次投影算法是最有效的投影算法之一对于投影算 法，投影运算非常重要但在实际数值运算中，投影运算并不能精确求解因 此我们证明经小扰动后的二次投影算法有意义且所产生的序列仍然收敛到 变分不等式的解为了讨论近似点算法所产生迭代序列的收敛性，s o l o d o v 和 s v a i t e r 针对极大单调算子提出了混合近似点算法，本文第三部分将混合近似点 算法推广到具有伪单调映射的变分不等式问题，同时也分析了扰动后的混合近 似点算法所产生的序列仍然收敛到变分不等式的解近似点算法中的子问题求 解很少有学者关注，本文第四部分利用二次投影算法的思想来讨论近似点算法 子问题解的算法 关键词：变分不等式；近似点算法；近似点算法的子问题；混合近似点算 法；投影算法；扰动 第i 页，共2 5 页 t h es o l u t i o no fv a r i a t i o n a li n e q u a l i t yp r o b l e ma n d p e r t u r b a t i o na n a l y s i so fp r o j e c t i o na l g o r i t h m m a j o r ：p u r em a t h e m a t i c s p o s t g r a d u a t e ：q i ut a os u p e r v i s o r ：h ey i - r a n a b s t r a c t ：t h i sp a p e rm a i n l ys t u d i e st h ea l g o r i t h m sf o rv a r i a t i o n a l i n e q u a l i t yp r o b l e ma n dp e r t u r b a t i o na n a l y s i so fp r o j e c t i o na l g o r i t h m s p r o j e c t i o na l g o r i t h m sf o r v a r i a t i o n a li n e q u a l i t i e sh a v e b e e ne x t e n s i v e l y s t u d i e d a tp r e s e n t ，d o u b l ep r o j e c t i o na l g o r i t h mi so n eo ft h em o s te f f e c t i v e m e t h o do fp r o j e c t i o na l g o r i t h m s p r o j e c t i o no p e r a t i o ni sv e r yi m p o r t a n tt o p r o j e c t i o na l g o r i t h m s f r e q u e n t l y , p r o j e c t i o no p e r a t i o na l eu n a b l et os o l v e e x a c t l y s ow ep r o v et h a tt h ed o u b l ep r o j e c t i o na l g o r i t h ma f t e rp e r t u r b a t i o n i sw e l l d e f i n e da n dt h eg e n e r a t e ds e q u e n c ec o n v e r g e st oas o l u t i o n s o l o d o v a n ds v a i t e rp r o p o s ea h y b r i dp r o j e c t i o n p r o x i m a lp o i n ta l g o r i t h mf o rf i n d i n g z e r o so fam a x i m a lm o n o t o n eo p e r a t o r i nt h et h i r dp a r to ft h i sp a p e r ， w eu s eh y b r i dp r o j e c t i o n - p r o x i m a la l g o r i t h mt os o l v ev a r i a t i o n a li n e q u a l i t y p r o b l e mw i t hp s e u d o - m o n o t o n em a p p i n g ；a n dp r o v et h a tt h ei t e r a t es e q u e n c e p r o d u c e db yh y b r i dp r o j e c t i o n - p r o x i m a lp o i n ta l g o r i t h mw i t hp e r t u r b a t i o n i sc o n v e r g e n t af e ! wr e s e a r c h e r sc o n c e r n e dt h es u b p r o b l e mo fp r o x i m a lp o i n t a l g o r i t h m i nt h el a s tp a r t ，u s i n gt h ei d e ao fd o u b l ep r o j e c t i o nm e t h o d ，w e p r o p o s eam e t h o df o rs o l v i n gi t k e yw o r d s ： v a r i a t i o n a l i n e q u a l i t y ；p r o x i m a lp o i n ta l g o r i t h m ；s u b - p r o b l e mo fp r o x i m a lp o i n ta l g o r i t h m ；h y b r i dp r o x i m a lp o i n ta l g o r i t h m ； p r o j e c t i o na l g o r i t h m ；p e r t u r b a t i o n 四川师范大学学位论文独创性及 使用授权声明 本入声明：所呈交学位论文，是本人在导师隼选煞指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外， 本论文不含任何其他个人或集体已经发表或撰写过的作品或成 果。对本文的研究做出重要贡献的个人和集体，均已在文中以明 确方式标明。本声明的法律结果由本人承担。 本人承诺：已提交的学位论文电子版与论文纸本的内容一致。 如因不符而引起的学术声誉上的损失由本人自负。 本人同意所撰写学位论文的使用授权遵照学校的管理规定： 学校作为申请学位的条件之一，学位论文著作权拥有者须授权 所在大学拥有学位论文的部分使用权，即：1 ) 已获学位的研究生 必须按学校规定提交印刷版和电子版学位论文，可以将学位论文 的全部或部分内容编入有关数据库供检索；2 ) 为教学、科研和学 术交流目的，学校可以将公开的学位论文或解密后的学位论文作 为资料在图书馆、资料室等场所或在有关网络上供阅读、浏览。 本人授权中国科学技术信息研究所将本学位论文收录到中 国学位论文全文数据库，并通过网络向社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：砷涛 签字日期：为如年年月7 e 1 导师躲铴。枷坯 黼期辨乎月7 目 引言 变分不等式是当今非线性分析与数学规划的重要组成部分它在工程力学、微 分方程、控制论、数理经济、经济平衡理论、对策理论等方面都有重要应用由 于各应用领域要求计算变分不等式的近似解，变分不等式解的迭代算法被学者广泛 研究变分不等式解的迭代算法是变分不等式理论发展的一个不可或缺的重要研究 分支 变分不等式解的迭代算法主要有牛顿算法、近似点算法、投影算法等等不 同的算法要求映射具有相应的性质例如，牛顿算法要求其中的映射具有光滑性， 而且映射的导数是非退化的近似点算法要求映射是极大单调的投影算法要求 映射是连续的但不必具有单调性投影算法执行起来更容易，适用范围更广投影 算法最早起源于g m k o r p e l e v i c h 在1 9 7 6 年文章【1 3 】中提出的超梯度算法1 9 8 7 年 k h o b o t o v 【1 2 1 和1 9 9 1 年m a r c o t t e 【1 4 1 进一步发展了超梯度算法。1 9 9 9 年s o l o d o v 和 s v a i t e r 提出了超平面投影算法，这一算法也n - 次投影算法 2 5 】2 0 0 6 年y i r a n h e 在s o l o d o v 和s v a i t e r 的基础上提出了修改了的二次投影算法 1 1 1 目前最有效的 投影算法是二次投影算法，它比超梯度算法效率更高要求的条件更弱二次投影算 法不要求其中的映射是l i p s c h i t z 连续的，而且针对一些典型问题，它的测试结果让 人满意投影运算对于二次投影算法是非常重要的一般的说来，每一次投影就是 一个凸规划问题因为实际上投影运算并不能精确求解，所以我们有必要研究这种 不精确是否影响算法的收敛性对于近似点算法，一些学者已经研究了近似点子问 题非精确求解时算法的收敛性 2 3 】我们讨论二次投影算法中关键的投影运算非精 确求解时的情况 近似点算法和二次投影算法都可以求解变分不等式问题，那经过适当组合 的混合近似点算法是否也可以解决变分不等式问题呢? 1 9 9 9 年m v s o l o d o v 和 b f s v a i t e r 2 6 】提出了混合近似点算法并用它求解极大单调问题本文在有限维空 间中证明混合近似点算法是可以求解变分不等式问题的同时由于算法中的第二 步涉及到投影运算，而投影运算在计算过程中常常不能精确求解，所以我们有必要 证明在添加某种意义的扰动下，混合近似点算法依然收敛到问题的解我们第三章 第1 页，共2 5 页 引言 就讨论了混合近似点算法求解变分不等式，以及它的扰动分析 近似点算法，见【7 ，1 5 ，2 3 】，是求解极大单调算子t ( z ) 零点的经典方法日是实 的希尔伯特空间，kch 是闭凸集特别地，给出护k ，且z k p 0 ，新的迭 代x k + 1 k 由下列近似点算法产生： ( p j p a ) 0 p k t ( x ) + ( z x k ) 为了得到新的迭代x k + l ，我们常常需要解决变分不等式考虑 t ( z ) ：= f ( x ) + n k ( 。) ，( m 1 ) 其中n k ( x ) 是k 的法锥，也就是说， t 坛：p 凹：( x t - - x ，z 坯0 ，虮研如果蚝瓦 id 其他 则，近似点算法( p p a ) 的子问题等价于下面变分不等式问题：找z k 使得， ( z 7 一z ，z z 七+ 段f ( z ) ) 0 ， vx k ( 0 - 2 ) 近似点算法的子问题很少有学者关注，2 0 0 3 年韩德仁利用牛顿算法求解了近似点算 法的子问题 8 】我们将在第四章利用二次投影算法的思想来讨论近似点算法的子 问题 第2 页，共2 5 页 第一章预备知识 1 1 常用记号 c 是形空间中的非空的闭凸集，f ：舻- 形是连续映射，”fj 和( ，) 分别 按舻中通常的范数和内积定义 f 在c 上伪单调，即对任意z l ，z 2 c ， ( f ( x 1 ) ，x 2 一x 1 ) 0 兮( f ( z 2 ) ，x 2 一z 1 ) 0 ( 1 1 1 ) z 舻到c 上的投影定义为： 尸匆( z ) ：= a r g m i n l l y z | | ly c ) ， d ( x ，k ) 是z 到k 的距离： d ( x ，k ) ：= m 西z | | z 一耖| | i y k ) 剩余函数： e ( p ，p ) ：= p p c ( p p f ( 肛) ) 其中弘舻，p 0 当p = 1 时， e 似，1 ) ：= p 一。r 一f ( p ) ) 记e ( p ，1 ) = r ( p ) 1 2 基本知识 定义1 2 1 ：假设cc 舻是非空闭凸子集，变分不等式问题( 简记为： p ( a f ) ) 是指：找z c 使得， ( f ( x ) ，y 一矿) 0 ，对所有的y c 成立 用s o l ( c ，f ) 表示变分不等式的解集本文总假设s o l ( c , f ) 毋 引理1 2 1 ：x ，y r n ，z c 下列不等式成立： ( 1 ) ( p i c ( o ) 一z ，名一户a ( z ) ) o ； ( 2 ) ( p c ( x ) 一忍( y ) ，z y ) 0 ； ( 3 ) 1 1 助( z ) 一p c ( y ) l l i | z 一i l ； 第3 页洪2 5 页 第一章预备知识 ( 4 ) i i p c ( x ) 一2 1 1 2si i z z i l 2 一l i p c ( x ) 一z | 1 2 弓l 理1 2 2 ：厉= p 寥( z ) ，z + c ，贝! f l l 牙一z 1 1 2 i i z z 1 1 2 一i l z 一牙1 1 2 证明：因为1 1 2 一z ”2 = i z 一牙f f 2 + | | 叠一z i 2 + 2 ( x 一童，牙一z ) 且由引 理1 2 1 知仕一牙，牙一矿) 0 可以得到结论 弓f 理1 2 3 ：( f ( z ) ，r ( 。) ) i i r ( x ) 1 1 2 ， 比c 证明：因为r ( z ) = z p c ( z f ( z ) 即z r ( z ) = r 一f ( z ) 所以 ( z f ( x ) 一( z r ( z ) ) ，y 一( z 一7 _ ( z ) ) ) 0 ，v y a 特别地，取y = z ，则可以得到结论 引理1 2 4 ：( 见 1 1 j ) 设c 是舻中的非空闭凸集，九是上的实值函数， k ：= z c ：危( z ) o 如果k d ，h 在c 上满足利普希茨条件，设l 为利普希茨常数( vz ，y c ， lh ( x ) 一h ( y ) i l iz 一可i ) ，则 d ( x ，田l m a x h ( x ) ，o ，比a 证明：当z k 时，d ( x ，k ) = 0 ， ( z ) 0 ，故d ( x ，k ) l m a x h ( x ) ，o ) z c k 时，因为k 是闭集，所以存在y ( x ) k 满足i i x 一训= d ( z ，k ) 由h n 普 希茨连续，有 0 ( z ) 一九( 可( z ) ) 05l i i = 一掣( z ) i i = l d ( x ，影) 因为zgk ，y ( x ) k ，贝u ( z ) 0 ，九( 可( z ) ) 0 所以 危( z ) s ( z ) 一九( ( z ) ) = i 九( z ) 一 ( 耖( z ) ) i l d ( x ，k ) 结论得证 引理1 2 5 ：( 见【1 】) 序列【0 i ) r ，i n ，i o + 且 尻) 见p ，满足 f 魂 0 ， 第4 页，共2 5 页 第一章预备知识 存在充l ，当如 z 知。时，o z 。+ s 取而 m a x k 1 ，k 2 当五 坛时， 对e 0 ，存在昆2 ，当鬼 k 2 时，e 而 0 所以口f 交换五和如的位置，可得v 专 所以t ，= f 证毕 引理1 2 6 ：设 0 ，v i p ( c , f ) 的解集s o l ( c , f ) 与r ) 的零点组成的集合 是一致的即是说，z + 是p ( c ，f ) 的解当且仅当矿= f b p p f ) 】 引理1 2 7 ：( 2 】) 设u r n ， p 0 ，有下式成立： i l e ( u ，y ) i i i l e ( i t ，p ) i | ( 1 2 3 ) 第5 页，共2 5 页 第二章二次投影映射的扰动分析 2 1 问题来源及解决方法 c 是舻空间中的非空的闭凸集，f ：r n 一即是连续映射，i i i l 和( ，) 分 别按舻中通常的范数和内积定义v r p ( gf ) 的解集为s o l ( c ，f ) 变分不等式是 一类非常重要的非线性问题，产生于许多不同的领域，如物理学，工程学和金融管 理科学等等变分不等式问题己引起广泛关注，有兴趣的读者可以阅读相关文章 4 娟，9 】 针对变分不等式问题的投影算法被国内外学者广泛研究，这类算法要求计 算到闭凸集上的投影，比如近似点算法，超梯度算法，二次投影算法等，参见 【1 3 ，2 4 ，2 9 ，3 0 】其中，二次投影算法是一种非常有效的投影型算法【2 5 】对于求解 变分不等式的投影算法，投影运算非常重要一般的说来，每一次投影就是一个凸 规划问题因为实际上投影运算并不能精确求解，所以我们有必要研究这种不精确 是否影响算法的收敛性对于近似点算法，一些学者已经研究了近似点子问题非精 确求解时算法的收敛性f 2 3 】接下来我们讨论二次投影算法中关键的投影运算非精 确求解时的情况 本章假设f 在c 上是伪单调的 2 2 主要结论 算法2 2 1 ：选取6 0 ，x 0 c ，参数仃 0 ，y ( 0 ，1 ) ，i y , o 开始取 第一步：计算r ( ) ，如果l | r ( ) i i 艿，那么停止否则执行第二步 第二步：找出满足下列式子的最小正整数， ( f ( x 一，y r ( z ) ) 一f ( z ) ，r ( z ) ) 一仃l l r ( x ) 1 1 2 ( 2 2 1 ) 第三步：假设臻= 7 ，z = 一r l i r ( x ) 第四步：x i + 1 = ( ) + 其中 ：= z c ：( f ( 名。) ，z 一矿) o ) ( 2 2 2 ) 其中咿| j o o 让i = i + 1 再回到第一步 引理2 2 1 ：z s o l ( c ，f ) ， ) 是由算法2 2 1 产生，则 第6 页，共2 5 页 第二章二次投影映射的扰动分析 ( 1 ) i i x 一z + l f 收敛，进一步 ) 有界 ( 2 ) 1 1 + 1 一l i 收敛到0 证明：( 1 ) 在引理1 2 1 ( 3 ) 中，用甄代替c ，代替z ，z + 代替y ，得到 l l 讼；( ) 一淼。( z + ) l lsi i z 。一z + l | 因为( ) = + 1 一，吼( 矿) = 矿( 因为矿甄) 所以 l l z + 1 一一z l l l i x 一z l i 又 i i x + 1 一z 0 一i i e i | si i x + 1 一一z l l ， 所以 0 z + 1 一z 0si l 一z + l i4 - i i | i 因为三咿i i o 。，所以由引理1 2 5 知恕i p 一矿。存在，令 1 i m | | 矿一z i l = p ， 进而 ) 有界 ( 2 ) 在引理1 2 1 ( 4 ) 中，用硒代替c ，代替z ，矿代替z ，得到 0 p 配( z ) 一z 1 1 2 | i 一z 1 1 2 一i i x 一户砭( 。) 1 1 2 即 i i 尸k ) 一1 1 2 l i x 一z + 1 1 2 一i i p k , ( x ) 一z 1 1 2 又p 酸( z ) = + 1 一，所以 i i x + 1 一z 一| 0 2 i i x 一z + 1 1 2 一l i x 件1 一z 一1 1 2 = i t x 一。 2 一( i z + 1 一z + 1 2 + l i e 0 2 2 ( x + 1 一z ，) ) = i i x 一z j | 2 一l i x 件1 一z + 1 1 2 一l i c f 1 2 + 2 x 件1 一z + ，) ， 由于i - - - 0l 妒l l 6 ( 否则程序停止) ，从而存在非负的整数k i 满足( 2 2 1 ) j f ( z ) ：= ( f ( z 。) ，z 一矿) 假设矿s o l ( c ，f ) ，算法2 2 1 产生了一个无限序列 特别地忪( ) i i 6 ，v i c 是上闭凸集，( z ) 是上的实值函数由矿s o l ( c ，f ) ，f 伪单调，知 ( f ( 名。) ，矿一矿) 0 故k d 易知， ) 在c 上满足利普希茨条件，不防假设利普希茨常数为p ，则由 引理1 2 4 ， d ( x 。，甬毛) 口一1 m a x f ( z 。) ，z 。一z 。) ，o ) ，v z k 从而有， d ( x 。，k ) 8 - 1 ( f ( 矿) ，矿一名。) ( 2 2 3 ) 由( 2 2 1 ) 知( f ( ) ，r ( ) ) 一盯 ( ) 1 1 2 + f ( x ) ，r ( ) ) 又z = 一r i i r ( x ) ，故 ( f ( z ) ，一z ) 一仃仇l l r ( ) 1 1 2 + 讯( f ( ) ，r ( ) ) 一哪f | ( r ( ) 1 1 2 + l d l r ( x ) 1 1 2 ( 1 一仃) 仇j j r ( ) 1 1 2 从而有下式成立， d ( 。，j 矗) 8 - 1 ( 1 一盯) 琅0 r ( z ) 1 1 2 第8 页，共2 5 页 第二章二次投影映射的扰动分析 而 d ( x 2 ，j 厶) = l | z + 1 一一z i i 0 ，则存在j ，蜘7 ) = 0 因为 ) 有界，故存 在j zi j ，1 i m = 矿因为7 连续所以r + ) = 0 由l p 一矿i f 收敛 l _ 和1 i mz = 2 。，i f 知j i mz = z ，i n t - - * 0 0l + o 。 ( i i ) 如果l i m s u p 仇= 0 ，i e 1 i m 聊= 0 】有界设矿是 ) 的一个聚点 从而存在 ) 的子序列 ) 收敛到矿 0 口l | r ( z 巧) 1 1 2 0 ，t ( z ) 是极大单调算子 因为求解( 3 1 1 ) 和求解t ) 零点的难度不相上下所以非精确近似点算法的各种 形式就出现了，见 2 ，1 0 ，1 6 2 1 ，2 1 - 2 3 ，2 7 ，2 8 x k c ，觑 0 ，磊和e k 满足下列 等式 z 七+ e k = 玩+ & t ( s k ) ( 3 1 2 ) 其中 七】- 是误差序列常常我们让0 扩i i v 七l l = 七一砂m 非精确近似点算法建立起 一个超平面，它将当前迭代与变分不等式问题的解严格分离开来接下来的迭代由 当前迭代投影到超平面投影步骤保证了迭代序列的收敛性我们在= 0 的情况 下再来说明一下我们的方法此时，d k = 。_ i c 一砂， ( d k ，z 詹牙七) = | | z 庇一叠惫1 1 2 0 ( 3 1 3 ) 等式右边在= 矿时等于0 ，但此时x k 是问题的解而矿c + ， ( d k ，z 七一牙七) 一( 凤f ( 量七) ，z 一孟七) 0 ( 3 1 4 ) 故 h k ：= z r n l ( d k ，z 一牙七) o ) ( 3 1 5 ) 第1 0 页，共2 5 页 第三章混合近似点算法求解变分不等式 严格地将z k 与解分离开来再由z 七+ 1 = p c n 凰( 舻) 产生下一步迭代，并保证序列 的收敛性 3 2 主要结论 算法3 2 1 ：选取卢 0 ，l ，( 0 ，1 ) ，x o c 和k = o ( k = 0 ，1 ，2 ，3 ) ， 如果一量s o l ( c ，f ) 第一步：c ，选取凤【p ，+ ) 和v k 【0 ，叫找出妒和驴，满足下列式 子： ( z 7 一孟蠡，牙七一z 惫+ 风f ( 牙七) 一e 知) 芝0 ， vx 7 c ( 3 2 6 ) 0 8 v k l l x 七一妒| i 第二步：让z 七十1 = p c n 风( 一) 其中d i , = 一护+ 矿 三k ：= x r 1 i ( d k ，z 一孟知) o ) 说明：算法1 的第二步是有意义的设x c ，则 ( f ( x 4 ) ，y 一矿) 0 ，v y c 由f 伪单调知 ( f ( 矽) ，y z + ) 0 ，v y q 取y = 妒，则 ( f ( 牙七) ，牙惫一z 。) 0 ， 即 ( f ( 牙詹) ，z + 一牙七) 0 由( 3 2 9 ) ， ( z 七一孟七+ 8 k , z 7 一牙知) ( 玩f ( 牙七) ，z 7 一牙奄) ， vz c 取= 矿，则 ( z 七一牙七+ e 七，z + 一牙知) ( p k f ( 牙知) ，z 一牙七) ， 从而 ( d k ，矿一牙知) 0 第1 1 页，共2 5 页 ( 3 2 7 ) ( 3 2 8 ) 第三章混合近似点算法求解变分不等式 所以矿凰故cn 矾d 又c 是闭凸集，易知凰也是闭凸集，所以cn 矾 是非空的闭凸集 引理3 2 1 ：c ，凤 0 和0 v k 移 0 ，v x 0 c ，存 在u k 使得s o l ( b f + i x 0 ，k ) 非空此结论等价于证明，存在让c ，满足 ( + j 3 f ( u ) z o ，y t 正) 0 ，vy d 令 g ( u ) ：= u c i ( u + z f ( u ) 一x 0 ，y u ) o ) 则g 是k k m 映射且g ( 耖) 是闭集设牙6 s o l ( f k ) ，则 ( f ( 至) ，y 一面) 20 ，vy c 如果乱g ( 牙) ，贝u 0 ( 让+ z f ( u ) 一z 0 ，牙一t ) = ( 缸一z 0 ，牙一u ) + ( p f ( u ) ，牙一让) ( 牡一2 7 0 ，牙一u ) 所以g ( 牙) 有界故s o l ( p f + i x 0 ，k ) 非空从而( 3 2 6 ) 和( 3 2 7 ) 至少有一 组精确解 引理3 2 2 ：z + s o l ( c ，f ) ， 矿) 由算法3 2 1 产生，则 ( 1 ) f i x 知一z + | l 收敛，进一步 舻) 有界 ( 2 ) l l x 奄+ 1 一j j 收敛到0 证明：记c k ：- - cni l k ，在引理1 2 1 ( 4 ) 中，用仅代替c ，代替z ，z 代 替名，得到 l l 户反( z 凫) 一z + 0 2 l i z 七一z + 0 2 一i i p c 。( x 七) 一z 七1 1 2 又f ( z 知) = z 南+ 1 ，所以 i l z 南+ 1 一z + f 1 2 | | z 七一z + 0 2 一l j z 七十1 一z 七1 1 2 故l l 一z 4 l l 收敛， 扩) 有界。l i mi i z 知+ 1 一一0 = 0 尤。 第1 2 页，共2 5 页 第三章混合近似点算法求解变分不等式 引理3 2 3 ： z 知) 和扩是由算法3 2 1 产生，则i i 砂一扩i | 收敛到0 ，d k 收敛到0 证明：c k = z c l 0 引理3 2 4 ：矿s o l ( c ，f ) ，【z 南) 是由算法3 2 2 产生，| i 驴i i o 。，则 ( i ) l l x 知一矿l | 收敛，进一步 舻) 有界 ( 2 ) h x 磨j r l 一x k | i 收敛到0 证明：( 1 ) 在引理l 。2 。1 ( 3 ) 中，用q 代替a 代替而z + 代替y ，得到 1 1 只巩( z 七) 一只氕( z 。) i i i i x 七一z l i 因为舷( ) = x k + 1 一驴，( z ) = z + ( 矿c k ) 所以 j j z 七+ 1 6 七一z + j j j j z 七一z 玑 又l l z 奄+ 1 一z l l l 陋七i l l i z 知+ 1 一j k z + 1 1 所以l l z k + 1 一z + l l 1 l z k z + l l + 1 1 6 k 1 1 又 因为妻i妒0oo，所以由引理324知拄怂ixk-x*ii存在，令兰恐l|xk-x*k 02p = o 冗+ u u ，u u 进而 z 七) 有界 ( 2 ) 在引理1 2 1 ( 4 ) 中，用g 代替c ，代替z ，z f 替名，得到 0 p & ( z 七) 一z 1 1 2 l i z 七一z 1 1 2 0 z 七一p c 。( x 七) 1 1 2 即 i i p c 。( = 蠹) 一z 奄0 2 i i z 鸯一z + f 1 2 一1 1 只久( z 七) 一2 1 1 2 第1 4 页，共2 5 页 第三章混合近似点算法求解变分不等式 又魄( 扩) = x 七+ 1 一胪，所以 i i z 奄+ 1 一z 是一6 1 1 2 | l z 一。+ 1 1 2 一l l z 蠢+ 1 一z 幸一6 奄1 1 2 = j j z 知一z i j 2 一( ij z 知+ 1 一z + j 1 2 + i j 6 惫| j 2 2 ( z 七+ 1 一z 幸，6 七) ) = i l z 一z 1 1 2 0 z + 1 一z 1 1 2 一l | 6 凫1 1 2 + 2 ( z 凳+ 1 z ，6 奄) 由于ei i 胪l i 0 ，新的迭代z 七+ 1 k 由下列近似 点算法产生： ( p p a ) 0 反r 0 ) + ( x z 鸯) 为了得到新的迭代x k + l ，我们常常需要解决变分不等式考虑 t ( x ) ：= f ( x ) + 慨( z ) ，( 4 1 1 ) 其中n k 江) 是x 的法锥，也就是说， 坛：卜邮： x t - - x ，z ) 0 ，( 0 ，1 ) ，g ( x o ) c 且k = 0 k = 0 ，l ， 如果9 ( 扩) 譬s o l ( c , f ) 运行第一步： 第一步：g ( x 七) c ，选取觑归，+ 。o ) ，魄【0 ，| ，) ，9 ( 妒) 和满足： 夕( 孟七) c ，( 夕( z 7 ) 一9 ( 童七) ，9 ( 童七) 一9 ( z 七) + 卢 ：f ( 孟知) 一七) 0 ，v g ( x 7 ) d ( 4 1 3 ) 第二步：令 l i e 血0 v k l l g ( x 知) 一9 ( 砂) 1 1 ( 4 1 4 ) 夕( 厉七) = p c k q ( x 七) 一口七凤f ( 岔知) 】( 4 1 5 ) 第1 6 页，共2 5 页 第四章近似点算法的子问题 其中 一绁铲 ( 4 邶) d k = 9 ( 。七) 一夕( 圣七) + 磨( 4 1 7 ) 第三步：丁 0 ，新的迭代夕( z 七+ 1 ( 7 ) ) 定义为 夕( z 詹+ 1 ( 丁) ) = p c l q ( z 七) 一r ( 夕( z 蠡) 一9 ( 牙七) ) 】( 4 1 8 ) 本算法最主要的步骤就是找出9 ( 妒) 和扩满足( 4 1 3 ) 和( 4 1 4 ) 引理4 1 1 ：给出一日：g ( x 七) c ，凤 0 ，0 0 ， 因为 l l i m9 ( 孟2 ) = 9 ( z ! 麦乞) ， 在经过有限步的内部迭代后，程序将产生一个夕( 牙) 幻( ) ) ，满足( 4 1 9 ) ， 夕( 牙) 。p b b ( z 七) 一觑f ( 牙) 】( 4 1 1 1 ) 且 凤| | f ( 牙) 一f ( a 一1 囟( z k ) 一凤f ( 孟) 】) ) l i 魄1 1 9 ( z 惫) 一忍b ( z 七) 一厥f ( 牙) 川 ( 4 1 1 2 ) 上面的不等式成立是因为( 4 1 1 2 ) 的左边无限接近于o 时右边无限接近 于魄( 护) 一9 ( z ) 1 1 2 0 我们如此定义9 ( 砂) 和一 夕( 童七) ：= 而b ( z 七) 一觑f ) 】 第1 7 页，共2 5 页 第四章近似点算法的子问题 产：= 反i f ( 童蠢) 一f ) 】 由( 4 1 1 1 ) 和( 4 1 1 2 ) ，我们有 9 ( 童七) = p c b ( x ) 一风f ( 孟) 】= p c q ( x 七) 一凤f ( 孟七) + 詹】 = k l l g ( x 七) 一夕( 矿) 1 1 这样的夕( 砂) 和矿就是我们所要找的 细心的读者可能已经注意到在引理4 1 1 中很关键的一步，求解( 4 1 1 0 ) 的任何 一个迭代算法都会产生一个序列9 ( ) 收敛到a ( x ：扬) 本文章就是要具体的给出 算法求解( 4 1 1 0 ) 然而我们知道在g = ，( 恒等映射) 的情况下，算法4 1 1 可以写成： 算法4 1 2 ：设p 0 ，l ，( 0 ，1 ) ，z o c _ f t 凫= 0 k = 0 ，1 ，如果岳c ， 运行第一步： 第一步：扩c ，选取觑归，+ o 。) ，【o ，p ) ，砂和扩满足： 孟七g( z 一面七，叠七一z 七十房b f ( 童七) 一七) 0 ， v 。7 g ( 4 1 1 3 ) 第二步：令 其中 妒i l 魄忙七一铲l i ( 4 1 1 4 ) z 毒+ 1 = 圣凳= 忍k 七一a 七凤f ( 牙露) j ( 4 1 1 5 ) q 七= 譬 d k = z 七一童知+ e 七 引理4 ，1 ，1 可以写成 引理4 1 2 给出矿c ，反 0 ，0 0 ，z o c ，参数盯 0 ，7 ( 0 ，1 ) ，i 从0 开始取 第一步：计算危( z o ) ，如果i i h ( x o ) 0 = 0 ，那么停止否则执行第二步 第二步：找出满足下列式子的最小正整数， ( f ( z 一7 危( z ) ) 一z + z ，危( z ) ) a l l h ( x ) 1 1 2 ( 4 2 2 0 ) 第1 9 页，共2 5 页 第四章近似点算法的子问题 第三步：假设吼= ，= 一臻九( ) 第四步：z 件1 = p c , ( 一) 其中 c 毛：= z c ：( f ( z ) 一z + z ，z z ) o ) ( 4 2 2 1 ) 让i = i + 1 再回到第一步 定理4 2 1 ：如果飑c 止连续且单调，则算法4 2 1 在有限步迭代后终止或产 生一个无限序列收敛到( 4 1 1 8 ) 的解 证明：算法1 的第二步是有意义的因为7 ( 0 ，1 ) ，f 连续，随趋近于。， ( f ( x 一，y 缸h ( x ) ) 一名+ ，h ( x ) ) 趋近于 ( f ( z ) 一z + z 。，h ( x 。) ) 因为h ( x ) ：= 二尼( 2 一f ( x i ) ) ，所以 q f ( x ) 一+ 危( ) ，矽一+ h ( x ) ) 0 ，v y c 取y = ，有 ( f ( x ) 一z + z ，危( 。) ) 之i i h ( x ) 1 1 第四步有意义童s o l ( c , f ) ，由于 p ) = 0 ，即厉：= 只( 名一f ) ) ( f ( 童) 一2 + 牙，至一y ) 0 ，v y c 取y =