（应用数学专业论文）求解一类单调变分不等式的交替方向法.pdf

求解。一类单调变分不等式的交替方向法 摘要 自从二十世纪六十年代产生以来，有限维变分不等式的理论和算法得到了迅 速的发展，并且广泛地应用到经济平衡理论，交通运输，社会经济模型等方面因此， 变分不等式问题的研究和应用已经成为了计算数学的一个热点课题本文研究了 一类单调非对称的变分不等式的交替方向法交替方向法( a d m ) 是求解带线性等 式或线性不等式约束的变分不等式的一种有效的方法实质上，交替方向法是一种 分解方法，它是通过交替地求解一系列子问题而得到原变分不等式的解的方法原 有的交替方向法需交替求解一个具有简单约束的线性变分不等式和一个良态的非 线性方程组，且这两个子问题易于求解并有较成熟的算法实现本文对原有的求解 单调非对称的变分不等式的交替方向法作了如下的改进和推广： 1 在原有交替方向法的基础上提出了一类非精确自适应交替方向法( i s a a d m ) ， 允许对其中一个子问题非精确求解，并证明了该方法的收敛性 2 提出了一类新交替方向法( n a d m ) 求解变分不等式问题，并在合理的假设 下，我们证明了新方法的收敛性，且这种方法允许两个子问题都是非精确求解的 3 我们提出新自适应交替方向法( n s a a d m ) 对于我们提出的新交替方向法， 数值实验表明，迭代的步数与时间与所取的参数o t ，卢有关，然而我们很难去选择一 个合适的参数口，p ，因此我们提出新自适应交替方向法，对其中的参数口，口进行自 适应调整，这种自适应算法根据每步迭代信息自动地调整参数a ，卢，并证明了算法 的收敛性 最后，我们对非精确自适应交替方向法和新交替方向法给出了数值实验结果， 证实了算法的有效性 关键词：变分不等式；交替方向法；非精确方法；自适应 硕士学t ：) = 论文 a b s t r a c t f r o m1 9 6 0 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 lv a r i a t i o n a li n e q u a l i t i e s h a v eb e e nd e v e l o p e dr a p i d l ya n da p p l i e db r o a d l yt ot h et h e o r yo fe c o n o m i ce q u i l i b r i u m ， 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 a l - e c o n o m i ca n a l y s i sa n d s oo n p a r t i c u l a r 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 yh a v eb e e nav e r yi m p o r t a n tr e s e a r c hf i e l di n c o m p u t a t i o n a lm a t h e m a t i c s t h i st h e s i sp r e s e n t ss o m ew o r k si nt h ea l t e r n a t i n gd i r e c t i o n m e t h o df o rs 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 g d i r e c t i o nm e t h o di se f f i c i e n tf o rs o l v i n gac l a s so fv a r i a t i o n a li n e q u a l i t yw i t hl i n e a re q u a l i t y o rl i n e a ri n e q u a l i t yc 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 e s 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 i e sv i as o l v i n ga l t e r n a t e l yt w ok i n d so fs u b - p r o b l e m s t h i s t r a d i t i o n a lm e t h o d sn e e d sa l t e r n a t e l ys o l v i n gal i n e a rv a r i a t i o n a li n e q u a l i t yw i t hs 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 ds y s t e mo fn o n l i n e a re q u a t i o n s ，a n dt h es u b - p r o b l e m s c a nb es o l v e de a s i l yb ym a n ye f f i c i e n tm a t h e m a t i c a la l g o r i t h m s t h et h e s i sg e n e r a l i z e s a n di m p r o v e st 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 do nt h ef o l l o w i n ga s p e c t s ： 1 o nt h eb a s i so ft h et r a d i t i o n a lm e t h o d ，w ep r o p o s ea ni n e x a c ts 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 d t h en e wm e t h o da l l o w so n ek i n do fs u b - p r o b l e m st ob e s o l v e di n e x a c t l y 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 ean e wa l t e r n a t i n gd i r e c t i o nm e t h o da n dp r o v et h ec o n v e r g e n c eo f t h en e wm e t h o du n d e rm i l da s s u m p t i o n s t h i sm e t h o da l l o w st oi n e x a c t l ys o l v et h et w o k i n d so fs u b - p r o b l e m s 3 w bp r o p o s en e ws 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 t t l 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 tt h en u m b e ro fi 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 e p a r a m e t e rq ，p b u t ，i ng e n e r a l ，i ti sd i f f i c u l tt oc h o o s eap r o p e rp a r a m e t e rq ，p t h u s w ep r o p o s en e ws 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 dw h i c ha d j u s t st h es c a l ep 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 d t 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 l t e s t ss h o wt h a tt h ei n e x - a c ts 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 da n dt h en e wa l t e r n a t i n gd i r e c t i o nm e t h o d a r ee f f i c i e 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 tm e t h o d ； s e l f - a d a p t i v e i i i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 成果除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已 经发表或撰写的成果作品对本文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明本人完全意识到本声明的法律后果由本人承担 作者签名： 豫承日期： 。9 了年j 月y 弓日 学位论文版权使用授权书 作者签名：蒜番 日期：如9 年j 月小日 聊雠。问护醐旷p 哆日 硕士学位论文 1 1变分不等式 第1 章绪论 变分不等式( y 歹) 自从二十世纪六十年代产生以来，得到了迅速的发展，在微 分方程，力学，控制论，对策论，经济平衡理论，交通运输，社会和经济模型等很多方 面有着重要的应用，应用前景非常广阔而且数学规划中的很多问题也可以归结为 变分不等式问题来研究，因此，变分不等式问题的研究和应用也是数学规划和运筹 学等领域的一个重要课题对变分不等式的研究主要分为理论和算法两大方面理 论研究的焦点集中在变分不等式解的存在性，唯一性和灵敏性等而算法方面主要 是研究如何引进和借助各种技术，概念和思想等以建立各种类型的变分不等式的 具体解法( 见文献【l 一3 1 ) 从推广上看，对变分不等式的研究又有将标准变分不等 式推广到广义变分不等式g v i ( k ，) 和拟变分不等式q v i ( k ，厂) 再到广义拟变分 不等式g q v i ( k ，) ，所有这些都推动了一般点到集值映射的发展及其在数学规划 中的应用还有学者从更基本的拓扑和泛函的观点上研究了无限维赋范空间的变 分不等式问题 本文只讨论n 维欧氏空间舻中的变分不等式 定义1 1 1 n 设k 是佗维欧氏空间舻中的一个非空闭凸子集，：k _ 形是一个 连续映射，变分不等式问题( 简记为v i ( k ，) ) 是：求向量矿k ，使得 ( z z ) t ，( z + ) 0 ，v z k ， k 称为v i ( k , ，) 的可行集，记v i ( k , ，) 的解集为k + 定义1 1 2 1 4 设k 是伊中的凸锥，是形到自身的映射，广义互补问题( 简记为 g c p ( k ，) ) 是：求向量矿k ，使得 ，( z 。) j f ，( z + ) r z 。= 0 ，( 1 2 ) 其中是k 的共轭锥，f = 可舻：y t x 0 比k ) 定义1 1 3 【4 】设，是衍到自身的映射，非线性互补问题( 简记为n c p ( k ，) ) 是： 求向量矿毋= z r i x o ，i = 1 ，2 ，n ) ，使得 ，( 矿) e 霹，( 矿) 7 矿= 0 若，是仿射映像，则( 1 3 ) 称为线性互补闯题( 简记为l c p ( k ，) ) 设g 为死阶正定矩阵，z 舻，记向量z 的欧氏范数为： i l x l l = ( z ) 垆= 扫i 而 一1 一 ( 1 3 ) 求解一类单调变分不等式的交替方向法 矩阵g 意义下的范数为i i = l l g = ( x t g x ) 1 2 定义1 1 4 【5 】设k 是扎维欧氏空间舻中的一个非空闭凸子集，：k _ 舻是一个 映象， ( 1 ) 称，为k 上的一个单调映象，若有 ( z 一可) t 矿( z ) 一，( ) 】20 ，v x ，配 ( 2 ) 称，为k 上的一个严格单调映象，若有 ( z 一可) t 【，( z ) 一，( 可) 】 0 ，比，y k ，z y ( 3 ) 称，为k 上的一个强( 或一致) 单调映象，若存在常数q 0 有 ( z 一耖) t 【，( z ) 一，( ! ，) 】q l i z 一可0 2 ，v z ，y k 根据定义可知，强单调映象必是严格单调映象，严格单调映象必是单调映象 下面给出变分不等式问题的解的存在性和唯一性的有关结果： 引理1 1 1 1 1 】若映象，在k 上是严格单调的，则变分不等式问题v i ( k , ，) 最多有 一个解 引理1 1 2 【1 】设k 是佗维欧氏空间舻中的一个非空闭凸子集，：k _ 舻是一 个映象，若映象，在k 上强单调的，则变分否等式问题v i ( k ，) 有唯一解 定义1 1 5 【1 】设k 是礼维欧氏空间舻中的一个非空凸子集，向量z 在集k 上欧 氏范数下的投影为 户k ( z ) = a r gm i n x 一! ，l iv y 后) ， g 范数意义下的投影为 p k , g ( x ) = a r gm i n l l x y l l cv y 后 下面我们给出心( ) 的性质( 见文献【6 】) ： ( 1 ) ( z p k ( z ) ，尸k ( z ) 一秒) 0 ，v y k ( 2 ) ( 斥( z ) 一忍( 可) ，z 一可) 0 ，地，y 舻 ( 3 ) i i 段( z ) 一r ( 训 0 ，则矿是v x ( k ，) 的解的充要条件是 矿= 忍陋+ 一m ( x + ) 】 一2 一 硕士学位论文 于是求解v i ( k ，- 厂) 等价于求非线性函数 e ( z ) ：= z 一f k 扛一卢，( z ) 】 的零点，即矿是v i ( k ，) 的解号e ( 矿) = 0 变分不等式与互补问题，不动点问题，最优化问题等有着密切的联系，下面给 出一些特例： ( 1 ) 1 8 j 如果k = 舻，解v i ( k ，) 等价于求解矿舻，使得，( 矿) = 0 若，是 仿射映像，即，( z ) = m x + q ，则v i ( k ，f ) 等价于经典的线性方程组： m x + = g ( 2 ) n 当k 舻是一个凸锥时，则v i ( k ，) 等价于广义互补问题( g c p ) ；当 k = 碎，且，是仿射映像，则v i ( k ，) 等价于线性互补问题( l c p ) ( 3 ) t x l 若k 是舻中的任意闭凸集，r 是k 到自身的连续映射，定义为： ，( z ) = z t ( z ) ，则v i ( k ，) 等价于不动点问题：矿= t ( x ) ( 4 ) 阑若k 为凸集，f ( x ) 是可微函数p p ) ：舻一r 的梯度且，扛) 的j a c c o b i 阵v f ( x ) 为对称矩阵，则v i ( k , ，) 是约束优化问题 j m i n e ( x ) ， 1s t z 艮 的必要条件 鞍点问题与优化问题紧密相关设xc 符，yc 胛是两个闭凸集，l ：席 舻_ r 是可微凸凹函数，即，对给定的y k 工( ，y ) 是凸的，对给定的z x ，l ( x ，) 是凹的鞍点问题定义如下：求矿x ，y + y ，使得 l ( x ，y ) 三( z + ，y ) l ( x ，可) ，v 童x ，v y y( 1 4 ) 记n = l + m ，u = x y ，定义映像g ：舻一舻如下： u = g 撕沪( 兰， m 5 ， 我们可以注意到这样定义的g 是单调的 引理1 1 4 1 1 0 i 鞍点问题( 1 4 ) 等价于变分不等式问题：求t 。u 使得 0 一t + ) t a ( u ) 0 ，y u 阢( 1 6 ) 其中t ，a ( u ) 如( 1 5 ) 所定义 在最优化中，鞍点问题是消除函数约束的有力工具我们考虑如下的优化问题： m i n s o ( x ) lz d ) ，( 1 7 ) 求解类单调变分不等式的交替方向法 其中 d = z xi 五( z ) 0 ，i = 1 ，m ) ， 五：r 。_ r ，i = 0 ，仇是凸可微函数， ( 1 8 ) x = z 硝i 巧0 ，j ) ，j l ，z ) ( 1 9 ) 然后我们定义问题( 1 7 ) 一( 1 9 ) 相应的l a g r a n g e 函数： l ( x ，可) = ，o ( z ) + 弘 ( z ) ( 1 1 0 ) 为了得到问题( 1 7 ) 一( 1 9 ) 与( 1 4 ) ( 1 1 0 ) 的关系，我们需要一定的约束品性成立，也 就是，考虑如下假设： ( c ) 所有的函数 ，i = 1 ，m 是仿射，或者存在一点牙使得五( 牙) f i ，i = 1 ，2 ，礼 当k = 髓，x = 霹时，文献【3 6 】中提出了交替方向法求解，当k = k 2 ，x = 殿 时，文献 3 6 - 3 8 】中提出了交替方向乘子法求解，但在上述两种方法，其中一个子问 题仍是非线性非对称变分不等式问题，在本质上，求解它们与求解原问题一样困难， 于是在文献【3 3 】中，建立了一种新的有效的交替方向法，只需交替地求解一个具有 简单约束的凸二次最优化( 或一个对称线性互补问题) 及一个良态的非线性方程组 即可 类似，当k = 蜀，x = 殿时，韩德人等人在文献阻】中提出了一种新的交替 方向法，这种方法在假设是f 双强制且解集非空的情形下，是收敛的但由于对， 要求比较高，在此基础上，韩德人在文献【3 4 1 提出了一种修正的交替方向法，在假 设，是单调且连续且解集非空时，这种方法只需每步迭代时作一个到简单集上的 正交投影和一些到简单的函数计算对于同时带有等式和不等式约束的变分不等 式问题，z h o n gz h o u ，a n t h o n yc h e n ，韩德人迸一步在文献【4 3 】中提出一种推广的交 替方向法，这种方法只需在文献【3 4 1 的基础上增加一个到简单集上的投影即可，且 在合理的假设下具有全局收敛性更有，对于带一般约束问题，童小娇，何炳生在文 献【4 6 】提出了一类新的交替方向法，其子问题易于求解，且可非精确求解 1 4 本文结果 针对文献，4 6 】提出的交替方向法，本文从以下三个方面考虑了做了改进与 推广： 一6 一 硕士学位论文 1 ) 文献【3 3 】中提出的精确交替方向法要求子i - j 题是精确求解的，在实际计算 时，不可能精确求解子问题，有时候也没必要，因此本文提出了非精确算自适应交 替方向法，允许一个子问题是非精确求解的 2 ) 文献】提出的交替方向法是交替迭代求解一个线性变分不等式和一个 强单调的线性方程组，我们提出的新的交替方向法，是交替迭代求解一个强单调线 性变分不等式和一个强单调的线性方程组，且在合理的假设下，允许两个子问题都 是非精确求解的 3 ) 建立了新的自适应交替方向法数值实验表明，在相同的条件时，迭代的次 数和时间明显依赖于口，p 的值，因此，我们提出了自适应交替方向法，这种方法根 据每步迭代信息自动调整参数q ，口 一7 一 求解一类单调变分不等式的交替方向法 第2 章求解一类非对称单调变分不等式的非 精确自适应交替方向法 2 1引言 本章考虑如下形式的变分不等式： v i ( k ，) ( z z + ) r f ( x ) 0 ，v x k ，( 2 1 ) k = z t v l b x = 6 ，z o ) ，b j p n ，b i f ， 且v f ( x ) 可为非对称的 引入l a n g r a n g e 乘子y ，问题( 2 1 ) 等价如下形式的变分不等式： v i ( f l ，f ) ( 心一t + ) t f ( u ) 0 ，v u q ， ( 2 2 ) 其中 乱= ( i ) ，f c 钍，= ( p ，2 二：r 可) ，q 三彤x y , y = 冗m 群， a = ( ；) ，口= ( 三) ，卢 。是常数 求解y ，( q ，f ) 等价于求e ( u ，p ) ：= u r 阻一f ( u ) 】的零点对于( 2 2 ) 有 e ( 邶) ：= ( 一p 帅f ( x ) 一- - ( 缸a t y - 口) 】) ( 2 3 ) 本章作如下假设： ( 1 ) ，是舻中的连续单调映像 ( 2 ) y j ( q ，f ) 解集甜非空 2 2 非精确自适应交替方向法算法及收敛性分析 基于子问题( 2 1 ) ( 2 2 ) ，我们提出非精确自适应交替方向法，在每步迭代中，根 据每步迭代信息自动地调整参数口 算法2 1 非精确自适应交替方向法算法( i s a a d m ) 给定 0 ，- y ( o ，2 ) ，岛 0 ，z o 舻，非负序列 仉) ( 尼= 0 ，1 ，2 ) 且满足 一8 一 硕士学位论文 + e 仉 十，对k = 0 ，1 ，2 ， k - - - o 步1 ：计算矿，使得 ( y 7 一! ，) t ( a z 七一口) 一a 归k f ( x 知) 一a r 犷】) 0 ，w y( 2 4 ) 步2 ：若l i f ，k f ( x 知) 一a t y 蠹0 0 ，b y ：= i n f ( 风 铲 + 知 其中g = 兀( 1 + 几) i = 0 引理2 2 1 【铂】对任意给定的z 彤，若y 是( 2 4 ) 的解，则有 ，f ( x ) 一a t y l i | i e ( u ，a ) l l 、百j 聊i l f l f ( x ) 一a r y l l ( 2 7 ) 因为求解v i ( a ，f ) 等价于求e ( 让，) 的零点，很多时候均以e ( t | ，卢) 作为误差 界，从上面引理可知，| f 侥，( 矿) 一矿0 也可以作为误差界，从而我们取i i f ，k f ( w 七) 一 a r 矿0 g 作为算法的终止准则 引理2 2 2 设 t 知= ( 一，矿) 是由算法产生的序列，v ，圹) 甜有 ( 矿一矿) + 凤【，( 矿) 一，( 矿) 】) t 【凤，( 矿) 一a t 可1 i i 厥，( 矿) 一a t 矿1 1 2 ( 2 8 ) 证明 由( 2 1 ) ( 2 2 ) ( 2 3 ) ，若( 矿，旷) 是( 2 2 ) 的解，从而是( 2 3 ) 的零点( 其中( 2 2 ) ( 2 3 ) 中的p 取凤) ，于是有 凤，( z + ) = a r y ，( 2 9 ) ( 矿一矿) r ( 触+ 一口) 0 ，( 2 1 0 ) ( y + 一可詹) t ( 触七一n ) 一a 【凤，( 矿) 一a t y 七】) 0 ( 2 1 1 ) 一9 一 求解一类单调变分不等式的交替方向法 由( 2 1 0 ) ，( 2 1 1 ) 推出 ( 彭+ - - y 知) r ( a z 七一肘) 一a f l k f ( x 七) 一a t y 詹】) 0 ， 即 ( z 七一矿) + 慨，( z 知) 一a r y 知】) t ( a t 暑，+ 一a t ! ，七) 0 又由( 2 9 ) 可得 ( z 知一z ) 一l 6 k f ( x 知) 一a t y 七】) t l e d ( x + ) 一p k f ( x 七) 】+ 陋k f ( x k ) 一a t y 七+ 1 】l 0 ， 因为，单调，由上式推出 ( 矿一z + ) + 凤【，( z ) + ，( z ) 】) t 陋k f ( x 七) 一a t y 知】i i & f ( x 詹) 一a t y 知1 1 2 证毕 定理2 2 1 设 u 七= ( 扩，矿) ) 是由算法产生的序列，v ( 矿，旷) 甜，那么3 k o 0 ，使 得v k k o 有 i i ( z 七+ 1 一z 。) + f j k f ( x 七+ 1 ) 一，( z + ) 川2 ( 1 + 亨再碉4 ) f j ( x k - - x * ) + m y ( z 七) 一，( z ) 川2 一三，y ( 2 一，y ) 慨他七) 一a r 矿0 2 ( 2 1 2 ) 证明由( 2 3 ) 式有 巩( 矿+ 1 ) = z 七+ 1 + ，k f ( x 知+ 1 ) 一陋七+ 凤， 七) 】 ft p k f ( x 七) 一矿】 故有 i i ( 铲+ 1 一z ) + 像【，( z 七+ 1 ) 一f ( x + ) i1 1 2 = i i ( 矿一z + ) + 凤【，( z 七) 一f ( x ) 】一 y j d ( x 七) 一a t y 七) 】一o k ( x 七+ 1 ) 1 1 2 = 0 ( 矿一z + ) + j k f ( x 知) 一f ( x + ) i1 1 2 + i l 佃k f ( x 七) 一a t y 七】一o k ( x 七+ 1 ) 1 1 2 2 ，y ( z 七一z + ) + 凤【，( z 七) 一f ( x + ) 】 t j k f ( x 七) 一七】 + 2 ( z 七一z + ) + z k f ( x 知) 一f ( x 。) 】) t 靠( z 知+ 1 ) i i ( 矿一z + ) + 展【，( z 七) 一f ( x + ) i1 1 2 + i i t j k f ( x 七) 一a t y 七】一o k ( x 詹+ 1 ) 1 1 2 + 2 _ 【( z 七一z + ) + 凤【，( z 知) 一f ( x + ) 】) t o k ( x 知+ 1 ) 一2 7 i i 风，( z 七) 一a r 洲2 ( 2 1 3 ) 一1 0 硕士学位论文 因为i i o k ( z 1 ) j | 讯0 风，( 矿) 一a t y 七忆碾 ( 1 + e ) l 凤【，( 矿+ 1 ) 一，( 扩) 】i i ，在下一步迭代中， 我们应提高值风，相反若i i x 知+ 1 一矿0 雨1l i 凤( ，( z 七+ 1 ) 一，( 矿) ) 0 ，则在下一步迭代 中我们应减少凤，记 = 警掣， 然后变参数序列 风) 按下式产生： i ( 1 + n ) 风， 若。知 1 + a i 凤， 其它 例如，我们可取e = 3 ，靠二 i i f i n ( 1 ，面嗣硒1 = 移) ) = 1 ，1 ，i 1 ，石1 ) ，其中d 为 ( 2 2 ) 中乘子的维数 另外，满足 + 的非负序列 亿，可以根据算法自动产生，记魄为序列 段 的改变次数，也就是， c o - o , c k + l - = 萋害蛳g “； 下面给出产生非负序列 ) 的一种策略： 策略1 亿= l ( 吼+ 1 一) 2 0 ， 若儡 0 ，易知按上面的策略产生的非负序列【仇) 满足亿 0 ，问题( 3 1 ) 等价于 u = 昂【钍一u f ( 让) 】 令，u 用( u ) ：= 牡一p n u - u f ( t | ) 】，则问题等价于求e n ，咽( t i ) 的零点，其中u 0 特 别地，问题( 3 1 ) 等价于求下式的零点： 脚，= ( 可一引o f ( 州x ) - 血a t y 叫，) 慨2 ， 由忍( ) 的性质 ( z 一斥( z ) ，忍( z ) 一影) 0 ，v y k( 3 3 ) 在( 3 3 ) 式中取z = 缸一v f ( u ) ，可= t ，k = q ，有 ( e f l ，u 用 ) 2 1 f ( t 正) i | e 【n ，u 卅( t 正) 02 ，v u q ( 3 4 ) 一1 5 求解一类单调变分不等式的交替方向法 引理3 1 1 删f 是强单调映像，u + 是强单调y j 的唯一解，则存在强单调模因子 p 0 ，有 2 v ( e t n ，u 用( u ) ) r f ( 钍) 一i i e e ，叫( 仳) 1 1 2 i i 缸一t 正+ 0 2 讹q ，u p 一1 ( 3 5 ) 3 2新精确交替方向法 基于子问题( 3 1 ) ，我们构造新精确交替方向法，交替迭代求解分别关于z 和y 的子问题 算法3 1 新精确交替方向法算法( n e a d m ) 给定0 ，q 0 ，y ( 0 ，2 ) ，p 0 ，护舒，! o 对k = 0 ，1 ，2 ， 步1 ：计算知+ l ，使得 ( 可7 一矿+ 1 ) t ( m 一n ) 一a ( 9 ( z 南) 一a t y 知+ 1 ) 4 - 口b + 1 一y k 】) 0 ，y ( 3 6 ) 步2 ：若i i 卢，( 扩) 一a t y k + l i l + i 旷+ 1 一矿l i 0 ，使得对所有v k 0 ，有 z l l e ( u k + 1 ) l i i i ，( z 詹) 一可七+ 1 l i4 - l l 耖七十1 一可知| | 证明因为 脚) = ( 可一帅p f ( x ) 一- 池a t y 叫】) 硕士学位论文 故 即m ) = 。笺f ( x 旷k + 1 ) ，- - 一a ( t y k 机+ l - n ) 】) ， 由( 3 6 ) 式可得 矿+ 1 = p y 由七+ 1 一( ( a x 七一o ) 一a ( p ，( z 七) 一a t y 知+ 1 ) + q ( 剪南+ 1 一y k ) ) 】， 令 g k ( y 七+ 1 ) = ( a x 一a ) 一a ( p ，( z 七) 一a t y 知+ 1 ) + 口( y 七+ 1 一y k ) 由，p k ( ) 的非扩张性得 由 i i e ( u 七+ 1 ) l | 0阿( z 1 ) 一a t y 1| l i | p y 【可七+ 1 一g k ( y 七+ 1 ) 】一p y b 七+ 1 一( 缸七+ 1 一o ) 】| l l l 肌1 ) 一a t y 1 ll i la ( z 七+ 1 一矿) + a 归，( z 七) 一a t y 七+ 1 】一q ( 可膏+ 1 一y 七) 0 0 ，y ( 0 ，2 ) ，a 0 ，卢 0 ，z o i t ，, i o v 选取魄使其满足 u k + o 。置k ：= 0 步1 ：确定y k + l 使其满足 i i 矿+ 1 一雪1 i i 一2 l 一 求解一类单调变分不等式的交替方向法 步2 ：若i i z i ( z 七) 一a t y k + l i i + 1 1 可知+ 1 一圹i | 0 ，由引理3 1 1 ，有 其中 2 v ( e t r 螂。】) ( ! ，七+ 1 ) ) t g k ( y 七+ 1 ) 一l i e k 吼川2 i 矿+ 1 一雪知+ 1 1 1 2 , u p 七一1 e 【k 蛳】( 可) = y p y b