（应用数学专业论文）强单调逆变分不等式的投影算法.pdf

摘要 变分不等式问题广泛应用在自然科学、经济均衡和工程计算等诸多领域逆交分 不等式是广义变分不等式的一种特殊形式，逆变分不等式像变分不等式一样，广泛地 出现在交通控制、经济平衡和管理科学等诸多领域，因此研究本课题具有实际应用意 义 本文利用投影技巧给出了新的求解强单调逆变分不等式的投影算法和自适应投 影算法，并在适当假设条件下，证明了两种算法的收敛性 全文共分为四部分，主要内容如下： 第一部分预备知识概述了变分不等式和逆变分不等式的定义，一些变分不等 式和逆变分不等式问题的基本理论，并给出了一些关于投影算子的基本性质，以及投 影算法研究进展 第二部分提出了新的求解强单调逆变分不等式问题的投影算法，在适当假设条 件下，证明了算法的收敛性 第三部分提出了新的求解强单调逆变分不等式问题的自适应投影算法，证明了 算法的收敛性，该算法的收敛性与参数的选取无关 最后，总结了本文的主要工作，并将从三个方面对逆变分不等式问题作深入研究 关键词：变分不等式；逆变分不等式：投影算法；强单调 p r o j e c t i o na l g o r i t h mf o rs t r o n g l ym o n o t o n e i n v e r s ev a r i a t i o n a li n e q u a l i t y a b s t r a c t v a r i a t i o n a li n e q u a l i t i e sp r o b l e m sh a v ew i d e l ya p p l i c a t i o n si ns c i e n c e ，e n g i n e e r i n ga n d e c o n o m i c s i n v e r s ev a r i a t i o n a li n e q u a l i t i e si s as p e c i a lc a s eo fg e n e r a lv a r i a t i o n a l i n e q u a l i t i e s i n v e r s ev a r i a t i o n a li n e q u a l i t i e ss i m i l a rw i t hv a r i a t i o n a li n e q u a l i t i e s ，h a v ea w i d er a n g ea p p l i c a t i o n si nd i f f e r e n tf i e l d s s u c h a st r a n s p o r t a t i o ns y s t e mo p e r a t i o n ， e c o n o m i ce q u i l i b r i u ma n do p e r a t i o n a ls c i e n c e t h e r e f o r e ，h o wt os o l v ei n v e r s ev a r i a t i o n a l i n e q u a l i t i e sp r o b l e mh a si m p o r t a n ta p p l i c a t i o nv a l u e s t h i sp a p e rp r o p o s e sap r o j e c t i o na l g o r i t h ma n das e l f - a d a p t i v ep r o j e c t i o na l g o r i t h m s f o rs o l v i n gi n v e r s ev a r i a t i o n a li n e q u a l i t i e sb a s e do np r o j e c t i o nt e c h n o l o g y u n d e rs u i t a b l e a s s u m p t i o n s ，w es h o wt h a tt h ep r o p o s e da l g o r i t h mc o n v e r g e s t h ep a p e ri sd i v i d e di n t of o u rp a r t s t h er e s u l t so fc h a p t e r sa sf o l l o w i n g ： t h ef i r s tp a r ti sp r e l i m i n a r i e s w ei n t r o d u c ed e f i n i t i o no fv a r i a t i o n a li n e q u a l i t i e sa n d i n v e r s ev a r i a t i o n a li n e q u a l i t i e s s o m ep r o p e r t i e so fp r o j e c t i o no p e r a t o r ， s o m eb a s i c t h e o r yo fv a r i a t i o n a li n e q u a l i t i e s a n di n v e r s ev a r i a t i o n a l i n e q u a l i t i e s a r ei n t r o d u c e d m o r e o v e ht h ed e v e l o p m e n to ft h ep r o j e c t i o nm e t h o d sa r es t u d i e d i nt h es e c o n dp a r t ，p r o p o s e san e wp r o j e c t i o na l g o r i t h mf o rs o l v i n gi n v e r s ev a r i a t i o n a l i n e q u a l i t i e sb a s e do np r o j e c t i o nt e c h n o l o g y u n d e rs u i t a b l ea s s u m p t i o n s w es h o wt h a t t h e p r o p o s e da l g o r i t h mc o n v e r g e s i nt h et h i r dp a r t ，p r o p o s e san e ws e l f - a d a p t i v ep r o j e c t i o na l g o r i t h m sf o rs o l v i n g i n v e r s ev a r i a t i o n a li n e q u a l i t i e sb a s e do np r o j e c t i o nt e c h n o l o g y w es h o w t h a tt h ep r o p o s e d a l g o r i t h mc o n v e r g e s t h ec o n v e r g e n c e o ft h i sm e t h o dh a sn o t h i n gt od ow i t ht h ep a r a m e t e r t h el a s tp a r ti sac o n c l u s i o na b o u tt h em a i nw o r ki nt h i st h e s i s ，a n dw ew i l ld of u r t h e r r e s e a r c hi ni n v e r s ev a r i a t i o n a li n e q u a l i t i e sf r o mt h r e ea s p e c t s k e yw o r d s ：v a r i a t w n a li n e q u a l i t i e s ；i n v e r s ev 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 na l g o r i t h m ； s t r o n g l ym o n o t o n e d i r e c t e db y ：p r o f h a nh a i s h a n ( p h d ) a p p l i c a n tf o rm a s t e rd e g r e e ：l iy u - m i n g ( a p p l i e d m a t h e m a t i c s ) ( c o l l e g eo fm n t h e m a t i c s i n n e rm o n g o l i au n i v e r s i t yf o rn a t i o n a l i t i e s , t o n g l i a o0 2 8 0 4 3 c h i n a ) 内蒙古民族大学硕士学位论文作者声明 本人声明：本人呈交的学位论文是本人在导师指导下取得的研究 成果。对前人及其他人员对本论文的启发和贡献己在论文中做出了明 确的声明，并表示了感谢。论文中除了特别加以标注和致谢的地方外， 不包含其他入已经发表或撰写的研究成果。 本人同意内蒙古民族大学保留并向国家有关部门或资料库送交 学位论文或电子版，允许论文被查阅和借阅。本人授权内蒙古民族大 学可以：旖本人学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签 日期：型丝年么月望日 内蒙古民族大学硕士学位论文 1 1 本文的选题意义及背景 第一章绪论 经典的变分不等式问题是由p h i l i ph a r t m a n 和g u i d os t a m p a c c h i a 在2 0 世纪6 0 年 代提出来的【l 】，之后g u i d os t a m p a c c h i a 在文献团中加以推广目前变分不等式问题已 经是运筹学领域中的一个重要分支，广泛应用在自然科学、经济均衡和工程计算等诸 多领域【3 一】所以，对求解变分不等式问题的研究具有重要的理论意义和现实意义 在变分不等式问题中映射与自变量互换位置的数学问题称之为逆变分不等式问 题，它是广义变分不等式的一种特殊形式，【8 1 中详细说明了逆变分不等式像变分不等 式一样，广泛出现在交通控制、经济平衡和管理科学等诸多领域虽然逆变分不等式 有广泛的应用，但还没有引起人们的足够重视，对于逆变分不等式的性质，f 9 】1 1o 】只对 其中一些简单问题有些零碎的研究而对于逆变分不等式的算法，何炳生等在】【1 2 】中 针对单调逆变分不等式和“黑箱”条件下的逆变分不等式给出了几种算法，包括精确近 似点算法，非精确近似点算法，预测校正近似点算法和自适应预测校正近似点算法 等，且在一定条件下，证明了这些算法的收敛速度是线性的 1 2 变分不等式的基本概念和基本结论 变分不等式问题( 记为v i ( k ，) ) 1 1 3 】为：设k 是有限维e u c l i d e a n 空间r ”中的非 空闭凸子集，f 是从尺”到自身的一个映射，关于x 的变分不等式v i ( k ，) 是求一个 x r ”，使得 x k ，( y x ) r f ( x ) 0 ，v y k ， ( 1 1 ) v i ( k ，f ) 的解集记为s o l ( k ，f ) 问题( 1 1 ) 是一般变分不等式的定义伴随变分不等式问题在工程和科学各个领域 中的广泛应用，学者们又提出了各种其他的变分不等式问题包括广义变分不等式 2 强单调逆变分不等式的投影算法 【1 4 】、混合拟变分不等式【1 5 】、带约束变分不等式【1 6 1 等它们都是一般变分不等式问题( 1 1 ) 的推广下面列举几种一般变分不等式问题( 1 1 ) 的推广： 1 ) 广义变分不等式g v i ( k ，f ) ：设k 是有限维e u c l i d e a n 空间尺”中的非空闭凸 子集，是k 从到月”的一个连续映射，g 是从尺”到自身的一个映射，关于工的广义 变分不等式g v i ( k ，f ) 是求一个x r ”，使得 x k ，【g ( y ) 一g ( x ) 】7f ( 工) 0 ，v g ( y ) k 2 ) 广义变分不等式g v i ( k ，f ) ：设k 是有限维e u c l i d e a n 空间r ”中的非空闭凸 子集，f 是k 从到r ”的一个连续映射，g 是从尺“到自身的一个映射，关于工的广义 变分不等式g v i ( k ，f ) 是求一个x r ”，使得 工k ，l v g ( x ) 】7f ( x ) 0 ，b 少k 3 ) 混合变分不等式m v i ( k ，f ) ：设k 是有限维e u c l i d e a n 空间尺”中的非空闭凸 子集，f 是k 从到尺”的一个连续映射，伊( 9 是尺”到尺u 佃 的连续泛函，关于x 的混 合变分不等式m v i ( k ，f ) 是求一个x r ”，使得 x k ，( y 一工) r f ( x ) + 9 ( j ，) 一缈( x ) 0 ，v y k 4 ) 混合拟变分不等式m q v i ( k ，f ) ：设k 是有限维e u c l i d e a n 空i 日r ”中的非空闭 凸子集，f 是k 从到的一个连续映射，缈是r 一r ”到ru 栅) 的连续二元泛 函，关于x 的混合拟变分不等式m q v i ( k ，f ) 是求一个x r 一，使得 x k ，( y - x ) 7f ( 工) + o f y ，x ) 一缈( x ，x ) 0 ，v ) ，ek 5 ) 带约束的变分不等式：设足= 缸r l a , 6 ，扛l ，2 ，刀 ，f 是从尺”到自 身的一个映射，关于x 的变分不等式v i ( k ，f ) 是求一个x r “，使得 工k ，( y x ) 7f ( x ) 0 ，v y k 目前，求解变分不等式的算法己经有很多：投影算法、临近点算法、内点法、牛 顿型方法、交替方向法等这其中临近点算法、内点法、牛顿型方法、交替方向法是 内蒙古民族大学硕士学位论文 3 求解变分不等式比较有效的算法，它们各有各的优点，但是当投影比较容易计算时， 投影算法就成了求解变分不等式问题最简单的方法之一 下面给出一些在研究收敛性分析时常用的概念和基本结论首先为了叙述方便， 我们记1 日l 为欧氏范数，并给出以下定义 定义1 1 1 1 3 】设，是从足”到自身的一个映射，若存在常数三 0 ，使得 忙( x ) 一，( y ) 忙训x y 0 ，v x ，ye g ”， 则称f 在r ”上l i p s c h i t z 连续 定义1 2 【1 3 1 设，是从彤到自身的一个映射， 1 ) 若 ( x 一夕) r f ( y ) 0j ( x j ，) 7f ( z ) 0 v x ，y r ” 则称f 在r ”上是伪单调的 2 ) 若 ( x 一少) 7 ( ，( x ) 一，( j ，) ) 0 v x ，y r ” 则称f 在r ”上是单调的若一，是单调的，则称f 是负单调的 3 ) 若 ( x y ) 7 ( ，( x ) 一，( 少) ) 0 ， v x ，y r ”， 则称f 在r ”上是严格单调的 4 ) 若存在常数c 0 ，使得 ( f ( x ) 一f ( y ) ) 7 - c l l x - y l l 2 ，v x ，y 尺疗， 则称f 在r “上是强单调的 5 ) 若存在常数c 0 ，使得 ( ，( x ) 一，( y ) ) 7 ( x y ) _ c l l f ( x ) 一f o ) 1 1 2 ，v x ，y r ”， 则称f 在r ”上是c o c o e r c i v e 的 定义l - 3 17 1 设k 是足“中的非空闭凸集，若中的序列 满足 、，、夕、，、，、，、， 彩 脚 q 卸 哪 忉 0 q 0 0 u 0 4 强单调逆变分不等式的投影算法 i i x + l x i i _ l l x 一工8 ，v x ek ， ( 1 8 ) 则称序列 在k 上是f e j e r 单调，且序列 ) 在k 上有界且至多有一个聚点 定义1 4 【1 3 1 设k 是犬“中的非空闭凸集，我们把向量1 ，在k 上的投影算子兀r ( ，) 定义为， h r ( v ) = a r g l i l i n 舡一v l i l u k ) ( 1 - 9 ) 投影算子有如下性质这些性质在后面的证明中发挥莺耍的作用 定理1 1 【1 8 】设k 是r ”中的非空闭凸集，则有以下结论成立 1 ) ( v - i - i k ( v ) ) 7 ( w - h r ( i ，) ) 0v v g 1 ，w ek ， 2 ) 1 1 7 k ( v ) - l - i rl l , - , ，l l v v ，w er “， 3 ) 1 1 1 - - i k ( v ) - w l l 2 0 v w 0 2 一i l v h k ( v ) 1 1 2 1 3 逆变分不等式的基本概念和基本性质 v v r ”，w k ( 1 - 1 0 ) ( 1 - 1 1 ) ( 1 1 2 ) 设k 是r ”中的非空闭凸集，f 是从r ”到自身的一个映射，求工r ”，使得 f ( x ) k ，( 1 p - - f ( x ) ) 7x 0 ，v v k ，( 1 1 3 ) 这样的问题称为逆变分不等式隅1 ，记作i v i ( k ，) 它是由问题( 1 1 ) 中的自变量与映射 相互交换位置得到的如果，的逆算子为g ，记y = f ( x ) 和x = f _ 1 ( y ) = g ( y ) ，则问 题( 1 1 3 ) 可以化成 y k ，( y - y ) 7 g ( j ，) 0 ，v y k ( 1 - 1 4 ) 这也是我们称( 1 1 3 ) 为逆变分不等式的原因还有一部分逆变分不等式要将( 1 - 1 3 ) 中的改为为了与i v i ( k ，f ) 有所区别，我们把求x r ”，使得 f ( x ) k ，( v - - f ( x ) ) 7x 0 ，v v k ， ( 1 - 1 5 ) 这样的逆变分不等式，记作i v i ( k ，f ) l 在一般变分不等式( 1 1 ) q b ，我们经常会遇到一类约束型的变分不等式问题【1 3 】，其 中的k 是关于x 的多面体在逆变分不等式中，我们同样也会遇到类似的关于x 的约 内蒙古民族大学硕士学位论文 5 束型逆变分不等式i v i ( k ，) f ( x ) k ( w ) ，( v f ( x ) ) r x 0 ，v v k ( w ) ， 其中 或者 k ( w ) = w r i a 7 。w 6 ，w ) ， k ( w ) = w er ”i a7 w = b ，w e w ， 这里a r “”，b r m , wcr “是一个简单闭凸集 ( 1 1 6 ) ( 1 1 7 ) ( 1 1 8 ) 我们都可以在实际生活中找到以上几种逆变分不等式问题，下面举例说明【8 j ： 1 ) 通过调整利率达到控制存款率问题中的逆变分不等式i ( k ，f ) ( 1 1 3 ) 设存款率q ( x ) 为利率x 的函数，则存款率是利率的单调递增函数设政府一定要 将存款率控制在k = e l , b 】这个范围内假设最有利于银行的自身利益的最好利率为 而，在能够帮助政府实现调控存款率的同时，银行当然希望利率的变动值尽可能的小 一些现记利率的调整量为z ，并记f ( x ) = q ( x o + x ) 若x 为最优调整量，则有 如果a f ( x ) 0 ，( 1 - 2 2 ) r ( x ，r ) = f ( x ) - i 膏( f ( x ) - r x ) = 0 ( 1 - 2 3 ) 同理，x 是逆变分不等式i v i ( k ，尸) 的解当且仅当它满足投影方程 f ( x ) = 兀r ( ，( x ) + f x ) ，v f 0 对于给定的x r ”，投影方程( 1 - 2 2 ) 的残量函数( 1 - 2 3 ) 有下面的性质，该结论对证 明强单调逆变分不等式投影算法的收敛性起重要作用 定理1 7 对于任意给定的x r ”和f r 0 ，有 8 ，( x ，r ) l l - i i ，- ( x ，r ) 8 ， ( 1 2 4 ) 和 妊剑娅剑 ( 1 - 2 5 ) fz 1 4 投影算法的研究进展 从上个世纪6 0 年代开始，众多数值方法被运用于求解变分不等式问题，其中最重 要的是投影算法投影算法的主要思想是运用投影的概念，建立起变分不等式问题和 不动点问题的等价关系，然后利用w i e n e r - h o p f 方程求解口0 1 投影算法每步迭代的计 算量非常小，只是一些到可行集的投影以及函数值的计算所以它已经成为求解变分 不等式问题最简单的方法之一，且很适合于解决大规模的问题 显式投影算法最早由g l d s t e i n 2 1 1 ，l e v i t i n p o l y a k 】提出 ，”= 兀量( ，- r , f ( x ) ) 当映射，强单调，l i p s c h i t z 连- 续g q 满足定条件时显式投影算法是全局收敛 的但是显式投影算法存在以下两个缺点： 1 ) 算法的收敛性需要估测l i p s e h i t z 常数三和强单调定义中的c ，而这两个参数在 实际问题中是不易估测 2 ) 映射，强单调条件太强，使一大类问题的求解不能采用此方法 内蒙古民族大学硕士学位论文1 1 为了克服显式投影算法的上述缺点，文献【1 5 】【2 3 】提出自适应投影算法文献【1 5 】中 的自适应投影算法适用于解决混合变分不等式问题，而文献中的自适应投影算法 适用于解决线性变分不等式 此外，为减弱收敛性对强单调的限制，k o r p e l e v i c h t 2 4 】提出了预测校正投影算法， = 1 - i k ( x 一r k f ( x ) ) ， x 纠= 兀r ( 一气f ( ) ) 其中- 七= 1 - i r ( 一r k f ( x ) ) 为预测步，”= 1 - i r ( 一r k f ( x ) ) 为校正步 显然，预测- 校正投影算法中，预测步和校正步中步长吒的选取准则是相同的，这 也使得算法的收敛速度较慢为此，文献2 5 1 中改进了上述方法，在预测步和校正步中 采用不同的步长，加快了预测校正算法的收敛速度 之后，b s h e 2 6 i 提出的收缩投影法： x 。“= x 一垆( x ，t ) d ( x ，乙) ， 其中 d ( x r ) = ，( 工，f ) 一r f ( x ) 一f ( x - r ( x ，r ) ) 】， 贴2 笔挚， r ( x ，r ) = x - h k i x r f ( x ) 】 由于收缩投影法的收敛速度较慢，d r h a na n dh o n gk l o 在【1 8 1 中改进了收缩投影 法： 工“1 = n r i x 一y p ( x k , 0 ) d ( 石，0 ) 】， d ( x ，r ) = r ( x ，r ) + r f ( x 一，( x ，f ) ) ， p ( x ，f ) = 厂( x , r ) r 8 d d ( ( x x ，, r r ) ) l r ， r ( x ，f ) = x h 胃i x r f ( x ) 】 随后x h y a ha n dd r h a n 在【2 7 】中又改进了收缩投影法： “= n r 一护( x ，t ) d ( ，? o ) 】， d ( x ，r ) = 厂( 工，r ) + r f ( x 一，( z f ) ) ， 1 2强单调逆变分不等式的投影算法 p ( x , r ) = m i n ( 1 1 - - - ! - ) 石a 瓦忑r ( x 瓦, r ) rd丽(x,r) r ( x ，f ) = x - y i r x - r f ( x ) 1 5 本文主要研究内容 第二章，运用显式投影算法的思想，给出新的求解强单调逆变分不等式的投影算 法2 1 ，并证明该算法的收敛性 第三章，利用自适应准则，讨论了强单调逆变分不等式的自适应投影算法，此算 法中我们无须知道强单调定义中的参数c 的值，在这点上算法3 1 要优于算法2 1 内蒙古民族大学硕士学位论文1 3 第二章强单调逆变分不等式的投影算法及其收敛性 在这一章，假设逆变分不等式i v i ( k ，f ) 的解集s 非空，映射f 连续、可逆，且f 在k 上是强单调的运用显式投影算法的思想，给出新的求解强单调逆变分不等式的 投影算法，并证明该算法的收敛性 2 1 强单调逆变分不等式的投影算法 算法2 1 初始步初始点x o k ，置k = 0 ： “，( ) ，? 步骤一若f ( x ) = 兀k ( f ( x 2 ) 一) ，算法终止否则转步二； 步骤二 选取以 0 ，令f ( x “1 ) = n r ( f ( ) 一气) ，置k = k + l ，转步骤一 2 2 强单调逆变分不等式的投影算法的收敛性 首先给出定理1 6 和定理1 7 的证明 定理1 6 石是逆变分不等式i v i ( k ，f ) 的解当且仅当它满足投影方程 f ( x ) = 兀r ( f ( x ) - r x ) ，v r 0 ， 即 r ( x ，r ) = f ( x ) 一兀k ( f ( x ) - r x ) = 0 证明若x 是逆变分不等式i ( k ，f ) 的一个解，那么有f ( x ) k 而k 是r ”中 的非空闭凸集，所以由( 1 1 0 ) 有 ( v - i - i k ( 1 ，) ) 7 ( f ( x ) 一兀k ( v ) ) 0v v r 4 ， 在上式中，令1 ，= ，( x ) 一r x ，可得 【f ( x ) 一r x - i - i r f ( x ) 一r x 】) 7 f ( x ) 一兀r f ( x ) 一r x 】) 0 由r ( x ，r ) = f ( x ) - r i k ( f ( x ) - r x ) ，上式可以写成 r ( x ，f ) 一r x 7 r ( x ，f ) 0 ， 从而有 1 4强单调逆变分不等式的投影算法 l ，( x ，r ) 1 1 2 ，( x ，f ) r x ( 2 1 ) 另外，由于n r ( f ( x ) - r x ) k ，x 是逆变分不等式i v l ( k ，f ) 的一个解，由( 1 1 3 ) 可得 即 兀f i f ( x ) 一r x 一f ( x ) 7 x 0 ， r ( x ，f ) 7x 0 显然，由( 2 1 ) 和( 2 - 2 ) 可得，( x ，f ) = 0 反之，在( 1 1 0 ) q b ，取1 ，= f ( x ) 一f x ，可得 f ( x ) - r x - f l r 【，( x ) 一f x 】) 7 w - f l r i f ( x ) 一r x 】) 0 v w ek ， r ( x ，f ) = 0 ，则有兀r f ( x ) - r x 】- f ( x ) k ，代入不等式( 2 3 ) ，可得 f ( x ) k ，( w - - f ( x ) ) 7x 0 ，v m ，k ， 所以x 是逆变分不等式i v i ( k ，f ) 的一个解证毕 定理1 7 对于任意给定的x r ”和f f 0 ，有 0 ，( x ，f 。) l l - l l ，( 工，r ) | l ， 和 娅纠也型 证明忙矧挪么只须跏娜证 ( 0 ( t 一二) 0 f 由( 1 l o ) 有 ( v - l i ( v ) ) 7 ( f i r ( ，) 一忉0v ，尺疗，w k ， 在上式中令w - - - 兀 f ( x ) - r 明，1 ，= f ( x ) - r x ，并利用 兀足 f ( x ) - r x l - h r f ( x ) - r 工】= ，( z ，f ) - - r ( x ，f ) ， 可得 t r ( x ，f ) 一r r x r ，( 而r ) 一，( 毛r ) ) 0 同理可得 r r ( x ，f ) 一f r x r r ( x ，r ) - r ( x ，r ) ) 0 ( 2 2 ) ( 2 - 3 ) ( 2 4 ) ( 2 - 5 ) ( 2 6 ) 内蒙古民族大学硕士学位论文 1 5 将( 2 5 ) ，( 2 6 ) 相加，可得 r r ( x ，r ) - r 。r ( x ，f ) ) 7 1 ，( x ，r ) 一r ( x ，f ) ) 0 ， 展开得 ( f + r ) ，( x ，r ) 7 ，( x ，f ) 季r 0 ，( x ，f ) 1 1 2 + r i i ，( x ，f ) 0 2 将上式两边同时除以l l 厂( x ，f ) l | 2 ，可得 ( f + fy z t 2 + f 1 i 叩( 2 - 4 ) 成立，定理得证 引理2 1 设x 。s 是强单调逆变分不等式i v i ( k ，f ) 的解，则对于任意x r ”，有 ( 肌) 一f ( x ) ) k v ) ( 1 一捌以，r ) 1 1 2 ( 2 - 7 ) 证明由x s 是强单调逆变分不等式i v i ( k ，f ) 的解，在( 1 1 3 ) 中取 ，= 兀r ( f ( x ) - r x ) 得 t x “( y i r ( f ( x ) - r x ) - f ( x ) ) 之0 在( 1 1 0 ) 中取v = f ( x ) 一t x w = f ( x ) 得 ( 2 8 ) ( f ( x ) 一r x ) - l - i r ( f ( z ) 一r x ) ) 7 丌髟( f ( x ) - r x ) - f ( x ) ) 0 ( 2 9 ) 将( 2 - 8 ) 与( 2 9 ) 相加得 ( f ( x ) - r x ) - i - i r ( f ( x ) - r x ) + r x ) r 1 - i 量( f ( x ) - r x ) - f ( x ) ) 0 ( 2 l o ) 将r ( 五f ) = y ( x ) - l - i 并( f ( x ) - r x ) 代x ( 2 1 0 ) 得 r ( x ，r ) 一z ( x - - x ) 7 ( f ( x ) 一f ( x ) ) 一，( x ，f ) ) 0 ( 2 11 ) 由( 1 - 6 ) ，( 2 - 1 1 ) 可化为如下形式 ( ，( x ) 一f ( x ) ) 7 ，( x ，r ) - l l r ( x ，哪+ f ( ，( x ) 一f ( x 。) ) 7 一x ) 一r ( x 一石) 7 r ( x ，f ) - i i ，( x ，f ) 1 1 2 + f c l i x 一工0 - r ( x z ) 7 ，( x ，f ) - l l 巾1 1 2 + 卜。，一吾b r ，一l ，( v ) l | 2 1 6 强单调逆变分不等式的投影算法 ( 1 一丢) ，谢证毕 定理2 1 设x s 是强单调逆变分不等式i v i ( k ，f ) 的解， x ) 是由算法2 1 生成 的点列，则 m ) 川x 小胁) 川刈2 - ( 1 一别以圳2 ( 2 - 1 2 ) 证明由引理2 1 得 0 f ( + 1 ) 一，( x ) 1 1 2 = u f ( x k + i ) 一f ( x k ) + f ( x k ) 一f ( x + ) 1 1 2 = i i f ( x ) 一，( z + ) 一，( ，吒) 1 1 2 ) 川z ) i | 2 - ( 1 一别以圳2 - 证毕 定理2 2 设x s 是强单调逆变分不等式i v i ( k ，f ) 的解， 是由算法2 1 生成 的点列，如果 吒) 满足o i n f 气乙s u 。p r k 2 c ，则 x 收敛到x 证明假设；s 是强单调逆变分不等式i v i ( k ，f ) 的解， 当 0 i n t 吒q s u p r k 0 和z 1 k 夕置k i l 歹 第七步 对于和气一。，若忆，1 ) 0s 占，算法终止否则找最小的非负整数丘( 从 厶= 0 开始) ，令气= 气一，以及 f ( x “1 ) = 兀( f ( ) 一q x ) ， ( 3 1