（计算数学专业论文）求解一类非对称单调变分不等式的交替方向法.pdf

摘要 在过去的几十年里，有限维变分不等式( 包括互补问题) 的理论和算 法已经广泛地应用到运输计划、社会经济分析、能量模型及博奕论等领 域，取得了迅速的发展特别地，变分不等式的算法研究已经成为了计 算数学的一个热点课题本文研究了求解一类单调非对称变分不等式的 交替方向迭代法 交替方向法( a d m ) 是求解具有线性等式或线性不等式约束的变分不等 式( v i ) 的一种有效算法这种算法的基本思想是通过交替地求解一个具 有简单约束的线性变分不等式及一个良态的非线性方程组来逼近变分不 等式问题的解这种方法的一个显著优点是两个子问题都易求解，并有 较成熟的算法实现本文对原有的求解非对称变分不等式的交替方向法 作了如下的推广和改进： 1 原有的的方法用于分别求解带等式约束的问题和带不等式约束的 问题本文用于求解同时带这两种约束的问题，证明了方法的收敛性 2 提出了两类非精确交替方向法允许在求解两个子问题时可以是 非精确的，在合理的假设下，仍然证明了方法的收敛性 3 建立了自适应交替方向法因为，当卢 0 是常数时，求解v i ( k ，厂) 与求解v i ( x ，p f ) 等价，但数值实验表明，在相同精度的条件下，迭代的 次数明显地依赖于口值的选取对于单独的一个问题，我们难以选择一 个合适的参数口，因此，我们提出了自适应的交替方向法，这种方法根 据每步迭代信息自动地调整参数口 最后，对第二类非精确交替方向法和自适应交替方向法给出了数值 实验结果，证实了算法的有效性 关键词：变分不等式；交替方向法；非精确：自适应 i i a b s t r a c t o v e rt h ep a s td e c a d e s ，t h et h e o r ya n da l g o r i t h m so ff i n i t e - d i m e n s i o n a l v a r i a t i o n a l i n e q u a l i t y ( i n c l u d i n gc o m p l e m e n t a r i t yp r o b l e m s ) h a sb e e n d e v e l o p e dr a p i d l y a n d a p p l i e db r o a d l y t o t r a n s p o r t a t i o np l a n n i n g ， s o c i o e c o n o m i c a n a l y s i s ，e n e r g ym o d e l i n g ，g a m et h e o r y a n ds oo n p a r t i c u l a r l yt h ea l g o r i t h m s o ff i n i t e d i m e n s i o n a lv a r i a t i o n a li n e q u a l i t y h a v eb e e nav e r yi m p o r t a n tr e s e a r c hs u b je c ti nc o m p u t a b l em a t h e m a t i c s t h i sp a p e r p r o v i d e ss o m er e s e a r c h e so nt h ea l t e r n a t i n gd i r e c t i o nm e t h o df o r s o l v i n gac l a s so fa s y m m e t r i cm 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 a l t e r n a t i n gd i r e c t i o n m e t h o di se f f i c i e n tf o r s o l v i n g ac l a s so f v a r i a t i o n a l i n e q u a l i t i e s w i t hl i n e a r e q u a l i t i e s o rl i n e a r i n e q u a l i t i e s c o n s t r a i n t s t h eb a s i ci d e ao ft h em e t h o di st oa p p r o x i m a t et h es o l u t i o no f v a r i a t i o n a li n e q u a l i t i e sv i as o l v i n ga l t e r n a t e l yal i n e a r v a r i a t i o n a l i n e q u a l i t y w i t h s i m p l e c o n s t r a i n t sa n daw e l l - c o n d i t i o n e d s y s t e m o f n o n l i n e a re q u a t i o n s ar e m a r k a b l em e r i to ft h ea l t e r n a t i n gd i r e c t i o nm e t h o d i st h a ti ti se a s yt os o l v es u b p r o b l e m s i na d d i t i o n ，t h es u b p r o b l e m si nt h e a l t e r n a t i n g d i r e c t i o nm e t h o dc a nb es o l v e db ym a n ye x i s t i n ge f f i c i e n t m a t h e m a t i c a l a l g o r i t h m s t h ep a p e rg e n e r a l i z e s a n d i m p r o v e s t h e t r a d i t i o n a la l t e r n a t i n gd i r e c t i o nm e t h o do nt h ef o l l o w i n ga s p e c t s ： 1 t h et r a d i t i o n a la l t e r n a t i n gd i r e c t i o nm e t h o dw a sa p p l i e dt o r e s p e c t i v e l ys o l v eac l a s so fv a r i a t i o n a li n e q u a l i t i e sw i t hl i n e a re q u a l i t i e so r l i n e a ri n e q u a l i t i e sc o n s t r a i n t s t h em e t h o do ft h ep a p e ri sa p p l i e dt os o l v ea c l a s so fv a r i a t i o n a li n e q u a l i t i e sw i t hb o t hl i n e a r e q u a l i t i e sa n dl i n e a r i n e q u a l i t i e sc o n s t r a i n t s w eh a v ep r o v e dt h ec o n v e r g e n c eo ft h em e t h o d 2 w ep r o p o s et w oc l a s s e so fi n e x a c td i r e c t i o nm e t h o d sa n da l l o wt o i n e x a c t l ys o l v i n gt h et w os u b - p r o b l e m s w eh a v ep r o v e dt h ec o n v e r g e n c eo f t h em e t h o du n d e rm i l da s s u m p t i o n s 3 w ep r o p o s es e l f - a d a p t i v ea l t e r n a t i n gd i r e c t i o nm e t h o d a l t h o u g ht h e s o l u t i o n o fv i ( k ，f ) i si n v a r i a n tu n d e rm u l t i p l y i n gfb ys o m ep o s i t i v e s c a l a r 口，y e tt h en u m e r i c a le x p e r i m e n th a ss h o w nt h a t t h en u m b e ro f i t e r a t i o n sd e p e n d ss i g n i f i c a n t l yo nt h ep o s i t i v ep a r a m e t e r w h i c hi sa c o n s t a n ti nt h eo r i g i n a la l t e r n a t i n gd i r e c t i o n i ng e n e r a l ，i ti s d i f f i c u l tt o c h o o s eap r o p e rp a r a m e t e r9f o ri n d i v i d u a lp r o b l e m s t h u sw ep r o p o s e i l l 硕士学位论文 s e l f - a d a p t i v ea l t e r n a t i n g d i r e c t i o nm e t h o dw h i c h a d j u s t s t h es c a l a r p a r a m e t e ra u t o m a t i c a l l yp e ri t e r a t i o nb a s e do nt h em e s s a g eo ft h ei t e r a t e s w eh a v ep r o v e dt h ec o n v e r g e n c eo ft h em e t h o du n d e rm i l da s s u m p t i o n s f i n a l l y w ep r e s e n ts o m en u m e r i c a lr e s u l t s t h e s en u m e r i c a lt e s t ss h o w t h a tt h es e c o n di n e x a c ta l t e r n a t i n gd i r e c t i o nm e t h o da n dt h es e l f - a d a p t i v e a l t e r n a t i n gd i r e c t i o nm e t h o da r ee f f i c i e n ta n ds i g n i f i c a n t 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 ；a l t e r n a t i n gd i r e c t i o nm e t h o d ； i n e x a c t ；s e l f - a d a p t i v e i v 表5 1 表5 2 表5 3 表5 4 表5 5 表5 6 表5 7 表5 8 表5 9 附表索引 对于不同的初始点c p u 的运行时间和迭代次数3 8 改变非对称和非线性程度以后的结果3 8 对于不同的初始点和松驰因子主程序所对应的迭代次数3 9 不同的仇数值实验结果3 9 不同的缩放因子所对应的主程序迭代次数k 4 0 不同的方法所对应的迭代次数4 1 不同的方法所对应的迭代次数4 1 不同的方法所对应的迭代次数4 2 不同的方法所对应的迭代次数4 2 v i i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立 进行研究所取得的研究成果。除了文中特别加以标注引用的内 容外，本论文不包含任何其他个人或集体已经发表或撰写的成 果作品。对本文的研究做出重要贡献的个人和集体，均己在文 中以明确方式标明。本人完全意识到本声明的法律后果由本人 承担。 作者签名：期3 z 扫霄 日期：枷b 年毕月占日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的 规定，同意学校保留并向国家有关部门或机构送交论文的复印 件和电子版，允许论文被查阅和借阅。本人授权湖南大学可以 将本学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在一年解密后适用本授权书。 2 不保密回。 ( 请在以上相应方框内打”) 作者签名： 导师签名： 哪抽葭 阳l 日期：抛占年中月善日 日期： f 年y 月日 1 1 变分不等式 第1 章引言 变分不等式早已于二十世纪六十年代产生，近年来，变分不等式问题( 玎) 的研究有了迅速发展，由于它的理论和方法不仅是非线性最优化的一个重要部分， 而且在微分方程、力学、控制论、对策论、经济平衡理论、交通运输、社会和经 济模型等许多方面都有着重要的应用，有着广泛的应用前景，数学规划中的许多 基本问题也可以归结为一个变分不等式问题来研究，因此，变分不等式问题的研 究和应用是数学规划和运筹学等领域中的一个重要课题对w 的研究大致可分为 理论和算法两大研究方向理论方面的研究焦点集中于玎解的存在性、唯一性和 灵敏性等而算法方面主要是研究如何引进和借助于各种技术、概念和思想等以 建立各种类型的订的具体求解方法( 见文献【l 3 】) 从推广看，对玎的研究又 有将标准变分不等式推广到广义变分不等式g v i ( k ，) 和拟变分不等式 q v i ( k ，f ) 再到广义拟变分不等式g q v i ( k ，f ) ，所有这些同时推动了一般点到集 映射的发展及其在数学规划中的作用还有学者从更基本的拓扑和泛函的观点上 研究了无限维赋范空间的变分不等式阕题 下面只讨论一维欧氏空间五”中的变分不等式 定义1 1 1 设k 是，l 维欧氏空间最”中的一个非空闭凸子集，f ：k _ r “是一个 连续映象，变分不等式问题( 简记为v i ( k ，f ) ) 是：求向量x k ，使得 0 一z + ) 7 厂o + ) 0 ， v x k ( 1 1 ) x 称为v z ( k ，f ) 的可行集 变分不等式问题v i ( k ，f ) 的对偶形式( 简记为d v l ) 定义如下：求向量工e k ， 使得 0 一x + ) 7 f ( x ) 0 ， v x k ( 1 2 ) 求解v z ( k ，) 与求解d v i 紧密相关我们用世+ 、k 。分别表示呱1 1 ) 、r i o 2 ) 的 解集 设g 为h 阶正定矩阵，x 掣，记向量x 的欧氏范数为： i | x l l = ( x 7 x ) “2 = 彳+ 十+ ， 求解一类非对称单调变分不等式的交替方向法 矩阵g 意义下的范数为0 x 峙= o g x ) “2 在一些算法中，需要映象，的单调性，下面给出映象，的单调性定义 定义1 1 2 【4 j 设k 是r ”中的一个非空凸子集，厂：k 寸r ”是一个映象， 1 ) 称厂是一个单调映象，若有 一v ) 1 【，( “) - f ( v ) 】0 ，v u ，v k ( 1 3 ) 又如果对任意“、v k ，u v ，上述不等式严格成立，则称厂是严格单调映 象 2 ) 称厂为k 上( 以口为模数) 的强( 或一致) 单调映象，如存在常数口 0 使得 ( 甜- v ) 1 厂( “) 一，( v ) 】口1 i 甜一v i l 2 ， v u ，v k ( 1 ，4 ) 根据定义，强单调映象必是严格单调映象，严格单调映象必是单调映象 3 ) 称，在足上( 以卢为模数) 强制的，如存在常数卢 0 使得 ( “- v ) 1 厂( “) 一厂( v ) 】卢1 l 厂( “) 一，( v ) 旷，v u ，v k( 1 5 ) 变分不等式问题的解的存在性与唯一性结果有： 引理1 1 1 0 1 映象厂在芷上严格单调，则变分不等式问题w ( k ，厂) 最多有一个 解 引理1 1 2 【1 】设k 为胛维欧氏空间r ”中的非空闭凸集，映象厂：k 斗r ”为一连 续映象当，在五上强单调时，则变分不等式问题玎( 足，力有唯一解 定义1 1 3 称，是r ”中的l p s c h i t z 连续映象，若存在常数，使得 | | ，( x ) 一，( y ) l l 工0x y i i ，v x ，y e r “( 1 6 ) 定义1 1 4 设q 是r “中的一个非空凸子集，向量x 在集q 上欧氏范数下的投影 晶( x ) = a r g m i n ( 1 i x y 1 1 v y q ) g 范数意义下的投影为 圪n ( x ) = a r g m i n l i x y i k v y q 设q 是r ”中的一个非空凸子集，向量x 在集q 上欧氏范数下的投影圪( ) 具有 下列性质5 1 ： 1 ) 一晶( x ) ，o n ( x ) - y ) 0 ，v y q ( b o u r b a k i - c h e n e y - g o l d s t e i n 不等式成立) 2 2 ) ( 晶 ) 一圪( 力，x - y ) 0 ，v x ，y r “( 单调性) 3 ) i i 圪( x ) 一晶( y ) l l - 0 ，则x 是v i ( k ，力的解的充要条件是 工= ，k 【x + 一舟r ( x ) 】 于是求解v i ( k ，f ) 等价于求 e ( x ) _ x 一最陋一t i f f ( x ) 】 ( 1 7 ) 的零点，即x + 是w ( 芷，) 的解p ( ，) = 0 变分不等式与非线性分析( 如互补问题、不动点问题、最优化问题等) 有着 密切的联系，有如下特例： 1 ) 如果足取为r ”中的开集，文献【8 】称v ( k ，力为广义方程组，即 ，( x ) = 0 ； 若映象，是仿射映象，即f ( x ) = m x + q ，则上述问题等价于经典的线性方程组： m x = - q ( 1 8 ) 2 ) 若，( x ) 是可微函数口( d ：r ”寸r 的梯度且，( 功的j a c c o b i 阵v f ( x ) 为对称 矩阵，则v i ( k ，厂) 等价于约束优化问题 j 曲疗( 引( 1 9 ) 【s t x k 此时v i ( k ，) 的一个解x 为约束优化问题( 1 9 ) 的一个驻点，文献【4 】称为驻点问题 3 ) 当k 仁r ”是一个凸锥时，则玎等价于互补问题( c p ) ( 见文献 9 】) ：求向量 x k ，使得 f ( x ) k ，x * t f ( x + ) = 0 ， ( 1 1 0 ) 其中墨为置的对偶锥，即：k = 缸r ”l x r y 0 ，v y k ) 当可行集k 取为非负象限彤= p 掣l x t o ，i = l ，h ) ，且厂是仿射映象时， ( 1 1 0 ) 称为线性互补问题( l c e ) 3 求解一类非对称单调变分不等式的交替方向法 鞍点问题与优化问题紧密相关设x r 。，y cr ”是两个闭凸集， l ：r 。r “j r 是可微凸一凹函数，也就是，对给定的y y ，三( ，y ) 是凸的，对 给定的x x ，三( x ，) 是凹的鞍点问题定义如下：求x + x ，y y ，使得 三( ，y ) 茎上( 工+ ，) 蔓l ( x ，y + ) ，v x z ，y y ( 1 _ 1 1 ) 记 = 1 + 研，u = 工y ，定义映象g ：r ”斗r “如下： g 如加( ￥鼢 ， 嘲 注意到我们这样定义的g 是单调的 引理1 1 4 【1 0 1 鞍点问题( 1 1 1 ) 等价于变分不等式问题：求向量“u ，使得 一“+ ) 7 g ( u + ) 0 ， v u u ( 1 1 3 ) 在最优化中，鞍点问题是消除函数约束的有力工具我们考虑如下的优化问 题： m i n f o ( x ) 1 x d ， ( 1 1 4 ) 其中 d = x x l i ( x ) s 0 ，i = 1 ，- - ，1 ) ， ( 1 1 5 ) ，：r _ r , i = 0 ，m 是凸可微函数 x = x r 7 i x ，0 ，w j ) ，j ( 1 ，) ( 1 1 6 ) 然后我们再定义问题( 1 1 4 ) - - ( 1 1 6 ) 相应的l a g r a n g e 函数： l ( x ，_ y ) = 五( x ) + 蹦( x ) ( 1 1 7 ) i = l 为了得到问题( 1 1 4 ) - - ( 1 1 6 ) l ：j ( 1 1 1 ) ( 1 1 7 ) 的关系，我们需要某种约束品性成立也 就是，考虑如下假设： ( c ) 所有的函数z ，i = l ，m 是仿射，或者存在一点i 使得z ( _ ) ，。，f = 1 , 2 ，。，n 当k = k ，x = 彤时，文献【3 6 】中提出了交替方向法求解，当k = k 2 ，x = 彤 时，文献【3 6 3 8 】中提出了交替方向乘予法求解但在上述两种方法中，其中一个 子问题仍是非线性非对称变分不等式，在本质上，求解它们与求解原问题一样困 难于是在文献 3 3 】中，建立了一种新的有效的交替方向法，只需交替地求解一个 具有简单约束的凸二次最优化( 或一个对称线性互补问题) 及一个良态的非线性 方程组即可 1 4 本文结果 针对文献 3 3 1 0 0 提出的交替方向法，本文从三个方面考虑了一类非对称单调 变分不等式的求解方法： 1 、推广文献 3 3 1 中提出的交替方向法只适用于分别带等式或不等式约束的 玎，以用于求解同时带等式及不等式约束的变分不等式 2 ) 文献【3 3 冲建立的交替方向法要求子问题是精确求解的，在实际计算时， 不可能精确求解子问题，有时也没必要，因此我们提出非精确交替方向法，允许 7 求解一类非对称单调变分不等式的交替方向法 子问题非精确求解 3 ) 建立了自适应交替方向法因为，当 0 是常数时，求解v i ( k ，) 与求 解v i ( k ，p f ) 等价，但数值实验表明，在相同精度的条件下，迭代的次数明显地依 赖于口值的选取对于单独的一个问题，我们难以选择一个合适的参数卢，因此， 我们提出了自适应的交替方向法，这种方法根据每步迭代信息自动地调整参数 最后还给出了两类方法的数值实验结果，与原交替方向法进行了比较，数值 结果表明，本文中提出的方法是可行而有效的，对原方法有一定的改进 8 一 第2 章带等式与不等式约束的 交替方向法及收敛性 本章考虑如下结构的非对称变分不等式： v i ( k ，f ) 0 一x ) 7 “，) 2 0 ， 慨ek ， ( 2 1 ) k = z e r “i 马x = b l , b 2 x b 2 , z 己0 ) tb le r ”“”，b 2e 丑，b l r 4 ，6 2 r ， 且w ( 砷可为非对称的 通过对订( 2 1 ) 的约束引入l a g r a n g e 乘子，可构造如下形式的变分不等式： r , 7 ( n ，f ) 0 一“+ ) 7 f ( “) 0 ， v n ，( 2 2 ) 一，：( 竺科。料， y = r “r ：彤，卢 0 是常数 本章假设，是k 中的单调连续映象，v z ( n ，) 的解集o + 非空 2 1 一个定理 v ( 2 1 ) 与附( 2 2 ) 的解之间有如下关系 定理2 1 1若“= ( x ，y ) 是( 2 2 ) 的解，则x 是( 2 1 ) 的解 证明：由( 2 2 ) 有 0 一“+ ) 7 f + ) o ， v u q e x - - x 7 ( 爱 孤 ”肛y ( x x ) 7 【( x ) 一a 7 y 】+ ( y y ) 7 ( 止- a ) 0 ， 由x 的任意性，特别地，取x = x ，则得 由x 的任意性，特别地，取x = * ，则得 ( j ，一y ) 7 ( 血- a ) 0 ，、吵y v x e r “，y e y ( 2 1 3 ) ( 2 4 ) 令y = 篓 ，y = 萎 ，其中y 。r “，y ：r ：，y ，r ：，y ：r ”，- y ：丑：， 订联，由( 2 4 ) ，我们有 7 ：三二2 。，v ) ，。r ”，y ：r ：，y ，e r ： ( y l y ：) 7 ( b l x - b 1 ) + ( y 2 一y ：) 7 ( b 2 x 一6 2 ) + c v 3 一y ：) x 0 ， v y i r ，y 2 r ：，y 3 胄：，( 2 5 ) 由y 。，y ：，y ，在各空间中的任意性，特别地，我们在( 2 5 ) 式中 1 ) z r y 。= y ：，y 2 = y ：，则 魄一以) 7 x + 0 若取弘= y ：+ s ，s 。= ( o ，o ，1 ，o ，o ) ，( i = 1 , 2 ，n ) ，可得z 0 第t 4 - 2 ) 取y ：= y ：，y 3 = 以，则 ( y 1 一y ：) 7 ( b l x 一“) 0 若取y l = y 卜( 最工+ 一岛) ，则有| f b l x + - b 1 i l a o ；若取y l = y i 一( 马z 一岛) ，则有 0b l x 4 - b l0 0 因此i ib l x + 一b li i = 0 ，b l x 一b l = 0 3 ) 取y l = y ：，y ，= y ；，则类似于1 ) 可推得：b 2 x 一b 2 0 由1 ) 2 ) 3 ) 可知x + k 下面我4 f l i 正o x ) 7 f ( x + ) 0 ，v x k 由( 2 3 ) 式及x k 得： ( x x ) 7 【( x ) 】( x - - x ) 7 a 7 y 一( y y ) 7 ( 4 x 一日) ， = ( a x a x ) ”y 一( a x + 一) 7 ( y y ) 1 0 ( 垤r ”，y y ) ( v x r ”，y y ) 、1， 。n。儿。弘 一 i 2 3 y y y ，。l m y 2 y 3 b i x 一b l b 2 x b 2 x = ( 岛x b , x ) 7 以+ ( x - - x 。) 7 正 一( 岛f 一6 2 ) 7 ( 咒一y 2 ) - x ”0 一西) _ y 1 一y 1 y 2 一y 2 y s y s = ( b 2 x 一6 2 ) 7 y ：一( 丑2 x + 一6 2 ) 7 y 2 + x 7 y ；一x * t y 3 ， 取y 2 = o ，y 3 = 0 ，得 ( v x k c r ”、 ( v y 2 r ：，y 3 r n ) ( x x ) 7 【( x ) 】( b 2 x 一6 j ) 7 y ；+ x r y ； 0 + 0 = 0 ，( v x kc y r ”) 因为 0 ，所以o x ) 7 f ( x ) 0 这样，我们就证明了若“= ( x ，y + ) 是问题( 2 2 ) 的解，则z 是问题( 2 1 ) 的解 2 2 算法与收敛性 基于定理2 1 _ l ，构造交替方向法，即交替迭代求解分别关于x 和y 的两个子 问题 算法2 1 交替方向法( 加m ) 给定占 0 ，y ( 0 ，2 ) ，卢 0 ，初值x oe r ”，置七# 0 步骤1 计算y y ，使得 7 一y ) 7 ( 爿x 一日) 一a , o f ( x ) 一4 7 y 】 0 ， v y y ( 2 6 ) 步骤2 若1 1 。) 一a 7 y 。i i s ，则停止计算，输出x 。，y 。否则进行下一步 步骤3 计算x “1 太“，使得 o a x “1 ) = 0 ， ( 2 7 ) 这里 o a x ) = x + ( 力一【x 2 + g ( x ) 】+ y 【( x ) 一a r y 】( 2 8 ) 耵?x 一 一 一 即即x ，爿【 置k ：= k + 1 ，转步骤1 注2 1 步骤2 的合理性将由下面的引理2 2 1 得出 由引理1 1 3 ，求解w ( q ，f ) 等价于求p ( “) ：= 甜一p n 阻一f ( “) 】的零点这里 砌，= 。y i f 一( x 胁) - a r 。y 血一训 c z 为证明收敛性定理，我们先引入几个引理 引理2 2 1 对任意给定的x r ”，若y 是( 2 6 ) 的解，则有 一r 0 ( x ) 一a 。y i i 到i 口( “) l 峰1 + 0 4 1 1 20 ( x ) 一a2 y0 ( 2 1 0 ) 证明：根据e ( u ) 的式( 2 9 ) ，v x r ”，y y ，我们有 1 1 ( x ) 一a 7 y i l 2 马ie ( u ) 2 = | lp f ( x ) 一a 7 y l l 2 + 0y e r y 一( a x 一口) 】1 1 2 ( 2 1 1 ) 另一方面，根据引理1 1 3 ，我们有( 2 6 ) 的解y 满足 y = 0 ( y 一( 彳x 一4 ) + 4 厨“x ) 一a y 】 ( 2 1 2 ) 因为投影是非膨胀的，也就是： i ib ( y ) 0 ( y ”) j j 訇i y 一少。| | ，砂，y ，( 2 1 3 ) 由( 2 1 2 ) 和( 2 1 3 ) ，得 f f y 一最【y 一( a x 一日) 】| | = 0 j ，一( a x 一口) + a ( p f ( x ) 一a 1j ，) 卜0 陟一( a x 一口) 】f f | | a f l f ( x ) 一a 。y 】| l 0 a i f l f ( x ) 一a 。y 叭 由上面的不等式及( 2 “) ，引理2 2 1 得证 因为求解玎( q ，f ) 等价于求e ( u ) 的零点，很多算法均以| | e ( u ) | | 作为误差界， 从这条引理我们知，| 1 ( z ) 一a 7 y i i 也可以作为误差界，它从数值上度量了( x ，y ) 偏 离真解的程度，从而我们可以取i i ( x ) 一a 7 yl l 岔作为算法的终止准则 引理2 2 2 设扣。= ，y k ) ) 是由算法a d m 产生的序列，v ( x ，y + ) q ，我们 有 ( x 一x + ) + f l f ( x 2 ) 一f ( x ) 】) 7 【( x ) 一a 7 y 】到i ( 茏) 一a 7 y 1 1 2 ( 2 1 4 ) 证明：f l j ( 2 2 ) ( 2 9 ) ，若( x + ，y ) 是解，则 ) = a y 且 ( y 一y ) 7 ( a x 一) 0 ， v y y 因为y 。y ，所以 。1 2 ( y 一y 。) 7 ( d a x ) 0 另一方面由算法a d m ，我们又有 ( y 一y k ) 7 ( 4 x 一口) 一a n ( x ) 一a 7 y 】 0 ( 2 1 5 ) + ( 2 1 6 ) ，得 ( y + 一y k ) 7 爿( x 一z ) 一a n ( x 。) 一a 7 y 】 0 ， ( 2 1 5 ) f 2 1 6 ) ( x 一z + ) 一【( z ) 一a y 1 1 7 ( 彳7 y + 一a 7 y ) 0 在上式中用( x + ) 替换a 7 y ，有 ( x 一x ) 一【( x ) 一a 7 y 2 】) 7 【酽0 ) 一( x ) 】+ 【( x ) - a 7 y 】 0 ， ( x 。一x + ) + f l f ( x ) 一f ( x ) 】 7 【( x 。) 一a 7 y 】 到lp f ( x ) 一a 7 y 1 1 2 + ( x 一x ) 7 【，( x ) 一f ( x ) 】， 由上式及， 的单调性，引理2 2 2 得证 引理2 2 3 设伽= ( x k , y ) ) 是由算法a d m 产生的序列，v ( x ，y ) q + ，我们 有 0o ”一x ) + 卢【厂( x 。“) 一f ( x ) 】0 2 q i ( x - - x + ) + n f ( x ) - f ( x ) 】1 1 2 - r ( 2 一y ) l l ( x 2 ) 一a 2 y 21 1 2 ，( 2 1 7 ) 证明：对于算法2 1 ，由( 2 8 ) 有 ( x “1 一x ) + 卢【厂( x “1 ) 一f ( x ) 】= ( x 一x ) + f l f ( x ) - f ( x ) 卜，【( x ) 一4 7 y 】 由( 2 1 4 ) 有 i io “1 一x ) + 所，( x “1 ) - f ( x + ) 卅 爿i ( x 一x ) + j o f ( x ) 一f ( x ) 卜r 1 9 ( x ) 一a 7 y 】| i 2 刊1 “x ) 一x + ) + p f ( x ) 一f ( x ) 】1 1 2 + i i y ( x ) 一a 7 y 】1 1 2 2 y ( x 一x + ) + n f ( x ) 一f ( x 。) 】) 7 【j f 抓z ) 一a 7 y 】 q i ( x 一x ) + 所，( x ) 一f ( x ) 】f | 2 2 ，0 ( x 。) 一a 7 y 1 1 2 + 0 y o ) 一a 1 y 2 洲2 爿i ( x 。一x ) + b f ( x ) 一f ( x ) 】1 1 2 一r ( 2 一，) | ib y ( x ) 一a r y 1 1 2 引理得证 此引理说明，由交替方向法所产生的序列 l i ( x 一x ) + n f ( x ) 一f ( x + ) 川) 是 单调下降的，不等式( 2 1 7 ) 告诉我们，若值0 ) 一a 7 y l i 较大，则当前迭代效 果较好，相反的，若值0 o ) 一a 7 y i l 充分小，由式( 2 1 0 ) n 其后的说明，当前 迭代点“= ( ，y 。) 就是瞰2 2 ) 的一个好的近似解 定理2 2 1 设( “= ( x k , y 2 ) ) 是由