（计算数学专业论文）广义牛顿型算法求解两类离散非光滑问题.pdf

博士学位论文 摘要 障碍问题和h a m i l t o n - j a u c o b i - b e l l i i l a n 方程( 简称h j b 方程) 问题产生于机械、工 程技术、物理、金融、最优控制等领域它们的数值解，尤其是大规模问题数值解 的研究是工程界和计算数学界一个非常热门课题近几十年来，取得了许多成果 既然障碍问题和h j b 方程是两类典型的非光滑问题，在本文中，我们将研究求解这 两类问题的广义牛顿型算法 在第2 章，我们提出了广义牛顿s c l l 瓢w z 迭代法来求解离散的单边障碍问题该 算法的优点如下：( 1 ) 算法在每个牛顿迭代步，只采用有限步加性或乘性s c h 嗡r z 迭 代来求解一个低维线性方程组的近似解而不需要求解该线性方程组的精确解，从 而可以大大减少计算工作量；( 2 ) 算法具有单调收敛性且在适当条件下超线性收敛 到问题的解此外，与其它具有单调收敛的s 概z 算法相比较，该算法的初始迭 代很容易选取 在第3 章，我们提出了求解离散h j b 方程的广义牛顿法并证明了算法的单调 收敛及局部超线性收敛性该算法的优点是每个牛顿步只求解一个线性方程组 从而便于采用线性方程组的快速求解器进行求解特别地，我们验证了l i o 璐以 及m e r c i e r 于1 9 8 0 年提出的迭代格式i i 是一类特殊的广义牛顿法，所以该迭代格式 具有局部超线性收敛性进一步，我们研究了求解离散h j b 方程的广义牛顿迭代 法该算法在每个牛顿步均采用迭代法来求解线性子问题的一个近似解从而大大 地减小了计算工作量在适当的条件下我们证明了算法具有局部超线性收敛性 数值实验表明了算法是非常有效的 在第4 章，我们研究了求解离散的双边障碍问题的阻尼广义牛顿法与离散的 单边障碍问题的情形相比，离散的双边障碍问题的求解难度更大当采用古典的有 效集策略或增广拉格朗日策略进行求解，常常得不到算法的单调收敛性本章中， 通过选取适当的初始迭代以及在每个迭代步选取一个适当的阻尼因子，我们证明 了阻尼广义牛顿法是单调收敛的且具有有限步终止性而且当问题退化为单边障 碍问题时，阻尼广义牛顿法等价于古典的有效集策略算法( 或增广拉格朗日策略算 法) 在第5 章，我们提出了求解离散的双边障碍问题的阻尼广义牛顿迭代法注意 到在前一章中得到的阻尼广义牛顿法在每个牛顿步均需要求解一个低维的线性方 程组当离散问题的规模很大时，精确求解子问题需要很大计算工作量为了减少 计算工作量，本章中我们将在每个牛顿步均采用迭代法来求解线性子问题的一个 近似解在适当条件下，我们证明了算法是超线性收敛的数值结果表明算法是十 分有效的 此博士论文得到了国家自然科学基金( 1 0 6 7 1 0 6 0 ，1 0 9 7 1 0 5 8 ) 的资助 广义牛顿型算法求解两类离散非光滑问题 此博士论文用珏x 2 。软件打印 关键词：障碍问题；h j b 方程；广义牛顿法；单调收敛 博_ 上学位论文 a b s t r a c t t h e0 b s t a u c l ep r o b l e m 衄dt h eh 锄i l t o n - j a c o b i - b e u m a d le q u a t i o n ( d e n o t e db y h j be q u a t i o n ) a r i s e 行o mm 龇l y 丑e l d s ，s u c h 羽m e c h a n i s m ，e n 舀n e e r i n g ，p h y s i c s ， 缸a n c e ，o p t i m a lc o n t r o lt h e o ua n ds oo n t h e i r 肌m e r i c a ls o l u t i o n s ，e s p e c i a i l y t h o s ef b rt h ei a r g es c a l ep r o b l e l s ，h a v ea t t r a c t e d m c ha t t e n t i o ni ne n g i n e e r i n ga j l d c o m p u t a t i o n 越m a t h e m a t i c s i nt h ep a s td e c a d e s ，m 舭l yf u i t sh a v eb e e nt a k e n t h b n gi n t oa c c o u n tt h en o n s m 0 0 t h n e s s0 ft h e s et w ok i n d so fp r o b l e m s ，i nt h i s t h e s i s ，陀s h 甜ld i 8 c u s st h eg e n e r a l i z e dn e w t o nt y p em e t h o d sf o rs o l v i n gt h e s et w o l 【i n d so fp r o b l e i i l 8 i nc h a p 钯r2 ，w ep r o p o s ea 群m e r a l i z e dn e w t o ns c h w a r zi t e r a t i v em e 此【0 d f o rt h em s c r e t eu i l i l a t e r 越o b s t a u c l ep r o b l e m t h ep r o p o s e di n e t h o de n j o y 88 0 m e n i c ep r o p e r t i e 8 f i r s t ，u n l i k em o s t8 m o o t h i n gn 印l r t o n - l i k e l e t h o d sw h e r ea te a c h i t e r a t i o na ne x a u c tn e 毗0 ns t e ph a 、，et ob eo b t 出n e d ，i no u rm e t h o dw e0 n l yn e e d t os o l v ea n 印p r o x i m a t es 0 1 u t i o no fal o w e r - d i m e n s i o n 越l i n e 盯s y s t e mb yf i n i t e l y m a 朐ya d d i t i v eo r m l t i p l i c a t i v esc ：h w zi t e r a t i o 瑚c o n s e q u e n t l y i ti sd e s i r et o s a ec o m p u t a t i o nc o s t ；s e c o n d ，t h ea l g o r i t h mp 0 8 8 e s 8 e sam o n o t o n ec o m r e r g e n c e p r o p e r t ya n ds u p e r l i n e a rc o n v e r g e n c ep r o p e r t 矿m o r e c i v e r ，t h ei n i t i a li t e r a t eo ft h e m e t h o di se a u s yt oc h o o s ec o m p 盯e d 丽t ht h a to fo t h e rm o n o t o n o u s l yc o n v e r g e n t s c b ，a r zm e t h o d s i nc h a p t e r3 ，r ep r o p o s ea g e n e r a l i z e dn e w 乞d nm e t h o df b rt h ed i s c r e t eh j b e q u a t i o na n dp r o v et h a tt h ei t e r a 七es e q u e n c ep r o d u c e d b yt h em e t h o di sm o n o t o n _ i c a l l yl o c a l l ys u p e r l i n e a r l yc o n v e r g e n t t h ea d v a n t a g eo ft h ea l g o r i t h mi 8t h a ti t o n l yn e e d s 七os o l v eas y s t e mo fl i n e a re q u a t i o n sa te a c hi t e r a t i o n i np a r t i c u l 盯， r es h o wt h a tt h ep r o p o s e dm e t h o dc o n t a i n st h ei t e r a t i v es e q u e n c ei ip r o p o s e db y l i o l l sa n dm e r c i e ri n 19 8 0a sas p e c i a lc a l 8 e h e n c e ，t h ei t e r a t i v es e q u e n c ei ia l s o p o s s e s s e sal o c a l l ys u p e r l i n e a rc o n v e g e n c ep r o p e r t y f i u r t h e r m o r e ，w ed e v e l o pa g e n e r a l i z e dn e 毗o ni t e r a t i v em e t h o df o rt h ed i s c r e t eh j be q u a t i o n a s r eo n l y n e e dt og e ta i la p p r o 妇m a t es o l u t i o no ft h es u b p r o b l e m ，t h ec o m p u t a t i o nc o s to f t h ep r o p o s e dm e t h o d 、釉u l db ev e 可c h e a p u n d e rp r o p e rc o n d i t i o i l s ，w ep r o v e t h a tt h es e q u e n c eo ft h ei t e r a t e so o i l 、r e r g e ss u p e r l i n e a r l y n u m e r i c a lr e s u l t ss h o w t h a tt h em e t h o di se 伍c i e n t i nc h a p t e r4 ，w ep r o p o s ead a m p e dg e n e r a h z e dn e w t o nm e t h o df o rt h ed i s ， c r e t eb i l a 土e r a lo b s t a c l ep r o b l e m c o m p a r e dw i t ht h ed i s c r e t eu n i l a t e r a lo b s t a c l e p r o b l e m ，i ti sm o r ed i 伍c u l tt os o l v et h ed i s c r e t eb i l a t e r a lo b s t a c l ep r o b l e m w h i l e i v 广义牛顿型算法求解两类离散非光滑问题 t h ep m b l e m 鲥v e d b yt h ep r i m a la c t i v es e tm e t h o d ( o rt h ea u g m e n t e dl a g r a n 舀衄 a c t i v es e tm e t h o d ) ，t h ei t e r a t i v es e q u e n c ei 8n o tm o n o t o n o u 8 l yc o n v e r g e n t 1 1 1t 1 1 i s c h a p t e r ，w ev e r 海t h a tt h ea k o r i t h mi sm o n o t o n o 璐l yc o n v e r g e n t m o r 骶r ，i t 七e r m i n a t e sa tt h e8 0 l u t i o n 谢t h i n 矗n i t e l ym a n yi t e r a t i o n si ft h ei n i t i 甜p o i n ta n dt h e d 锄p i n gf 犯t o ra u r ec h o s e n 印p r o p r i a t e l y i np 盯t i c u l a r ，嬲t h ep r o b l e mi 8r e d u c e d t 0ad i s c r e t em l i l a t e r a lo b 8 t a c l ep r o b l e m ，t h e i a m p e dg e n e r a | i z e dn 钾n o nm e t h o d i 8e q 哪v 出e n tt ot h ep r i m 砒a u e t i v e8 e tm e t h o d ( o rt h ea u g m e n t e dl a g r 锄舀a na c t i v e 8 e tm e t h o d ) i nc h a p t e r5 ，w ep r o p o s ead a m p e dg e n e r a l i z e dn e w t o i 卜i t e r a 七i v em e t h o d f o rt h ed i s c r e t eb i l a t e r a lo b s t a c l ep r o b l e m n o t et h a ta1 0 w e r - d i m e n s i o n a l1 i n e a u r 8 y s t e mn e e d st ob e8 d l v e da te a u c hn e 毗o n8 t e pf o rt h ea l g o r i t h mf t 啷t h ep r e v i o u s c h a p t e r w h e nt h es c a l e0 ft h ed i s c r e t ep r o b l e mi sl 盯g e ，i tt a 王【e 8ag r e a td e a io f c o m p u t a t i o n a lw o r kt os 0 1 v et h es u b p r o b l e me x a c t l y - i no r d e rt os a v et h ec p u t i m e ，i nt h i j sc h a p t e rw e 印p r 戚m a t et h es 0 1 u t i o no ft h es u b p r o b l e mt h r o u g ha n i t e r a t i v em e t h o da te a c hn e 毗o ns t e p u n d e ra p p r o p r i a t ec o n d i t i o n s ，陀p r a v e t h a tt h em e t h o dc o n v e r g e ss u p e r l i n e a r l y n u m e r i c a lr e s u l t ss h o wt h a tt h e1 1 1 e t h o d i se m c i e n t t h i sd i s s e r t a t i o ni ss u p p o r t e db yt h en a t i o n 越n a t u r a ls c i e n c ef b u n d a t i o no f c h i n a ( 1 0 6 7 1 0 6 0 ，1 0 9 7 1 0 5 8 ) 。 t h i sd i s s e r t a t i o ni st y p e s e tb ys o r w a r el a 死x 2 k e yw o r d s ：o b s t a c l ep r o b l e m ；h j be q u a t i o n ；g e n e r a l i z e dn e w t o n m e t h o d ；m o n o t o n ec o i n r e r g e n c e v 博士学位论文 1 1概述 第1 章绪论 自2 0 世纪9 0 年代以来，广义牛顿法求解非光滑方程得到了蓬勃发展，详见文 献f 1 _ 6 1 因其深邃丰富的理论性和实际计算中的有效性，受到了最优化工作者和 计算数学家的特别青睐，被广泛运用于求解p d e 约束的最优控制问题，变分不等式 问题，图象处理问题等等，详见文献 7 - 17 】及其参考文献本文主要研究求解离散 障碍问题以及离散h j b 方程的广义牛顿法及广义牛顿迭代法这两类算法可以看 成求解光滑问题的牛顿法及牛顿迭代法 1 p 2 1 】在求解障碍问题与h j b 方程上的推 广 1 1 1障碍问题 障碍问题在工程、力学、电磁学、水文学、经济学等众多的领域中有广泛的应 用一直以来都受到物理学家、数学家、计算机科学家等许多领域的专家的关注， 因而在理论分析、求解方法等方面取得了丰硕的成果已有许多专门的著作对其 进行了详细地阐述，详见文献f 2 2 3 1 1 离散障碍问题的数值求解方法包括直接法和迭代法直接法非常适合求解中 小型问题，详见文献f 3 2 3 5 1 然而对于大规模问题，由于舍入误差、数据存储等因 素的影响，直接法的稳定性较差因而偏重于迭代法求解投影松弛迭代法是求解 离散障碍问题最有效的方法之一，参见 2 4 ，3 6 】该算法的结构十分简便，很容易 在计算机上实现且算法是收敛的但是，它的收敛率却依赖于松弛因子的选取且 随着网格剖分的加密收敛效果会变得越来越差区域分解算法是上世纪七、八十 年代发展起来的新型迭代算法，这类算法的迅猛发展得益于其在求解离散偏微分 方程时所具有的非常好的网格无关收敛性质，参见文献 3 m 1 1 由于区域分解算 法将大型问题转化为小规模问题，复杂问题转化为简单问题，且具有非常好的并行 结构，因此其已被广泛地用于求解离散障碍问题，是求解离散障碍问题的十分有效 的迭代方法，详见文献4 2 5 4 1 在一定条件下，该方法具有非常好的收敛性多 重网格法的基本思想早在上世纪六十年代就由前苏联计算数学专家f e d o r e n k o 提 出，但当时并没有引起人们的注意七十年代中期以色列数学家b r a n d t 和德国数 学家h a c k b u s c h 以及后来美国数学家b r a m b l e 等对这一算法进行全面的创造性的研 究，提出了一些新的观点，使人们重新认识多重网格算法，这一方法受到了普遍的 重视，参见文献4 1 ，5 5 - 5 8 随后b r a n d t 和c r y e r 、m a n d e l 、h o p p e 、v a n g 和z e n g 于 八十年代，k o r n h u b e r 于九十年代分别对障碍问题讨论了相应的多重网格算法，详 见文献f 4 6 ，5 9 - 7 0 1 虽然在数值上，多重网格算法仍然是名符其实的“快速求解器”， 一1 一 广义牛顿型算法求解两类离散非光滑问题 但在理论研究上则远不及人意主要困难在于障碍问题本身具有的很强的非线性 然而不管是投影松弛迭代法、区域分解算法还是多重网格算法，在每步迭代都要 求解一个非线性子问题有效集算法( 或拉格朗日乘子法) 是求解离散障碍问题的又 一种有效的迭代方法，参加文献f 2 ，2 4 ，6 3 ，7 1 7 3 】其基本迭代由两步构成：首先基 于某种策略，把网格区域分解成有效集和无效集两个部分；然后关于无效集部分求 解一个低维的线性方程组近来随着广义牛顿法的迅速发展，有效集算法( 或拉格 朗日乘子法) 被解释为一类特殊的广义牛顿法，详见文献 2 ，6 1 人们对这一算法就 有了一个新的认识与前面三种迭代算法相比，有效集算法( 或拉格朗日乘子法) 在 每个迭代步不需要求解非线性的子问题从而可直接调用线性方程组的“快速求解 器”( 如：代数多网格求解器，并行算法求解器) 来求解离散障碍问题然而该算法存 在着一个弊端：现存的收敛性定理要求每一步迭代都必须是精确求解线性子问题， 参见文献【2 ，7 2 ，7 4 】 1 1 2h j b 方程 h j b 方程最早出现于利用动态规划方法求解最优控制问题，之后在科学、工 程、经济管理等领域有广泛的应用，参见文献 7 粥3 及其参考文献因此其离散 问题数值解的研究是一个非常热门的话题 l i o l l s 和m e r e i e r 于八十年代初在文献f 8 4 1 中首次提出了求解离散h j b 方程的 两个最经典的迭代格式( 简称l i o 瑚m e r c i e r 格式) 在这两个迭代格式中，每一步迭 代我们只需要求解一个线性互补问题或求解一个线性方程组而后，伴随着多重 网格技术在求解线性方程组与变分不等式中的发展与完善，h o p p e 在文献【8 5 1 中 研究了求解离散h j b 方程的多重网格算法该算法的基本思想是：在每一步迭代 中，利用多重网格算法来求解线性方程组或线性互补问题的解考虑到区域分解算 法在求解p d e 问题时所表现出来的有效性及此算法容易高度并行，c 锄i 1 1 i 等在文 献f 8 6 1 中首先提出了求解h j b 方程的区域分解算法随后，s u n 在l i o n s m e r c i e r 格 式的基础上也构造了一类区域分解算法，见文献f 8 7 1 最近，z h o u 在文献f 8 8 1 中提 出了另一类基于等价于离散h j b 方程的拟变分不等式的区域分解法，文中证明了 在适当的条件下离散h j b 方程解的存在唯一性，进一步研究了迭代序列的单调收 敛性考虑到前面所有的算法在每一步迭代中都必须去求解一个线性方程组或者 线性互补问题，近来z h o u 又在文献 8 9 和文献f 9 0 1 中分别提出了求解离散h j b 方 程的j a c o b i 型迭代法和g a u 瓣s e i d e l 型松弛迭代法与前面的算法相比，这两类迭 代算法在每步迭代中只执行简单的算术运算，计算简便，且在一定条件下是单调收 敛的算法的不足之处在于其收敛率依赖于松弛因子的选取及网格剖分的大小 一2 一 博士学位论文 1 2创新点及主要内容 本文我们讨论了求解离散障碍问题及离散h j b 方程的广义牛顿型算法其创 新点如下： 1 针对离散的单边障碍问题，我们提出了广义牛顿s c h w 面z 迭代算法该算法 既保留了广义牛顿法的单调收敛及局部超线性收敛性，又由于对子问题采取非精 确求解可以大大减少计算工作量，是“名符其实 非精确算法此外，算法很容易实 现并行计算，适合大规模问题求解对于双边障碍问题，首次得到了具有单调收敛 性的广义牛顿型算法 2 针对离散h j b 方程，我们提出了广义牛顿法和广义牛顿迭代法首次验证 了l i o l 峥m e r c i e r 格式i i 具有有限步终止性广义牛顿迭代法克服了l i o i l s m e r c i e r 格 式i i 中每步迭代均要求精确求解一个线性方程组这一难题在适当的条件下证明了 这两类算法具有单调收敛且局部超线性收敛性 整篇论文的安排如下：第二章我们提出了求解离散单边障碍问题的广义牛 顿s c h w 趾z 迭代法并分析了其收敛性；第三章讨论了求解离散h j b 方程的广义牛顿 及牛顿迭代法，证明了其收敛性，并给出了数值结果；第四章和第五章我们分别研 究了求解离散双边障碍问题的阻尼广义牛顿法和阻尼广义牛顿迭代法，在适当的 条件下证明了其单调收敛及局部超线性收敛性，数值结果表明了算法的有效性 1 3 记号及基本概念、性质 在这一节里，我们给出在整篇文章中所要用到的记号和基本概念、性质 1 3 1 记号 形 础n a = ( n 巧) 形黼 a 一1 a l j 川 z 帮 z j i i i i p ( - ) n 维欧氏空间 n 佗阶矩阵集 元素为a “的邢介矩阵 矩阵a 的逆矩阵 a 的子矩阵，其元素为( i ，歹j ) 川= ( o 巧i ) 佗维欧氏空间中向量z 向量z 的第i 个分量 分量为z i g j ) 的子向量 欧氏范数及相应的矩阵范数 矩阵的谱半径 一3 一 广义牛顿型算法求解两类离散非光滑问题 还有一些特殊的记号将在文中用到时再具体说明 1 3 2 基本概念、性质 在这一小节，我们将给出一些基本概念及基本性质首先，我们引入可微 性( s l a n td i 舵r e n t i a b i l i t y ) 的概念这一概念最初由c h e n 等人针对b a n a c h 空间上的 算子映射引入，详见文献 1 】随后得到了广泛的应用本文主要利用这一概念来 讨论有限维情形的问题假定u 舻是开集 定义1 3 1 函数日：u _ 研在z u 处是s ( s l a n t l y ) 可微的，如果存在一个映 射g ：u 一形n 使得矩阵族 g ( z + ) ) 关于足够小的危在矩阵范数下是一致有界 的且 溉避盟寺渺姐 映射g 称为日在z 处的s d f 彻，抚佗函数 定理1 3 1 设z + 是非光滑方程日( z ) = o 的解且函数日在z 处是g 可微的假定映 射g 是函数日在矿处的。曼函数且存在正常数三，使得在z 4 的领域u 内满足i i g ( z ) - 1 i | l 那么当l l z o 一矿i l 足够小时，迭代 z 。| c + 1 = z 七一a ( z 七) 一1 日( z 七) ，= o ，1 ， 超线性收敛到z ，其中a ( z ) 形加且满足 l i a ( z + + ) 一g ( z + 九) i i _ o 当 l i 九| | _ o 定义1 3 2 设4 舻煳。如果 n 乱 u ， z v o 玎0 ，歹i ，t ，j ， 则称4 为己一矩阵又若a 可逆且爿一1 o ，则称a 为m 一矩阵 下面两个引理分别来自文献【9 l 】和【9 2 】 引理1 3 1 假设a r n n 且满足j d ( a ) o 则矩阵j e i 也 为m 矩阵且 i i b 。i i 哦) 由于z + 西，则对任意z 厶成立z ；兢又因为日( z ) o ，所以对指标集如可得 乃：( z ) o 乃：( z + ) 一7 一 广义牛顿型算法求解两类离散非光滑问题 也就是说， 从而 a 如j 2 z j 2 + a 如j l 。j l 一九a b 屯z 乞+ a 如 z ；l 一厶 a 如，2 ( z + 一z ) 如一a j 2 ( z + 一z ) ( 2 1 8 ) 既然a 是肛矩阵，则由引理j 只彳知a 如屯也是肛矩阵且a 屯 0 考虑到对t 厶成 立z ；玩，由偿j 圳式可得 ( z 一z ) 如0 从而z + z 注2 1 1 引理2 j 2 意味着非光滑方程组俾f 矽至多存在一个解 命题2 1 1 设z d ，d o 且满足g ( z ) d 一日( z ) 那么z + d d 口 证明：既然z d 且d o ，那么有z + d2z 圣下面只需证明日( z + d ) o 关 于向量z ，定义下列两个不相交指标集： 厶：= 0l 戤一西t 口 t = 1 n 与啦= 钆的情况为简单起见，将k 与留t 等同起来令r ：舻+ 彤t 是一个 限制算子在本章中，危是一个秩为佻的啦礼矩阵它的转置嬲：舻t _ 研则是 延拓算子而且，砰的列就是佗他单位矩阵中的列形式上，这样的矩阵足可以 表示成 冠= 五d 死， ( 2 2 2 ) 其中厶是啦单位矩阵且死是某个礼礼的置换矩阵矩阵a 可分解为下列形式： 肚一旧主。卜 2 其中a 是a 的啦m 阶主子阵，a t 是与a 互补的矩阵a 的主子阵，且鼠，g 均是非 正矩阵显然a 与a 一 也是m 一矩阵 对t = 1 ，2 ，p ，构造矩阵岛形，t 如下： “ 最= 磁尼( 2 2 4 ) 由忌的定义知，矩阵忍是一个对角矩阵且与砰的非零行对应的对角元上的元素 是1 当a 来自于区域q = 岖1 q t 上微分算子的离散时，子区域q 通常可以由g p 种不同颜色着色使得如果q tnq f 仍那么q t 和q f 就着上不同的颜色相似地，我 们可以对子空间进行着色使得k 与着上不同的颜色只要kn o 对于块 重叠情形，矩阵易对角元的元素大于或等于1 ，从而矩阵是非奇异的而且，只 有在重叠的行，矩阵对角元素才大于1 但是，对角元素不会大于g 也就是说，我们 有 p ， ：旦茎口，( 2 2 5 ) l = 1 设a = 尼a 醪是4 关于子空间k 的限制那么a 是矩阵4 的某个m 阶主子 阵的对称置换且是非奇异的定义 只= 霹4 f 1 尼a = 碍( r a 霹) 一1 尼a 设z ( o ) 是线性方程组( 2 2 1 ) 的初始近似解由文献 9 4 】可知，阻尼加性s c h w a r z 迭代 可表示如下： z ( 外1 ) = 乃z ( 8 ) + c ，s = 0 ，l ，( 2 2 6 ) 其中秒 0 是阻尼因子， pp 乃= ，一日只= ，一目霹a f l r a ， ( 2 2 7 ) 一9 一 广义牛顿犁算法求解两类离散非光滑问题 且 c = ( ，一乃) a 一1 6 由文献【9 5 】知，求解线性方程组( 2 2 1 ) 的乘性s c h 瞰z 迭代可表示为 其中 且 z ( 卧1 ) = t z ( 。+ c ，s = 0 ，1 ，( 2 2 8 ) 1 t = ( j 一昂) ( j 一昂一1 ) ( ，一只) = ( ，一只) ， ( 2 2 9 ) i = 尹 c = ( ，一t ) a 一1 6 迭代序列( 2 2 8 ) 相当于依次在子空间，k 上进行逐次子空间校正 下列两个引理分别来自文献【9 6 】和 95 】 引理2 2 1 设a 是肛矩阵若口 i e q i o z jz 一 对于伊，我们不难验证存在非奇异的对角矩阵d 岛使得g 七= d 庇界，其中帮a 且 其非对角元素是非正的也就是说，尔也是肛矩阵类似于俾2 别，我们有 且 从而 肚一偿差卜 g ! = 磷愁1k ：= d ：谈 ( 磷) _ 1 磷= ( 霉) - 1 墩 一1 3 一 钟耻 他 广_一1j 1j 叫1叫磷-甩i 厶 g 知1 七1 七i 知1 g g g g 碍 霹 霹 碍 霹 p管甲警等：i 广义牛顿剞算法求解两类离散非光滑问题 考虑到a 七a 且均为肛矩阵，所以我们有 o ( g ；) 一1 砖= ( a ? ) 一1 成a f l 鼠 ( 2 3 1 2 ) 秘鼠( 2 3 9 ) 一( 2 3 ，1 2 ) 就祷 o 磅乃， 这意味着对任意正整数e ，成立 i | ( 删= z 墨。帮器鼎= ( 硼 从而结论成立口 对任意正整数克和2 ，利用引理2 2 1 可得j d ( ( 黠) 2 ) = p ( 璐) 。 1 从而矩阵，一 ( 露) 2 非奇异且由引理1 3 1 成立 下列定理建立了算法2 3 1 的单调收敛性 定理2 3 1 设z + 是非光滑方程组偿_ f 剀的解假定 扩 是算法2 7 _ f 产生的迭代序 列那么序列 ? 南) 收敛到z + 而且 z 知z 七+ 1 z + ，七= o ，l ， ( 2 3 1 3 ) 证明：由算法2 了f ，得到z 血+ 1 = 扩+ 扩，砒从而结合引理2 2 _ f ，2 3 j 以及2 3 研 得 z z 七十1 z + ， 尼= o ，1 ， 既然迭代序列 矿 是单调有界的，那么存在某个z ”使得l i mz 南= z ” e o o 利用算法2 了j ，对任意意我们有 扩，m e = 磅驴，m * 一1 + 扩 = 露( 露扩胁_ 2 + c 知) + = ( 磅) 2 扩，m t 一2 + 磅扩+ = ( 罐) m 驴o + ( 磅) m k _ 1 + ( 露) m k - 2 + + j = ( 磅) md ( 七，o ) 一 ，+ 磅+ + ( 磅) m t 一1 ( ，一磅) ( g 凫) 一1 日( 矿) = ( 磅) m d 岛 o 一 ，一( 磅) m ( g 七) 一1 日( z 七) 一1 4 一 p磅 p 铷 n h = o 玢露 一 p 博士学位论文 既然z 七+ 1 = 矿+ d 七，m ，那么成立 z 七十1 = z 七十( 露) m 扩o 一 ，一( 露) m 】( g 七) 一1 日( z 七) ( 2 3 1 4 ) 从而得到 0 一日( ) = g 知【j 一( 磅) m - 】一1 ( z 七+ 1 一z 七) + g 詹驴，o g 七 ，一( 磅) m 一1 扩，o i g 七i ( j r 一乃) 一1p 七+ 1 一z 七+ d 七，o + i g 七l d 七，o ( 2 3 1 5 ) 2 i g 岛i ( j 一乃) _ 1 驴，m - + i g 南l 扩，m - = i g 七i 2 ( j 一乃) 一1 + 明驴，m 一， 其中第一个不等式是由于扩d ，第二个不等式由引理f 3 j 和2 3 3 决定，第三个 不等式来自于偿只矽既然 矿 收敛到z 料，则有。h 罂沙，m t = o 考虑到 i g 七i 】- 和( j 一 乃) 一1 均是一致有界的从而由俾舅f 剀可得。1 i m 日( z ( 七) ) = o 又由函数日的连续 性，则有日( z ”) = 0 利用非光滑方程组似f 缈解的唯一性，就得到z “= 矿 口 进一步，我们得到下列局部收敛性结论 定理2 3 2 设z + 是非光滑方程组偿f 剀的解且 m 南) 器。是正整数序列如果成立 仇七+ o 。 当 七- + o 。，( 2 3 1 6 ) 那么算法2 舅_ f 生成的迭代序列 ) 超线性收敛到z + 证明：既然磅o 且驴，o o ，那么由俾彳7 ) 及俾了f 4 j 可得 o z 1 一z + = z 七+ ( 露) 价t d 詹，o 一 j 一( 磅) m - 】( g 南) 一1 日( z 知) 一z + z 七一z + 一( ，一( 磅) m t ) ( g 南) 一1 日( z 惫) ， 从而结合引理2 7 贿 l i z 凫+ 1 一z + | i i i z 七一z + 一( ，一( 露) m t ) ( g 后) 一1 日( z 七) | i i i 矿一z + 一( g 南) - 1 日( z 七) | i + i i ( 露) m * ( g 南) - 1 日( z 岛) i i 嘣嵫删k 审，彳一萨) _ 勺l i ( 2 3 1 7 ) + | i ( 黠) m t | | l l ( z 詹一z + ) | l 、7 i i ( g 七) 一1 i | ( 1 + l i ( 乃) 仇m | | ) | f 日( z 南) 一日( z + ) 一g 知( z 知一z 4 ) f i + ( 乃) m 。l l l l ( z 知一z + ) | 1 由俾j 彳) 和引理_ f 了彳知存在某个正常数c 使得对任意后，成立i | ( g 惫) 一1 i i c 注意 到j d ( 乃) 7 1 那么由引理f 7 珂得存在一个正常数p o 使得对任意p 加，成立 i i ( 乃) p i l 居半兰饥 d k u 又由偿彳纠可知对任意z 成立 g 七( ，一辟) = g 忍( ，一碍( g ? ) _ 1 r g 七) = ( ，一g 知霹( g ：) 一1 r ) 萨 类似于偿彳砂，可以证明，一g 忌r ，( g ；) 一1 尼o 既然g 扩，+ h ( ) o ，从而 g 七d 南，j + l =g 2 f 丁2 d 詹，+ c 七) = g 2 ( 丁七矿 7 一( ，一t 南) ( g 惫) 一1 日( z 凫) ) = 一日( z ( 彪) ) + g 丁南( d 七，o + ( g 凫) 一1h ( z 七) ) = 一日( z 局) + g 七t 七( v k ) 一1 ( g “d 血，。+ 日( z 忌) ) = 一日( z 南) + g 七( ，一芹) ( g 惫) 一1 ( g 南扩+ 日( z 膏) ) 0 = p 1 = 一日( z 七) + ( 一g 后r 歹( g ? ) 一1 忍) ( g 知驴，+ 日( 扩) ) i = p 一日( z 七) 由归纳法原理知俾彳成立 口 一1 7 广义牛顿犁算法求解两类离散非光滑问题 利用命题2 1 1 及引理2 4 1 ，我们得到下列引理 引理2 4 2 假定妒d 且迭代z 七十1 由算法2 彳j 的步2 及步3 得到那么z 1 d 而 且z 知 z 七+ 1 类似于引理2 3 3 ，我们有下列结论成立 引理2 4 3 设丁和p 分别由偿幺砂以及俾名砂定义那么o t 詹t 且对任意正 整数已成立i l ( t 七) 2 i | i i r i | 对任意正整数后和它，利用引理2 2 2 可得p ( ( t 七) 2 ) = p ( p ) 2 1 从而矩阵，一 ( p ) 。非奇异且由引理1 3 1 成立 下列定理建立了算法2 4 1 的单调收敛性 定理2 4 1 设z + 是非光滑方程组偿f 矽的解假定 扩) 是算法2 彳j 生成的迭代序 列那么序列 矿) 收敛到z + 而且 z 七z 知+ 1 z + ，后= 0 ，1 ， ( 2 4 7 ) 证明：由算法2 彳j 知z 七+ 1 = 扩+ 驴，m 结合引理2 j 研口2 彳珂得 z 七z 七+ 1 z + ，七= o ，1 ， 从而存在向量z + 使得l i mz j c = z 惫 o o 由算法2 彳_ f 可知对任意忌成立 扩，m k = 丁七d 印，m 一1 + c 詹 = 丁七( t 惫d 七，m k 一2 + ) + c 七 = ( 丁岛) 2 驴，m k 一2 + 丁惫c 七+ 少 ： = ( t k ) m 。d 七o + 【( t 七) m t 一1 + ( t 七) m k 一2 + + 明c 七 = ( 丁七) m d 七，o 一【，+ p + + ( t 凫) m t 一1 ( ，一t 七) ( g 七) 一1 日( z 七) = ( t 七) m d 七，o 一 ，一( t 七) m - 】( g 七) 一1 日( z 知) 既然z 七+ 1 = z 七+ d 惫，m k ，贝 z 七+ 1 = z 七+ ( 严) m 一扩，o 一【，一( t 南) m t 】( g 七) 一1 日( z 奄) 一1 8 一 醒 n ， t p 铷 耋量 i i 八， 勺 丁 一 ， 博士学位论文 从而