（基础数学专业论文）变分不等式的投影算法.pdf

变分不等式的投影算法 基础数学 研究生李风莲指导教师丁协平( 教授) 论文摘要：与其它类型算法相比，变分不等式的投影算法构造简洁因此该 算法被研究变分不等式算法的学者深入而细致地讨论但早期投影算法的收 敛性证明通常要求变分不等式中的映射是强单调和l i p s c h i t z 连续的二次 投影算法是近年来针对经典变分不等式提出的一类新的投影算法，它最大的 优点是算法的收敛性证明只要求映射是伪单调和连续的广义变分不等式不 仅包吉经典变分不等式作为特例，而且有更广泛的应用背景迄今为止，针 对广义变分不等式提出的算法通常假设映射是强单调和l i p s c h i t z 连续的本 文探讨将二次投影算法推广到广义变分不等式问题，算法及其收敛性证明仅 要求映射是伪单调和连续的其次，本文讨论了一类随机变分不等式的迭代 算法最后，局部凸空间中的个f a r k a s 引理被证明，它不仅推广了已知的 结果，而且证明方法更简洁 关键词：变分不等式；二次投影算法；伪单调映射；f a r k a s 引理 p r o j e c t i o nm e t h o d sf o rv a r i a t i o n a l i n e q u a l i t i e s p o s t g r a d u a t e l if e n g l i o n s u p e r v i s o rp r o f e s s o rd i n gx i e p i n g a b s t r a c t ：c o m p a r e dt oo t h e ra l g o r i t h m sf o rv a r i a t i o n a li n e q u a l i t i e s ，p r o - j e c t i o nm e t h o d s a r ec o n c e p t u a l l ys i m p l em e t h o d s i ti sb e c a l l s eo f t h i sr e s s o n t h a tp r o j e c t i o nm e t h o d sh a v eb e e ni n t e n s i v e l ys t u d i e di nt h eh t e r a t l l r e e a r l y 8 1 9 0 r i t h m 8o fp r o j e c t i o nt y p eu s u a l l ya s s u n l et h em a pi n v o l v e di ss t r o n g l y m o n o t o n ea n d o rl i p s c h i t zc o n t i n u o u s d o u b l ep r o j e c t i o na l g o r i t h mi r a - p r o v e st h o s ee a r l i e rp r o j e c t i o na l g o r i t h m sb ya s s u m i n gt h em a pt ob eo n l y p s e u d o m o n o t o n ea n dc o n t i n u o u s t h o u g he a r l yp r o j e c t i o na l g o r i t h m sh a v e a l r e a d yb e e ne x t e n d e dt og e n e r a l i z e dv a r i n t i o ni n e q u a l i t i e s ，t h ed o u b l ep r o - j e c t i o na l g o r i t h mh a sn o tb e e nd o n e8 0 t h i sp a p e rc o n c e n t r a t e so ns t u d y i n g d o u b l ep r o j e c t i o na l g o r i t h mf o rg e n e r a l i z e dv a r i a t i o n a li n e q u a l i t i e s m o r e - o v e r ，ap r o j e c t i o na l g o r i t h mf o rac l a s so fs t o c h a s t i cv a r i a t i o n a li n e q t u d i t i e s i sd i s c u s s e d ，a n daf a x k a sl e m m ai sp r o v e di nl o c a l l yc o n v e xs p a c e sw h i c h n o to n l yg e n e r a l i z e sk n o w nr e s u l tt om o r eg e n e r a ls p a c e sb u ta l s oi sp r o v e d i na s i m p l e tw a y 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 i e s ；d o u b l ep r o j e c t i o nm e t h o d ；p s e u d o - m o n o t o n e ；f a r k a sl e m m a 四川师范大学学位论文独创性及 使用授权声明 本人声明：所呈交学位论文，是本人在导师指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任 何其他个人或集体己经发表或撰写过的作品或成果。对本文的研究做出重要 贡献的个人和集体，均已在文中以明确方式标明。 本人承诺：已提交的学位论文电子版与论文纸本的内容一致。如因不符 而引起的学术声誉上的损失由本人自负。 本人同意所撰写学位论文的使用授权遵照学校的管理规定： 学校作为申请学位的条件之一，学位论文著作权拥有者须授权所在大学 拥有学位论文的部分使用权，即：1 ) 已获学位的研究生必须按学校规定提 交印刷版和电子版学位论文，可以将学位论文的全部或部分内容编入有关数 据库进行检索；2 ) 为教学和科研目的，学校可以将公开的学位论文或解密 后的学位论文作为资料在图书馆、资料室等场所或在校园网上供校内师生阅 读、浏览。 论文作者签名：李风莲 2 0 0 7 年4 月6 日 第一章投影算法发展的主要背景 变分不等式解的迭代算法是变分不等式理论发展的一个不可或缺的重 要研究分支一方面，各种各样的应甩领域要求计算变分不等式的近似解， 另一方面，算法本身也促进了变分不等式的理论研究 最经典的变分不等式阿题是由h a r t m a n - s t a r n p a c c h i a 在上个世纪年 代提出来的假设c 是有限维e u c l i d e a n 空间r “中的非空 j j 凸子集，f ： g r m 是个陕牡所谓变分不等式问题是找z c 满是 ( f ( 0 ) ，f o ) 之0 ，v f g( 1 1 ) 变分不等式解的存在性已经被深入细致的讨论，本文主要讨论变分不等式解 的算法变分不等式的主要算法包括牛饭算法近似点算法，t i k h o n o v 正则 化算法和投影算法等不同的算法要求映射具有相应的性质例如，牛顿算法 要求映射f 具有光滑性，而且映射的导数是非退化的；近似点算法是在求解 具有极大单调映射的包含问题的基础上发展而来的，相比较而言，投影算法 执行起来相对容易，适用范围更广现在我们总结投影算法发展过程中几个 重要的结果 假设f 是强单调和l i p s c h i t z 连续，s i b o n y 【1 】1 在1 9 7 0 年证明下面的 算法所产生的迭代序列 z t 收敛到变分不等式( 1 1 ) 的解，对任意初始点 两c ， 以+ l ：= i b 陬一口f ( z ) 1 ，k = o ，1 ，2 ， 其中d 0 是个( 依赖于强单调模和l i p s c h i t z 模) 的充分小的参变量 假设f 是单调和l i p s c h i t z 连续，k o r p e l e v i c h 【2 】在1 9 7 6 年证明下面的 算法所产生的迭代序列 戤 收敛到变分不等式( 1 1 ) 的个解：对任意初 始点：r 0 c 。 鲰：= i i c k 一口以以) j 。i ：= i i c 陬一a f ( y t ) 】，= 0 ，1 ，2 ， 其中o 0 是个( 依赖于l i p s c h i t z 模) 的充分小的参变量，这一算法被 称为超梯度算法( e x t r a g r a d i e n tm e t h o d ) 通常，人们无法预先知道参变量口 第一章投影算法发展的主要背景 2 应该小到什么程度为了克服这一困难，【3 ，4 l 等通过在每一步迭代中动态地 选取参变量而进一步发展超梯度算法 s o l o d o v 和s v a i t e r 5 在1 9 9 9 年提出了下面的算法假设f 是伪单调 和连续映射，他们证明下面的算法产生的迭代序列 z k 收敛到变分不等式 ( 1 1 ) 的一个解 算法1 1 选取勒c 和参量口 0 ，p ( 0 ，1 f ) ，7 ( 0 1 ) 取t = 0 步骤1 计算( ) ：；戤一r l e ( x t p f 慨) ) 如果协) = 0 ，停止；否则，转 到步骤2 步骤2 设”k 是满足下面不等式的最小的非负整数 f ( x 一矿( 锄) ) ，) ) 口8 ( 以) n ( 1 2 ) 令盈：= 戤一1 m 虬( 甄) 步骤3 计算+ 1 = i i a ( 毛) ，其中c ；= 口c ：( f ( ) ， 一矗) so ) 令 = “- 1 并回到步骤l ， 该算法教称为超平面投影算法( h y p e r p l a n ep r o j e c t i o na l g o r i t h m ) ，也日q 二次投影算法 实践表明，二次投影算法是一类比较好的算法一方面，它不要求映射 是l i p s c h i t z 连续的；另一方面，针对一些典型问题，它的攫4 试结果令人满意 【5 】 近来，有学者尝试将二次投影算法推广到所谓的一般变分不等式问题 ( 参见【6 ，a l g o r i t h m3 6 】) ：找z r “使得9 0 ) c 且 ( f ( z ) ，口一9 ( o ) ) 0 ，v c ，( 1 3 ) 其中，e 是碾，中的非空闭凸子集，g ：瑕，一c ，f ：r n 一时但是。这些 文献通常假设映射g 既是单射又是满射在这样的假设条件下，我们可以证 明一般变分不等式问题等价于下面的问题：找e 使得 ( ( f 。g - 1 ) ( o ) ，g 一$ ) 0 ，v y c ；( 1 4 ) 即，一般变分不等式等价于经典变分不等式问题因此，假设g 是双射似乎 不太恰当 本文不假设映射g 是双射，并给出了一般变分不等式的= 次投影算法， 该算法推广了经典变分不等式的二次投影算法我们的思路是，首先将一般 第一章投影算法发展的主要背景 3 变分不等式问题转化为具有集值映射的广义变分不等式，并讨论广义变分不 等式的二次投影算法及其收敛性作为推论，我们得到了一般变分不等式问 题的二次投影算法及其收敛性 研究广义变分不等式同题的二次投影算法还有另外一个动机，就我们所 知道的而畜，关于广义变分不等式的投影算法均假设映射是单调( 甚至更强 的单调性) 和l i p a c h i t z 连续的【7 1 ，将二次投影算法推广到广义变分不等式 问题将会大大削弱对映射的限制我们在集值映射是伪单调和连续映射的条 件下，提出了广义变分不等式的个投影算法，并证明了算法的收敛性 第二章= 次投影算法 2 1 预备知识 假设c 是r “中的非空闭凸子集我们用n c 表示c 上的投影算子，即 对每一i t , 舻， i i c ( z ) ：= a r g m i n ；e c l l x 一1 1 命题2 1 ( 投影变分原理) 。= n 口( z ) 的充要条件是 ( z z ，掣一名) 0 ，v 管e 证明参见【8 ，命题1 3 2 】 口 引理2 1 假设o c ，x 那么下面的结论等价： ( i ) l i ：一口0 2si i x v l f 2 一1 1 2 一$ 0 2 ，v g g ( i i ) o = n o ( x ) 证明对任给的c ， i i x 一1 1 2 = l i z 一4 1 2 + 1 1 2 一y l l 2 + 2 ( z 一。，：一) 运用投影变分原理，我们立即得到结论 口 下面关于集值映射的定义和性质参见书【8 】中的5 1 设f 是从拓扑空间y 到拓扑空间z 的集值映射。f 称为在y 上是上 半连续的，如果对任意z 中的开子集y ， 妇y ：f b ) c 矿) 是y 中的开子集等价地，对任意z 中的闭子集耳， 口y ：f ( ) n k 0 是y 中的闭子集 f 称为在y 上是下半连续的，如果对任意z 中的开子集y ， 0 y ：f ( ) n v 谚 4 第二章二次投彩算法 5 是y 中的开子集等价地，对任意z 中的闭子集k ， 妇y ：f c v ) c k ) 是y 串的翅子集 f 称为是在y 上连续的，如果它在y 上既是上半连续映射，又是下半 连续映射 假设k 是r ”中的非空子集映射f ：k r “被称为是强单调的，如 果存在 o 使得对任意，y k ， ( f ( z ) 一f c y ) ，z 一口) 口i l z 一引1 2 ； 映射f ：k r “被称为是单调的，如果对任意z ，g k ， ( f ( 习一f 白) ，z 一) o ； 映射f ：k r ”被称为是伪单调的【9 】，如果对任意z ，e k ， ( f ( z ) 。口z ) 0 = ( p ( p ) ，y z ) 0 集值映射f ：k 一2 i 被称为是单调的，如果对任意z ，e k ( z 一y ，z y ) 0 ，v 矿e f c x ) ，y f ( ) 集值映射f ：k 一2 r 被嚣为是沩单调的，如果对任意2 ，f k 和任意的 z f ( $ ) ，矿f ( v ) ， ( z ，一z ) 0 = 争f ，p z ) 0 2 2 一类广义变分不等式的二次投影算法 广义变分不等式是比经典变分不等式( 1 1 ) 更广泛的一类变分不等式， 是由【l o 】最早提出来的假设f ：c 一尹所谓广义变分不等式是找e 和f f 拉j 使得 ，一) 0 ，v ，d( 2 1 ) 文献【1 1 】在局部凸拓扑线性空间中研究了广义变分不等式解的存在性 第二章二次投影算法 6 2 2 1 基本假设 除非特别声明，我们总假设广义变分不等式的解集s 是非空的，f 是连 续集值映射且满足下面的条件：对所有y e c ，矿f ( 口) ，和每一z s ， ( 矿，一z ) 0 ( 2 2 ) 特别地，如果f 是伪单调映射，上面的条件( 2 2 ) 自然成立 2 2 2 算法及其良定性 假设p 0 是一个参变量，定义 q 。( 卫，z ) ：= 卫一n c ( 一i z x ) 算法2 1 任意选取初始点z o c 和参变量口 0 ，p ( 0 ，1 a ) ，和1 ( 0 ，1 ) 令i ；0 步骤1 如果存在f f ( 戤) 使得r 。( x l ，f ) = 0 ，那么程序终止；否则任意选取 & f ( z i ) 步骤2 令是使得下面表达式成立的最小非负整数k m p ( ( 唯( 毛，矗) ) ：f f 一矿( ，) ) j 唯( ，& ) 限( 2 3 ) 取五= 一m r ( x i ，矗) ，其中琅= 铲 步骤3 令 k 扣) ：= s u p 佳，u 一) ，( 2 4 ) f e ，( 二) 和集合g - p c ：旭0 ) o ) 计算z ：= c t ( ) 令t = - 1 并回到步骤1 注2 1 如果映射f 是单值的，算法2 1 回到【5 a l g o r i t h m2 1 1 在证明算法2 1 是良定之前。我们先证明一个引理 引理2 2 对每一z r ”和每一，f ( z ) ， ( z ，( ，矿) ) 2 # - 1 i i r ( x ，矿) 1 1 2 ( 2 5 ) 证明根据投影变分原理， 、 ( z p 。+ 一h c ( x p z ) ，口一i i c ( z 一，口) ) 0 ，y y d 特别地，取y = z 并注意到( z ，矿) = 一i i c ( x p 矿) ，我们得到结论口 第二章二次投影算法 7 根据引理2 2 ，我们能够说明算法2 1 的步骤2 是良定的，事实上，根据 引理2 2 ，我们有 s u p ( ，q ( ，矗) ) 幅，( 4 ，矗) ) # - 1 0 ( 瓢，6 ) 1 1 2 f f ( z 口( 墨，| f 2 其中最后个不等式成立是因为p 矿 口h 气( 毛毛) f f 2 令 w - k ：( ，( 孔，矗) ) 口唯( 戤，1 1 2 ) 那么形是歼集而且f ( n w & 因为f 是下半连续集值跃镕虫存在 6 0 使得 f ( z ) n w 0 ，v z b ( 戤，j ) ， 其中，b ( z d ) 表示以为心6 为半径的开球，因为h m i 一研一矿( 墨，靠) = ，存在m 使得 一矿( ，& ) b ( ，占) ，v k m 因此， f ( 筑一7 o ( 霸，纠) n w 0 ，y 七 值 这样满足表达式( 2 3 ) 的非负整数必定存在 下面的引理表明如果当前迭代不是变分不等式的解，那么毛每g 此外，变分不等式的解总是包含在每个集合g 中 引理2 3 假设矿是广义变分不等式( 2 1 ) 的解，函数札由( 2 , 4 ) 所定义邵 么 k ( 如) 琅盯i i ( ，6 ) 1 1 2 毛，) sd i 特别地，如果，鳓0 ，那么垃慨) 0 第二章二次投影算法8 证明因为= 甄一协r 。( ，靠) ， ( 以) = s u p ( 车，她一4 ) = 准s u p 任，( 奶，毛) ) f e f ( z - )托f 恤) ，7 i d l i ( ，已) 0 2 ， 其中不等式成立是根据( 2 3 ) 因为f 满足( 22 ) ，也( 矿) 0 口 2 2 3 算法的收敛性 下面的算法收敛性的证明借用了1 1 2 ，定理3 1 】的证明思想 定理2 1 假设f ：c 一2 ”是具有非空紧凸值的连续集值映射且广义变分 不等式( 2 1 ) 的解存在如果条件( 2 2 ) 成立，那么算法2 1 或者在有限步迭 代后停止或者产生一个收敛于变分不等式解的无穷序列 戤) 证明对任意选取的变分不等式的解，根据引理2 3 ， 矿g ，v t 如果算法2 1 不在有限步迭代后停止，那么它会产生个无穷序列 瓤) 因 此。我们必然有 ( 毛，釉o ，v 根据算法的第3 个步骤，缸+ 1 = 玎a ( z i ) ，根据引理2 , 1 ，我们有 0 z 件l 一，2 0 一。1 1 2 一| i $ 件1 一龟1 1 2 1 1 一r 8 2 一d 坩t 2 ( ，a ) ，( 2 6 ) 其中，最后一个不等式成立是因为。“l g 由此可以推出，序列 l l x t + 1 一 矿1 1 2 ) 单调递减，因此是一个收敛序列我们立即得到， 毛) 是一个有界序列 和 t i md i s t ( x i ，g ) = 0 ( 2 7 ) 因为f 具有紧值的连续映射，有界集在f 下的象也是有界集，所以 f ( ) ： t ) 是一个有界集根据矗和的定义，协，和怯) 都是有界序列这 样， f ( ) 也是有界集：存在m 0 使得 f ( ) cb ( o ，m ) ， v t ( 2 8 ) 第二章二次投影算法 9 我们断言， d i s t ( x t ，g ) m 。h ( 魏) ，v i ( 2 9 ) 事实上，因为g 是闭集，存在驰g 使得0 一雏n = d i s t ( x i ，g ) 根据函 数瓤的定义，存在“f ( 五) 使得 ( a ) = s u p ( ，毛一气) = ( t ，a 一4 ) ， i e f ( ) k ( 弘) = s u p ( 毒，筑一盈) ( ，弘一盈) 托，c 鼻) 因此 k ( z i ) 一k ( 弘) 墨扣，一毛) 一恤，弧一4 ) = ( t ，q 一弘) s9 u 一弘”s f 8 一弘0( 2 1 0 ) = m d i s t c z ，g ) 因为执g ，我们有7 l t ( 弘) 0 根据上面的表达式( 2 1 0 ) ， 趣瓴) 鬼溆) 一岛( 嚣) s m 幽t 弦，g ) ， 断言( 2 9 ) 得证 根据( 2 6 ) ，( 2 9 ) 。和引理2 3 ，我们得到 如t ( 承，g ) 兰m 一1 m “坼阮池。驯2 利用( 2 7 ) ，我们有 2 骢哺i i ( z i t ) i 1 2 = 0 ( 2 1 1 ) 下面分两种情况进行汪盟 如果l l m s u p t 。琅 0 ，那么根据( 2 1 1 ) ，l i m 呲一l i ( 毛，e ) 0 = 0 因 为序列 ) 和序列 矗 是有界的，存在 ( 戤，) 的一个聚点悔，0 因为 唯( ，) 是连续映射。( 雪，自= 0 ，即i 是变分不等式( 2 1 ) 的解甩i 取代 矿，根据此定理证明的前半部分，我们有 j l 五一刘 是单调递减的数列。因 此是个收敛数列注意到i 是序列 ) 的疑点，刊一训) 的某一个子序 列收敛到零这样，整个序列训缸一到) 收敛到零，即驰。矗= 孟 第二章二次投影算法 如果l i r a s u p “。啦= 0 ，因为 哺 是非负数列，我们有h m 。讯= 0 取序列( ( 缸，矗) ) 的任意聚点( i ，a ，那么存在个子序列 ( 2 。，屯) 收敛到 ( i ，自根据算法2 1 的步骤2 ，对每一 ，整数：= h 一1 必定使表达式( 2 3 ) 不成立。因此， 口0 勺( ，岛) 2 s u “( f ，( 。o ，岛) ) ：f f ( 一7 - 1 他( ，毛) ) k v 工 在上面表达式中让j o 。则产生下面的表达式 a l l r c ，钏2 s u p ( ，( i ，f ) ) ：f f ( i ) ) 幢( i ，a ) p - 1 0 唯( 牙，自悒 ( 2 1 2 ) 其中第个不等式利用了集值映射f 的下半连续性，第二个不等式成立是 因为f f ( i ) ，第三个不等式利用t 6 1 理2 2 因为妒 0 是一个参变量，定义 r ( z ，p ) ：= 9 扛) 一n c c g c = ) 一p f ( 甸) 算法2 2 任意选取初始点x 0 r ”和参变量矿 0 ，p ( 0 ，1 o ) ，和7 ( 0 ，1 ) 令 = 0 步骤1 如果r ( ，p ) = o ，那么程序终止；否则，继续 步骤2 ，令毛是使得下面表达式成立的最小非负整数 ( f c g ( x , ) 一产r ( 以，p ) ) ，兄( z t ，) ) 口l l r c z l ，_ 【) 1 1 2 ( 2 1 8 ) 取= g ( z d ) 一琅冗( 戤，p ) ，其中哺= p 步骤3 令 乜( u ) ：= s u p ( f ( ，口一g c u ) ) ：g ( q ) ；五 ，( 2 1 9 ) 和集合a 如e ：旭( 口) o ) 计算盘使得9 0 + i ) = n c , ( g c = d ) 令 ；i + 1 并回到步骤1 上面算法的良定性以及下面定理的证明通过运用上一节算法2 1 和定理 2 1 到集值映射fo g o 能直接得到 定理2 2 算法2 2 或者在有限步迭代后停止或者产生一个收敛于变分不等式 謦的无穷序歹l 扛。 ，如果下面的假设条件成立 ( i ) f ：l p 一舻是连续映射， ( i i ) g ：r “一e 是既开又闭的满射， ( i n ) ( 2 1 5 ) 成立， ( i v ) 变分不等式( 2 1 4 ) 的解存在 第三章随机变分不等式的算法 3 1 引言和预备知识 文献【1 3 】引入了一类广义强非线性拟变分不等式，并给出了两种求解变 分不等式解的迭代算法s i d d i q i 等【14 1 对这类变分不等式问题提供了扰动 的i s h i k a w a 迭代算法我们讨论这类变分不等式的随机化问题的解的迭代 算法 设日为可分的实h i l b e r t 空间，( z ，y ) 表示z 和的内积，2 日表示日 的一切非空子集所形成的集合族c ( h ) 表示日中切非空紧子集所形成 的集合族，8 ( 日) 表示日中切b o r e l 子集所形成的* 代数我们总假设 ( q ，a ) 是个可测空问，其中a 是q 上的代数对a d e ( 日) ， h a m ( e d ) ：= m a x s u p d s t 0 ，d ) ，s u p d i s t q ：，g ) ) z e c# d 表示集合c 和d 之间的h a u s d o r f f 度量如果kc 日是个闭凸子 集，n k ( ) ：日一耳表示投影算子 定义3 1 ，：n 一日称为是可测的，若对v b 8 ( 日) ，扣n ：，( 1 ，) 口 一4 ；t ：q 一2 片称为是可测的，若对v b 层( 日) ，扣q ：t ( w ) n b 口 a ，：q h 一日称为是连续随机算子，如果对每一o 日，( ，z ) ：n 一日 是可测的，并且对每一t l ，n ，) ：日一日是连续的t ：n 日一2 8 称 为是连续随机映射，如果t ( ，z ) 关于t ，n 可测，关于z h 是h a u s d o r f f 连续集值映射 定义3 2 映射叶：n 一日称为是映射f ：q 一2 8 的可测选择，如果q 是可 测映射并且对所有q ，口( ) f ) 定义3 3 ，l ：q h 一日称为是十连续的，如果对每一 q ，存在 目) 0 使得 8 似t l ，2 ) 一m ，u ) l l q ( ) i i 一训，v ，日 g ：n 日一日称为是强单调的，如果存在映射口：n _ ( 0 ，+ o 。) 使得 白( ，z ) 一9 ( ，”) ，z f ) a ( w ) l l = 一0 2 ，v z ，f 日，t ，q 1 3 第三章随机变分不等式的算法 1 4 t ：q h 一2 日称为是乒l i p s c h i t z 连续的，如果存在芦：n 一【0 ，+ o 。) 使 得 h ( t ( w ，z ) ，t ( w ，) ) p ( w ) l l z g ，v 。，y e 卸n 引理3 1 如果 ，：n 日一日是连续随机算子，则对任意可测映像f ：q h ，i ( w ，) ) 也是可测的 引理3 2 如果t ：nx h c ( h ) 是鼠连续的随机映像，那么对任意可测 映像“：n h ，r ( w ，让) ) ：n g ( 日) 是可测的 引理3 ，3 假设a ：n c ( h ) ，t ：l l c ( h ) 是两个可测映射， t l ：n j j f 是丁的可测选择，则存在a 的可测选择 ：0 一日使得 l t u ( w ) 一口扣) | l h ( a ) ，t ( ) ) ，v u n 引理3 4 设耳是日中的非空闭凸子集。7 1 1 , ：qxh h ，( ，z ) = m ( w ，z ) + k 那么对每一口h ， 尸k 佃牟) 扣) 二m m ，孑) + r f 扣一竹洳。) ) ，v ( t e ，。n h 所谓随机广义拟变分不等式是指求可测映像z ：n h ，：n 一日， 口：n - 日使得u ( w ) 丁( t j ( 伽) ) ，u ( 叫) a ( 埘，土( ”) ) ，9 ( 1 i j ，z ( ) ) 耳，z d w ) ) ，并且 扣( ) 一 ( t i ) ，可一9 ( ，( 删) ) ) 0 ，v w q ，可k ( t ，z ( ) ) ，( 3 1 ) 其申t ：n 嚣_ c ( 嚣) ，a ：q e _ e ( 嚣) ，套：q 嚣_ 耳 注3 1 ( 3 1 ) 的确定形式是d i n g 【1 3 】中讨论的广义强非线性拟变分不等式问 题如果对任意 n 和任意z h ，g ，功= 。，那么( 3 1 ) 就是文献i s i 的( 5 1 2 1 3 2 算法及其收敛性 定理3 ，1 可测映像。：q 一日，“：0 一h ，p ：n 一日满足( 3 1 ) 当且 仅当对每一 n ，u ( w ) 丁( ，z ( ) ) ，v ( w ) a ( w ，z ( ) ) ，9 ( ，z ( t ，) ) k ( w ，z ( ) ) 。并且 p ( t ，工( 甜) ) ；m ( ”，工( 掣) ) + 局f 细( 埘，。( ”) ) 一m ( t ，z ( 叫”+ “埘) p ( 掣) 一越( 纠) ) ) 其中p q 一( 0 ，+ ) 是可测函数 第三章缒枕麦分不尊式的算洼 算法3 1 设耳为日中的非空f j l 凸子集，m ：n 日一日，g ：n 日一日 是连续随机算予，t ：n h c ( 日) ，a ：n 日一c ( z ) 是连续随机映射， 耳汩砷= m ( w ，功+ k ，p ：n 一( 0 ，+ o o ) 是可测函数 任意取定可谢映像知：n 一日，根据引理3 2 和r i m m e l b e r g 【1 5 j ，存 在可测选择知，伽：f 2 一日使得u o ( w ) 以w ，跏( ) ) 铀( ) a ( w ，卸( 口) ) 令 乱j = 翱细) 一“2 ，。工o ( 研) ) + 州 ，勘) ) + j k ( 夕( 埘，z o ( 叫) ) 一m ( w ，= 0 0 0 ) ) + “叫) ( ( ) 一t 0 ( 1 r ) ) ) + e l ( ) ， 其中e l ：n 一日是扰动可测陕像 根据引理3 1 ，z l ：q 一日是可测映像由引理33 可知，分别存在 r 细，z l m ) ) 和a ，z l ) ) 的可测选择t 1 和n 使得 i i j q ( w ) 一t l o ( t l ，) 0 厅( t ( 叫，l ( t f ，) ) ，丁( 叫，知( ) ) ) l l 口1 佃) 一t 船( t ，) 0 詹( a ( t ，瓤( 埘) ) ，a ( 叫，勘( 恤) ) ) ， v w n 令 x 2 ( w ) = z l ( ) 一9 ( ，x l ( w ) ) + m ( ，? l 扣) ) + r f ( 9 ( ”，z l ( t t ) ) 一m 细，王i ( t f ，) ) + “硼) 扣l ( 叫) 一蛳( 埘) ) ) + e 2 ( 伽) ， 其中如：n 一日是扰动可测映像 继续上述过程可得到可测映像序列 ( ”) ) ， 1 ，l ) ) ， ) 使得 t k ( t t ，) 丁( 叫，、( ) ) ，嵋( ) ea ( t ，z 。( ) ) ， i ) 一t ，l 一1 m ) 1 1 厅( 丁( w ，靠) ) ，r ( ，n i ) ) ) i l ( t t i ) 一t b 卜，( 埘) 8 青( a ( ，霉。( 埘) ) ，a ( t | ，卜l ( ) ) ) ( 3 2 ) 靠( ) = h l 扣) 一9 扣，靠一i c w ) ) + m ( ，靠一1 ) ) + 攻( 9 f 口，一i p ) ) 一m ( 奶如一i ) ) + 烈( 一t ( w ) 一一l 扣) ) ) + e ，i ( 1 l ，) ， 其中e n ：n 一日是扰动可测映像 第三章随机变分不等式的算法 注3 2 如果去掉扰动项，上面的算法是【1 3 】中算法3 1 被推广到随机他的情 形 定理3 2 设耳为胃中的非空闭凸子集，m ：n 一日是口( 仲) l i p s c h i t z 连续随机算子，g ：q 日一嚣是a l ) - 强单调，玩( 砂“p s 吐d 乞z 连续随 机算子，t ：n - 一c ( u ) 关于g 是铆沁) 一强单调，岛( 钳) 一l i p s c h i t z 连续 随机算子，a ：n 日一c ( h ) 是1 知) l i p s c h i t z 连续随机算子，且对每一 n ，h h k 。) = 0 如果可测函数p ：q 一( o ，+ ) 满足 一絮糕糟籽| 茄鹣， 。， 其中口( t 】) ：= 1 2 叩c w ) 一、，巧_ = = 互苫i 面r 干丽，6 ( ) ：墨c 通( t u ) 解( 伽) 一 2 。( ) a 2 ( 锄) 7 ) + 腭) a ；如) 一所( t ，) 腭) 十f ( ) o 那么算法所产生 的迭代序列 ) ) ， t ，l 似) ， ) 分别收敛于r ( ”) ，矿( ) ，矿) ，并 且( r ( ) ，矿油) ，矿) ) 是问题( 3 1 ) 的解 证明因为投影算子是非扩张映射， i z + l ( v a ) 一如= 粒。) 一g ( w ，霉。陋) ) + m ( 解，n ) ) + j k 扫( 们，岛。( 伽) ) 一m ( w ，岛。( 伽) ) + p ( ) ( ( ) 一t ，；( t ，) ) ) + e m + l ( t l ，) 一? p 1 ( ) + 夕( t ， r t - l ( 叫) ) 一m ( ，筠t l ( 删) ) 一蜀r ( 9 ( t l ，暑。一l c w ) ) 一m ( w ，z 。一l ( t t j ) ) + p ( t f ，) ( 珥一l ( ) 一 a n 一1 ( ) ) ) 一c ，l ( ) 0 s2 1 1 m ( w ，z 。( t i ) ) 一m ( w ，, z n - l ( ) ) 0( 3 4 ) + 0 。) 一g ，l ) 一( 9 ( ，靠) ) 一9 ( ，一l ) ) ) 0 + 0 9 ( 1 l ? ，。( 埘) ) 一窖( 埘，o 。一1 ( t f ) ) 一烈 ) ( t ，。( t 7 ) 一t ，l l ( ”) ) 0 + “埘) 0 v 。( ) 一v n l ( 叫) 8 + 1 1 8 。+ l ( t ，) 一e - l ( ) i i 因为g ：n 胃一日是d l ) 强单调，尻( w ) - l i p s c h i t z 连续随机算子， i i z 。w ) 一2 。一1 ( t ，) 一( g ( w ，。( ) ) 一口( t ，如一l ( ) ) ) 2 = z 。( ”) 一z ，l ( w ) 1 1 2 2 。( t f ) 一z ，1 ( ”) ，g ( 留，o ”( ) ) 一9 佃，南。一l ( w ) ) ) + i i g ( 埘，舀。( 如) ) 一9 ( 彬，。一i ( 脚) ) 酽( 3 5 ) ( 1 2 q i ( 叫) + 钟( 叫) ) 8 z 。( 叫) 一4 ；一z ( 叫) 酽 第三章随机麦分不等式的算法 1 7 因为t ：q 日一c ( 日) 关于g 是劬扣) 一强单调，岛) 一l i p s c h i t z 连续随 机算子， 1 1 9 ( 埘，南；( 叫) ) 一9 ( 叫，z 。一l ( t l ，) ) 一_ p ( 叫) ( u 。( 埘) 一t k l ( 硼) ) j 1 2 = l i g ( w ，z c w ) ) 一g ( w ，x n - 1 ( ”) ) 酽 一2 p ( w ) c q ( ，岛t ( ) ) 一g ( w ，x n l ( ) ) ，。( ) 一t ，l l ( ) ) + 矿) u t ，i 细) 一t ，l 一1 ( w ) i 1 2 ( 3 6 ) ( 1 2 a 2 ) 反) + 矿细j 詹( ) ) h 扣) 一靠一t ( ) f 2 因为t ，l ：q h 一日是口( 加) 一l i p s c h i t z 连续随机算子，由( 3 4 ) - ( 3 6 ) 可以 得到 h 而h l ( t 一z ( 9 1 1 口( ) ”而。( 纠一与。一l ( ) l l + 小；”i ( ) 一n ( ”，( 3 7 ) 其中。 e ( w ) ：= 2 n ( w ) 4 - p ( 埘) 7 ( t ，) + 、l 一2 a l ( ) + 暖( 叫) + 、1 2 哑( w ) p ( 叫) + 矿( 暂) 鹰( 搿j - 根据条件( 3 3 ) ， 0 0 ，f ( x o + 扫一z ) ) 一，( 知) 0 ，根据可微泛函的定义，我们有对 任意的y 只 ( 舳h ，) = 规丛地芋也掣 o 换句话说，一，( 知) p x o ) 一因为z o 只我们有 s 一勒= x ：a = 0 ，啦，z ) = o ，v d ，( 知) ，。 基于上面的等式并运甩定理4 1 ，我们得到 - f ( 勖) ( s 一劫) 一= a c y 。) + c o n e 啦：i ，( 知) ) ； 即存在ae y 和以0 “f ( z o ) ) 使得 ，( 知) + a + a + 以q = o t e f 口 参考文献 1 s i b o n y ，m ，m e t h o d e si t e r a t i v e sp 坩蛔胁删咖e ti n e q u a t 伽sd d e r w e 8p a r t l e u e an o n l i n e o r e s 出功p em o n o t o n e , c a l c o i o ，v 0 1 7 ，p p 6 5 - 1 8 3 ， 1 9 7 0 2 k o r f e l e v i c h ，g m ，t h e 蜀：t r 叼m 出咖m e t h o d 加f i n d i n gs a d d l ep o i n t s a n do t h e rp 巾b c m m a t e c o n ，v r 0 1 1 7 p p 7 4 7 7 5 6 ，1 9 7 6 3 k h o b o t o v ，e n ，a 肘d d 析d 酣妇lo ft h e 厩晰叼m d 诂时m e t h o d o rs o l v i r _ g v a r i a 幽s o 血田耐妇ds o m eo 蟛m i m t e np r o b 栅, u s s rc o m p u t s - t i o n a lm a t h e m a t i c sa n dm a t h e m a t i c a lp h y s i c s ，2 7 ，p p 1 4 6 2 _ 1 4 7 3 ，1 5 9 7 ， 1 9 8 7 4 m a r c o t i 瑶，p ，a p p l i c a t u m 口，k w b o t o v 8a l g o r i t h mt o 蒯t 硼脚如叼t 靠 牲帮a n d n e t w o r k e q c i l i b r i u m , h 彘日n b t i s y s t e m s a n d o p e r a t i o n a l r c s e s r c k v b l2 9 ，p p 2 5 8 - 2 7 0 ，1 9 9 1 5 s o l o