（运筹学与控制论专业论文）伪单调算子的近似点算法.pdf

伪单调算子的近似点算法 运筹学与控制论 研究生周正指导教师何诣然( 教授) 论文摘要：s o l o d o v 和s v a i t e r 在2 0 0 0 年提出了一种混合近似点算法f 1 1 ，这种方 法迭代产生的序列在无限维h i l b e r t 空间内强收敛他们用这种方法求解了在 无限维h i l b e r t 空间内极大单调算子的零点这种强收敛的性质是将近似点 方法与向包含变分不等式解集的两个半平面交集的投影方法结合起来得到 的t a m ，y a o 和y e n 在2 0 0 8 年证明了在无限维空间的单调变分不等式的非精 确近似点算法的收敛性依然成立本文的第二章在上述成果的基础上，将单 调性条件削弱为伪单调性条件，在无限维h i l b e r t 空间中证明非精确近似点算 法产生的迭代序列强收敛到伪单调变分不等式的解另一方面j 经典的近似 点算法是大家熟知的一种可用于寻找一个极大单调算子的零点的方法结 合r o c k a f e l l a r 在1 9 7 6 年发表的研究成果f 2 3 1 与g o l s h t e i n 和t r e t y a k a v 在1 9 7 9 年得出的结论2 4 1 ，e c k s t e i n 和b e r t s e k a s 于1 9 9 0 年提出了一种广义近似点算 法，并用此方法寻找h i l b e r t 空间中一个极大单调算子的零点f 2 5 在参考文 献2 6 中这种方法得到了改进并被用于寻找在舻空间中极大单调算子在给定 闭凸子集内的零点文中还为这种改进的松弛近似点算法给出了在非精确 情况下的一种新的迭代方法本文第三章将这种松弛近似点算法运用于寻 找只n 空间中的伪单调集值算子在一给定闭凸子集内的零点随后在第四章 我们将松弛近似点算法用于寻找无穷维h i l b e r t 空间内伪单调集值算子的零 点，证明了由第四章中给出的算法产生的迭代序列强收敛于伪单调集值算子 的零点 关键词：伪单调；非精确近似点算法；弱收敛；强收敛；松弛近似点算法； 集值映射 t h ep r o x i m a lp o i n ta l g o r i t h mf o r p s e u d o - - m o n o t o n eo p e r a t o r s o p e r a t i o n sr 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 z h o uz h e n g s 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 ：w ei n t r o d u c e t h eb a c k g r o u n do ft h ep r o x i m a lp o i n ta l g o r i t h m ( p p a ) i nc h a p t e ro n e ，t h e ni nt h es e c o n dc h a p t e ro ft h i sp a p e r ，w ed i s c u s ss t r o n g c o n v e r g e n c eo ft h ei n e x a c tp r o x i m a lp o i n ta l g o r i t h m ( i p p a ) f o l f i n d i n gs o l u t i o n so fp 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 i e si na ni n f i n i t e d i m e n s i o n a l h i l b e r ts p a c e s o l o d o va n ds v a i t e rp r o p o s e dap r o x i m a lt y p e a l g o r i t h m w h i c hd o e sc o n v e r g es t r o n g l yi nt h ep r o b l e mo ff i n d i n gz e r o so fm a x i m a l m o n o t o n eo p e r a t o r si na ni 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 i n ：e 1 s t r o n gc o l l - v e r g e n c ep r o p e r t yw h i c ht h e yd i s c o v e r e di sf o r c e db yc o m b i n i n gp r o x i m a l p o i n ti t e r a t i o n sw i t hs i m p l ep r o j e c t i o ns t e p so n t oi n t e r s e c t i o no ft w oh a l f s - p a c e sc o n t a i n i n gt h es o l u t i o ns e t i tw a ss h o w nb yt a m ，y a oa n dy e nt h a t t h ec o n v e r g e n c et h e o r e mf o ri p p aa p p l i e dt oi m f i n i t e - d i m e n s i o n a lm o n o t o n e v a r i a t i o n a li n e q u a l i t i e sc a nb ep r o v e dw i t h o u tu s i n gt h et h e o r yo fm a x i m a l m o n o t o n eo p e r a t o r s 3 1 o u rp u r p o s ei st os t u d ys t r o n gc o n v e r g e n c eo fi p p a f o rf i n d i n gs o l u t i o n so fp 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 i e s t h e nw e t u r nt oc h a p t e rt h r e e f o ram a x i m a lm o n o t o n eo p e r a t o r ，aw e l l - k n o w nc l a s s i c a lp r o x i m a lp o i n t , a l g o r i t h mi so f t e nu s e dt of i n dt h ez e r o so ft h eo p e r a t o r c o m b i n e dr o c k a f e l l a r sa n a l y s i si n1 9 7 6 1 2 3 1w i t hg o l s h t e i na n dt r e t y a k a v s r e s u l ti n1 9 7 9 1 2 4 ，e c k s t e i na n db e r t s e k a sp r o p o s e dag e n e r a l i z e dp r o x i m a l p o i n ta l g o r i t h mt of i n dt h ez e r o so fam a x i m a lm o n o t o n eo p e r a t o ri nah i l b e r t s p a c e 2 5 y a n ga n dh ee n h a n c e dt h ea l g o r i t h mt of i n dz e r o so fam a x i m a l m o n o t o n eo p e r a t o ri na g i v e nc l o s e dc o n v e xs u b s e ti n ps p a c e t h e yg a v ea 2 n e wc r i t e r i o ni nt h ei n e x a c tc a s eo ft h e i rm o d i f i e dr e l a x e dp r o x i m a lp o i n ta 1 g o r i t h m 2 6 i nc h a p t e rt h r e eo ft h i sp a p e r ，b a s e do ny a n ga n dh e sr e l a x e d a p p r o x i m a t ep r o x i m a lp o i n ta l g o r i t h m ，w ew e a k e nm a x i m a lm o n o t o n i c i t y o ft h eo p e r a t o rb yp s e u d o - m o n o t o n ep r o p e r t ya n df i n dz e r o so fi t f u r t h e r - m o r e ，i nc h a p t e rf o u r ，w ed i s c u s st h er e l a x e da p p r o x i m a t ep r o x i m a lp o i n t a l g o r i t h mo nai 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 ea n dp r o v et h a tt h es e - - q u e n c eg e n e r a t e df r o mt h ei t e r a t i o nw h i c hi sg i v e ni nc h a p t e rf o u rc o n v e r g e s s t r o n g l yt oaz e r oo ft h ep s e u d o m o n o t o n eo p e r a t o r k e yw o r d s ：p s e u d o m o n o t o n e ；i n e x a c tp r o x i m a lp o i n ta l g o r i t h m ；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 ；r e l a x e dp r o x i m a lp o i n ta l g o r i t h m ；s e t v a l u e d m a p 四川师范大学学位论文独创性及 使用授权声明 本人声明：所呈交学位论文是本人在导。瓣， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外， 本论文不含仔何其他个人或集体己经发表或撰写过的作品或成 果。对本文的研究做出重要贡献的个人和集体，均已在文中以明 确方式标明。本声明的法律结果由本人承担。 本人承诺：已提交的学位论文电子版与论文纸本的内容一致。 如因不符而引起的学术声誉上的损失由本人自负。 本人同意所撰写学位论文的使用授权遵照学校的管理规定： 学校作为申请学位的条件之一，学位论文著作权拥有者须授权 所在大学拥有学位论文的部分使用权。即：1 ) 已获学位的研究生 必须按学校规定提交印刷版和电子版学位论文，可以将学位论文 的全部或部分内容编入有关数据库供检索；2 ) 为教学、科研和学 术交流目的，学校可以将公开的学位论文或解密后的学位论文作 为资料在图书馆、资料室等场所或在有关网络上供阅读、浏览。 本人授权中国科学技术信息研究所将本学位论文收录到中 国学位论文全文数据库，并通过网络向社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者虢周正 签字日期：沁f q 年中月扩日 导师虢夕孬。丫7 旺 签字日期腑矽月夕目 第一章背景介绍 变分不等式解的迭代算法是变分不等式理论发展的一个不可或缺的重 要研究分支一方面，各种各样的应用领域要求计算变分不等式的近似解， 另一方面，算法本身也促进了变分不等式的理论研究 最经典的变分不等式问题是h a r t m a n s t a m p a c c h i a 在上个世纪6 0 年代 提出来的假设c 是有限维e u c l i d e a n 空间p 中的非空闭凸子集，f ：c 寸 r n 是一个映射所谓变分不等式问题是找z c 满足 ( f ( z ) ，y 一。) 0 ，v y c ，( 1 1 ) 变分不等式解的存在性已经被深入细致的讨论本文主要讨论变分不等式解 的算法变分不等式的主要算法包括牛顿算法、近似点算法、t i k h o n o v 正则 化算法和超梯度投影算法等：不同的算法要求映射具有相应的性质 现在我们介绍近似点算法的由来以及本文所建立的算法背景 近似点算法是在求解具有极大单调映射的包含问题的基础上发展而来 的：寻找z h 使得 0 t ( z ) ( 1 2 ) 其中日是一个h i l b e r t 空间，t 是日上一个极大单调算子我们通常把这个问 题的解集写作 s ：= _ ( z h t 0 t ( z ) ) ( 1 3 ) t ：kh 2 k 是一个极大单调算子是指| 1 ：t 是极大单调算子当且仅当 ( z y ，缸一u ) 0 ，v ( y ，v ) g p h ( t ) ( 1 4 ) 时就有让t ( z ) 其c g p h ( t ) 定义是： g p h ( t ) = _ ( z ，u ) kxk ：乱丁( z ) ) ( 1 5 ) 为求解问题( 1 1 ) ，r o c t d e l l a r 于1 9 7 6 年提出了如下近似点迭代的方法 2 3 ： 令z 七为当前迭代获得的点，c k 0 ，寻找x k + l 满足 z 七x k + 1 + c k t ( x k + 1 ) ， 1 ( 1 6 ) 第一章背景介绍 这相当于将问题( 1 1 ) 转化为求解子问题 2 ( 1 7 ) 0 t ( x k ) + p 七( z z 七) ，( 1 8 ) 其中肌 0 k 一列相关系数如果 纵) 是有界的，则在s 0 的前提下，上面 所给出近似点方法迭代产生的序列 z 如) 弱收敛于s 内的点同时r o c k f e l l a r 在 他的论文中设置了一个公开问题：近似点方法得到的序列是否也总是强收敛 于s 中的点这个问题被g i i l e r 2 7 在1 9 9 1 年否定他证明，对于无限维h i l b e r t 空 间f 2 内的闭凸泛函厂( 在本文中即是将( 1 8 ) 中丁换做这个，) ，通过近似点迭代 得到的序列只能弱收敛于解集中的一点，而没有强收敛性质由此自然而然 伴随而来的问题就是近似点算法是否可以通过改进从而保证其迭代序列具 有强收敛性 s o l o d o v 和s v a i t e r 于2 0 0 0 年提出了一种混合近似点算法，这种算法将近似 点迭代( 1 8 ) 与向两个半平面的交集投影的迭代方法相结合来求解问题( 1 2 ) ， 在解集非空的前提下证明了在h i l b e r t 空间由这种方法迭代得到的序列强收 敛到解集内的点他们提出的方法如下： 算法1 1 任意选择x 0 h 和肌 0 ，通过k 部迭代我们得到z 七，选择( 纨，) 作为下 式的一个非精确解 0 t ( x k ) + 肛七( z z 七) ，( 1 9 ) 设半平面 h k ：- - ( z hl ( f ( 魄) ，z y k ) o )( 1 1 0 ) 和 w k ：= z hi ( 2 一z 七，z o x k ) o )( 1 1 1 ) 令 x k + l = p 日。n 砜( 知)( 1 1 2 ) 本文第二章正是在这一算法的基础上进一步探讨近似点算法在用于求 解单值伪单调变分不等式问题中产生的迭代序列的收敛性 、l ， 七 o ，i 1一 、l ， r + ， ， l + 知 z n p 耳 第一章背景介绍 3 另一方面，本文第三章将松弛近似点算法用于在算子丁是r n 空间中伪单 调集值算子的情况下求解问题( 1 2 ) 松弛近似点算法是近似点算法的一中改 进，文献 2 6 提出了这种算法并运用此算法在算子丁是r n 空间中极大单调算 子的情况下求解了i n l 题( 1 2 ) ，证明了由松弛近似点算法迭代产生的序列收敛 于问题( 1 2 ) 解集内的点第三章第一节将详细介绍这种算法的迭代程序 第二章伪单调变分不等式近似点算法的收敛性 2 1 介绍及准备知识 本文探讨的变分不等式问题即寻找o k 使得 ( f ( z ) ，y z ) 0 ，v y k ，( 2 1 ) 其中k 是h i l b e r t 空间x 内的一个非空闭凸集，f ：k _ x 是一个伪单调非空 单值映射令s = s o l ( fk ) 来表示( 2 1 ) 的解集 设z 七x 为的解的当前近似值，我们通过解以下近似点子问题得到下一 步迭代的近似值z 七+ 1 z s o l ( p k f + i x k ，k ) ，( 2 2 ) 其中【m ) 是一列正数于是由以上近似点迭代产生的序列 z 知) 弱收敛z s o l ( f , k ) 中 的一个点 求解在有限维空间变分不等式的主要方法m h a r k e r 和p a n g 提出f 4 1 ，他们 的文章展示了众多解的存在性和算法收敛性结论我们考虑在假设f 伪单调 的条件下用一系列近似点方法来求解问题( 2 1 ) k a r a m a r d i a n 早在1 9 7 6 就提 出了这一想法 5 ，他在这方面的研究与泛函的伪凸性质紧密相关6 ，7 1 其他 一些关于广义单调算子的思想出现在文献 s - 1 2 1 中，许多广义单调性的实际 运用和例子在 1 3 中可以找到而关于伪单调变分不等式解的存在性的一些 研究结果可参见文献f 4 ，5 ，1 4 - 1 6 1 下面再介绍一下收敛和单调的一些基本概念 定义2 1 1 强收敛与弱收敛1 7 1 ： ( 1 ) 点列的强弱收敛： 设x 是赋范空间， z 忆) cx ，x o x ，如果i i z n z o i l _ 0 ，( 礼_ + ) ， 则称 z n ) 强收敛f f ：z o 如果对任何的厂x 。，f ( z n ) 一f ( x o ) ，( 佗_ + ) ，则 称 ) 弱收敛于z o ( 2 ) 泛函的强弱收敛： 设_ 【厶) 是赋范空间x 上一列连续泛函，如果有，x 使得i i 厶一川o 0 ，( 礼_ + o 。) ，则称 厶) 强收敛于，；如果对任何的z x ，厶( z ) - - + ，( z ) ，( 礼_ + o o ) ，则称 厶) 弱收敛于， 4 第二章伪单调变分不等式近似点算法的收敛性 5 定义2 1 2 单调性和d u n n 性质1 8 ：设f 是x 0 d 上的映射，x 口d 代表一个可 行集合，则 ( i ) f 是单调的，如果v z l ，z 2 x a d 有 ( f ( x 2 ) 一f ( z 1 ) ，x 2 一z 1 ) 0 ( 2 3 ) ( 2 ) f 是强单调的，如果对比1 ，z 2 x o d ，存在a o 使得 ( f ( x 2 ) 一f ( z 1 ) ，x 2 一x 1 ) a l l z 2 一z 1 1 1 2 ( 2 4 ) ( 3 ) f 是伪单调的，如果比1 ，x 2 x 口d 有 ( f ( z 1 ) ，x 2 一x 1 ) 0 净( f ( x 2 ) ，z 2 一x 1 ) 0 ( 2 5 ) 这里的定义是来自【5 】，与b r e z i s 2 1 】提出的伪单调性的概念是有区别的 ( 4 ) f 是强伪单调的，如果对v z l ，z 2 x 谢，存在e 0 使得 ( f ( x 1 ) ，z 2 一z 1 ) 0 令( f ( z 2 ) ，x 2 一z 1 ) e l l z 2 一x l i l 2 ( 2 6 ) ( 5 ) f 是拟单调的，如果比1 ，z 2 x o d 有 ( f ( z 1 ) ，z 2 一x 1 ) 0 净( f ( z 2 ) ，x 2 2 ：1 ) 0 ( 2 7 ) ( 6 ) f 是弱单调的，如果对比1 ，z 2 x 砌，存在三 0 使得 ( f ( x 2 ) 一f ( z 1 ) ，x 2 一x 1 ) - l l l x 2 一z 11 1 2 ( 2 8 ) 这条性质包含了f + l ，是x 0 d 上的单调算子，其中，是恒等映射对每个有 界的子集scx d d ，如果存在l s 0 使得f + l s i 在s 上单调，则f 被称为 在x o z 是严格亚单调的2 2 1 进一步，容易识别弱单调性 ? , l i p s c h i t z 连续性更 弱 ( 7 ) f 具有d u n n 性质，如果对比1 ，z 2 x 以，存在a 0 使得 ( f ( x 2 ) 一f ( x x ) ，x 2 一x 1 ) ( 1 a ) i i f ( x 2 ) 一f ( x 1 ) 1 1 2 ( 2 9 ) 这里值得注意的是，如果多值算子f - 1 存在，则f 的d u n n 性质与f 1 的强单 调性实际上是等价的这有助于文献f 1 9 1 中提出的强制性当a = 1 时，我们 有( f ( x 2 ) 一f ( z 1 ) ，x 2 一x 1 ) i i f ( z 2 ) 一f ( z 1 ) 悒即j f l 是非扩张的 2 0 ( s ) f 具有伪d u n n 性质，如果对v x l ，z 2 x 础，存在e 0 使得 ( f ( z 1 ) ，x 2 一z 1 ) 0 令( f ( z 2 ) ，x 2 一x 1 ) ( 1 e ) i i f ( x 2 ) 一f ( x a ) 1 1 2 ( 2 1 0 ) 第二章伪单调变分不等式近似点算法的收敛性 2 2 非精确近似点迭代 6 因为要精确求解子问题( 2 2 ) 同求解( 2 1 ) 本身一样困难甚至是不可能的， 因此我们设计如下非精确近似迭代得方法来逼近问题的解我们设一个魂 k 使得 d i s t ( z k ，s o l ( f 七，k ) ) 氏，( 2 1 1 ) 且令z 0 ：- - 知，其c o f 七( z ) ：- - p k f ( x ) + x z k 一1 ，d i s t ( z k ，s o l ( f 七，k ) 表示 点钆到解集s o l ( f 七，k ) 的距离，钆0 满足条件 0 ，通过k 部迭代我们得到z 七，选择y k 作为下式的 一个非精确解 ( p k f ( x ) + x z k 一1 ，y z ) 0 ，v y k ( 2 1 3 ) 设半平面 h k ：= z xl ( f ( y k ) ，z y k ) o ) ( 2 1 4 ) 和 o w k ：= z xl ( z z k ，z o z k ) so )( 2 1 5 ) 令 z k + 1 = p 丑k n w ( z o ) ( 2 1 6 ) 容易证明由以上方法迭代得到的序列 z k 是合理的并且解是存在的我 们设s 是问题( 2 1 ) 的解集，并且对所有的u s ，我们都有( f ) ，z u ) o ，比k 于是由f 的伪单调性质，我们可知( f ( z ) ，z u ) 0 ，v z k 于 是显然对所有的凳都有( f ( 玑) ，y k - - l d ) 0 显然，甄= x 所以凰nw o ， z 1 是正确和合理的我们再设钆= 岛。一，n 肌一，翔是正确的，于是一，z o 第二章伪单调变分不等式近似点算法的收敛性 7 z 知) = 一岛k 一1 n 帆一，z o ，z o 一昂n 帆一，z o ) 0 这意味着u 帆因 此u 凰nw k ，z k + 1 = 岛。n 眠幻是正确和合理的 上述文字还包含了一层含义：问题( 2 1 ) 的解集是包含在两个半平面的交 集里的，h p s h kn 帆 2 3 主要结论 命题2 3 1 1 3 如果z + s o l ( f , k ) ，我们有 l i z 七一矿1 1 2 l i z 惫一1 一z l | 2 一i i z 七一z k 一1 1 1 2 ( 2 1 7 ) 命题2 3 2 设f 在k 上是伪单调的，p 0 是一个常数，z x ，并且u s o l ( g ，k ) ，其中g ( z ) = p f ( x ) + z 一2 ，比k 于是对任意的z s o l ( 只k ) ，都有 l i u z 1 1 2 i l z z 4 1 1 2 一i i z 一钉f 1 2 ( 2 1 8 ) 证明：因为z + s o l ( ek ) ，我们有( f ( z ) ，y z + ) 0 ，v y k 由f 的 伪单调性可得 ( f ( 可) ，y 一。+ ) 0 ，v y k ( 2 1 9 ) 因为v s o l ( eg ) ，所以 ( p f ( v ) + v z ，y v ) 20 ，v y k ( 2 2 0 ) 由此式以及分别在不等式( 2 1 9 ) ( 2 2 0 ) 中作替代y = u 和芗= z 后可得 ( v z ，z + 一u ) p ( f ( 钌) ，v z ) 0 ( 2 2 1 ) 于是得到 z 一z i l 2 一i i 。+ 一u i l 2 一l i u z l l 2 = ( z + 一幻， 一z ) 0 ( 2 2 2 ) 即是 | i z 一u i l 2 i i z 一z i l 2 一l i v 一z i l 2 ( 2 2 3 ) 引理2 3 1 设f ：k _ x 是一个连续伪单调映射，s o l ( ek ) 0 ，z o x 是一个给定向量，_ 【讯) 是由非精确迭代( 2 2 ) 得到的序列于是 魂) 有界并 第二章伪单调变分不等式近似点算法的收敛性 8 且如果存在子序列 钆， c z ；) 弱收敛于点岔x ，则君s o l ( f , k ) 并且 点 是序列_ 【) 的唯一弱收敛点 这个结论由t a m 等三位专家在2 0 0 8 年证明参见jo p t i mt h e o r ya p p l ( 2 0 0 8 ) 1 3 第2 6 6 页定理4 1 定理2 3 1 设z k - 是由上述近似点算法迭代产生的序列如果s = s o l ( f , k ) 0 并且( 2 1 ) 中定义的f 在k 上是连续伪单调的，则 名七) 强收敛于点z + = p s z o ， 证明：由引理2 3 1 知 z 南) 有界，这意味着 ) 一定有弱收敛点不妨 设乏是_ ( z k ) 的任意一个收敛点，并且 孙 的子序列 z 七，) 弱收敛于点乏我们 由引理2 3 1 还可知- 5 s o l ( f , k 1 由z 知+ 1 的定义，我们有 | 1 名知+ 1 一z o l i i i z 一徇i l ，v z 凰ny c k ( 2 2 4 ) 因为z + s o l ( f jk ) ch kn 帆，所以对所有的七有 i l 魂一z o l | | l z 。一细m( 2 2 5 ) 由此可知 z 幻一z + 1 1 2 = 1 1 2 b 一t o + x 0 一z + 1 1 2 = i i z k j 一幻1 1 2 + i i z 4 一询1 1 2 2 ( 2 b z 0 ，z 一翔) 2 ( 1 l x + 一知1 1 2 一( 钨一z 0 ，z + 一如) ) 由 魂，) 弱收敛到点虿和虿s o l ( f , k ) ，我们可知 l i ms u p i | 名幻一z 1 1 22 ( 1 l x 一徇1 1 2 一( z b z o ，z 一铂) ) = 2 ( z 一乏z + 一劲) # 2 ( p s z o 一乏，p s z o 一询) ) 0 ，通过k 步迭代我们得到z 七，选择弧作为下式的一个非精确解 设 和 令 ( p k f ( x 七) + m ( 。) 一m 7 ( 张一1 ) ，秒一2 ) 0 ( 2 2 9 ) 凰：= ( z xi ( ，( 玑) ，z 一纨) o ) w k ：= z xl ( 。一z k ，询z k ) o ) z k - f 1 = p h n w k ( z o ) 命题2 4 1 我们首先证明i h - j 题( 2 2 8 ) 解的存在性 证明：如果s o l ( f , k ) 仍，令z s o l ( f , k ) 并定义 ( 2 3 0 ) ( 2 3 1 ) ( 2 3 2 ) a ( y ) ：= z k ，( p k f ( x ) + m 7 ( z ) m 7 ( z o ) ，y z o ) o ) ，( 2 3 3 ) 第二章伪单调变分不等式近似点算法的收敛性 于是g 是一个闭值的k k m 映射接下来需要证明g ( 虿) 有界 因为z s o l ( f , k ) ，所以对任意m y k 有( f 伍) ，y 一虿) 0 如果z g ( 虿) j 我们有 ( p k f ( x ) + m ( z ) 一m 7 ( z o ) ，虿一z ) ( m 7 0 ) 一m ( z o ) ，- 2 一z ) + p k ( f ( z ) ，- 2 一z ) 1 0 因为对任意的可k 都有( f ( 虿) ，y 一虿) o 并且f 是伪单调的，所以( f ) ，z 一 虿) 0 ，即( f ( z ) ，虿一z ) 0 于是有 0 ( p k f ( x ) + m 7 ( z ) 一m ( z o ) ，虿一z ) ( m 7 ( z ) 一m 7 ( z o ) ，虿一z ) ( 2 3 4 ) 这说明g ( 虿) 是有界的 由k k m 定理可知s o l ( f 七，k ) d 定理2 4 1 如果s = s o l ( f , k ) 0 ，并且f 对一常数e 0 具有伪d u n n 性 质，m 7 具有l i p s c h i t z 适 续性，于是由方法2 2 迭代得到的序列 ) 有界并且其 聚点在s 中 证明：令z + p s ( 劲) 对每一七n ，选择x k s o l ( f 七，k ) 使得 i l 犰一x k j 2 e k ( 当e 七= 0 时讯s o l ( f 七，k ) ) 因为 z 七一z + l l i i 钆一x k l i + i x k z 。| i 2 e k + i l z 七一名知i | + i i 魂一x 。 4 e k + l 翔一z 。i l ( 2 3 5 ) 于是是1i i z k 二z 。i | 4e 墨1 + i i 徇一z i i + 说明( 魂) 有界又因为 x k z 。l ii i z 忌一z 七i i + 1 1 名七一z + 2 e k + l l 徇一z 。i i 第二章伪单调变分不等式近似点算法的收敛性 1 1 于是器。忙七一。i f 2 e 墨。e 惫+ i l 知二z + i i o 具有伪d u n n 性质，m 7 具有l i p s c h i t z 连续性，那么 魂) 强 收敛于点z 。= p s z o 证明： z k ) 有界说明 钆) _ 一定具有弱收敛点设 是序列 ) 的任意一个 弱收敛点，并且 ；) 是弱收敛到点獭任意子序列我们由定理2 4 1 可知 s o l ( f , k 1 z一 一 奄 名 汹 + 一 z 一 托 z 随 第二章伪单调变分不等式近似点算法的收敛性 我们z k + l 定义可知 1 2 名_ j c + 1 一z o l i i i z 一翔i i ，v z 凰nw k ( 2 4 0 ) 因为z + s o l ( f , k ) ch knw k ，于是对所有的尼有 f f 缸一z o l i l | z + 一z o l l ( 2 4 1 ) 我们注意到 一z 4 1 1 2 = d ，是一列标量 在一般情况下，要精确的得到上式是非常困难甚至不可能的，因此需要 一种非精确的变形 z 七+ l + c k t ( x k + 1 ) 弓x k + e 七+ 1( 3 3 ) 其中 e 如) 是一组误差值的序列，此方法也被称为非精确的近似点算法 为了找到极大单调算子t 在舻中给定的闭凸集q 内的零点，我们可以将 其考虑为这样一个问题：找到点z q 使得0 t ( x ) ，即是找到一个丁在q 内 的零点，并假设t - 1 ( 0 ) nq 0 为解决这个i ；- 1 题，参考文献f 2 6 1 提出了一种松弛非精确近似点方法：从 某个k 出发，由z 七经如下迭代得到氟+ 1 玩+ 1 + c k t ( s k + 1 ) 弓x k + e k + 1 ( 3 4 ) ( 3 5 ) 并且 叩2 0 ，则对所有的z q n 丁一1 ( 0 ) ，i n f e t ( 1 ，) ( ，y x ) 0 都 成立接下来我们将首先给出一个重要的结论，这个结论是解开本节主要问 题的钥匙 定理3 3 1 如果丁是伪单调的，则z + c 七t ( x ) x k + e k + 1 考z s o l ( c k t + i z 七一e k + 1 ，q ) 证明：令 v ( y ) ：= 【z q ：s u p ( c k ? 2 + z x k e 七+ 1 ，y z ) 0 ，v y q )( 3 1 7 ) u e t ( x ) 这里g 是一个闭值的k k m 映射否则，存在z o c o x , z n ) 使得x 0 = ：1a i x , ， 其中墨1 九= 1 ：入0 ，i = 1 ，2 ，n 而跏不属于u ：1g ( ) 因此，对任意 第三章伪单调集值算子的松弛近似点算法 1 6 的甄，我们有s u p u e t ( x 。) ( c k u + x o x k - - e k + 1 ，x i - - x o ) 0 ，于是s u p u e t ( z 。) ( c 七札+ z o z j c e 知+ 1 ，：1k ( 一g o ) ) s u p u t ( z o ) ( c k u + x 0 一z k e 七十1 ，：1 凡筑一x 0 ) = 0 ，这是矛盾的 设虿是c 七t ( ) + i x 七0 的一个任意解，于是有s u 儿r ( - ) ( 乱，y 一虿) o ，v y q 由t 的伪单调性，我们得至u i n f t ( 掣) ( u ，y 二虿) 0 ，v y q 如果z g ( 劫，我们就得到 0 = 0 ，所以有 s u p ( f ，y z ) 之0 ，v y q r 一) 1 7 ( 3 2 1 ) ( 3 2 2 ) 因此z 。t _ 1 ( 0 ) nq 再由引理3 2 1 和引理3 2 2 ，我们有 i l x k + l - x o 。1 1 2 ( 1 + 篆) l | 驴珊，v 七( 3 2 3 ) 因为z 知_ z ，兀是幻( 1 + 2 - 址 f k ” l k 2 、 0 ，存 在相应的2 使得 以及 因此，对所有k 一k t 都有 由此得知 e x k z z o 。i i i 二 ( 1 + 磊4 y k 卵：) 2 z l | c z 1 1 2 ( 1 + 互_ = 4 石 7 k - 1 7 7 ；一1 ) i l z 七一， z o 。1 1 2 f i ( 1 + 袅硝i | x t - - 3 2 0 0 酽 t = k 。 ，茸 2 - e 2 e 2 z 七一z o 。i i e 这即是表明 z | | c ) 收敛于点z o 。证