（应用数学专业论文）求解凸约束单调的非线性方程组的丙种算法.pdf

t w om e t h o d sf o rs o l v i n gm o n o t o n en o n l i n e a re q u a t i o n sw i t h c o n v e xc o n s t r a i n t s g u a n h o n g b o b s ( w u h a nu n i v e r s i t y ) 2 0 0 4 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fs c i e n c e a p p li e dm a t h e m a t i c s i nt h e g r a d u a t es c h o o l o f h u n a nu n i v e r s i t y s u p e r v i s o r p r o f e s s o rl id o n g h u i a p r i l ，2 0 1 1 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体己经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：炎弓眨刁诞 日期：汐f 年易月 2 e t 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 作者签名： 导师签名： l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 炎墀、礁日期：凹，年2 ) 月日 日期：渺年b 月纱日 求解凸约束单调的非线性方程组的两种算法 = = = = ：= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 竺! = = = = = 摘要 本文提出求解凸约束单调非线性方程组的一种修正p o l a k r i b i e r e p o l y a k ( m p r p ) 算法和s c a l e dc o n j u g a t eg r a d i e n t ( s c a l c g ) 算法在较弱的条件下，证明两 种算法的全局收敛性，并通过数值试验验证算法的有效性 第l 章，简要回顾求解无约束最优化问题的m p r p 和s c a l c g 算法m p r p 是 共轭梯度法中数值表现较好的算法之一，该算法具有收敛速度快和存储量小的优 点，适合求解大规模问题s c a l c g 算法可以理解为是拟牛顿法与共轭梯度法的 结合算法，也适合求解大规模问题本章还简单介绍凸约束单调非线性方程组的 发展背景 第2 章，提出一种求解凸约束单调非线性方程组的m p r p 方法在合理的假设 条件下，证明算法的全局收敛性并通过数值试验对所提出的算法加以检验，结 果表明提出的算法是有效的和稳定的最后，我们对提出的算法进行改进，数值 试验表明改进的算法比原算法有更好的数值表现 第3 章，提出一种求解凸约束单调非线性方程组的s c a l c g 方法在较弱的条 件下，证明算法的全局收敛性我们的数值试验结果表明提出的算法是有效的和 稳定的最后，我们对提出的算法进行改进，大量的数值试验表明改进的算法比 原算法有更好的数值表现 一 关键词：m p r p 方法；s c a l c g 方法；全局收敛性；单调非线性方程组 硕十学位论文 a b s t r a c t i nt h i st h e s i s ，w ep r o p o s eam o d i f i e dp o l a k r i b i e r e - p o l y a k ( m p r p ) m e t h o da n d s c a l e d c o n j u g a t eg r a d i e n t ( s c a l c g ) m e t h o d f o rs o l v i n gm o n o t o n en o n l i n e a r e q u a t i o n sw i t h c o n v e xc o n s t r a i n t s u n d e rw e a k e rc o n d i t o n s ，w ee s t a b l i s ht h e c o n v e r g e n c et h e o r e mo ft h ep r o p o s e dt w om e t h o d s w ea l s od os o m en u m e r i c a l e x p e r i m e n t st ot e s tt h ep e r f o r m a n c eo ft h ep r o p o s e dm e t h o d s i nc h a p t e r1 ，w es i m p l yr e v i e wt h em p r pa n ds c a l c gm e t h o d sf o rs o l v i n g u n c o n s t r a i n e do p t i m i z a t i o np r o b l e m s m p r pi sav e r ye f f i c e n tc o n ju g a t eg r a d i e n t m e t h o d ag o o dp r o p e r t yo fm p r pm e t h o di si t sl o w e rs t o r a g ea n df a s tc o n v e r g e n c e r a t e i ti ss u i t a b l ef o rs o l v i n gl a r g es c a l ep r o b l e m s s c a l c gm e t h o dc a nb er e g a r d e d a sac o m b i n a t i o no fc o n j u g a t eg r a d i e n tm e t h o da n dn e w t o n - t y p em e t h o d i ti sa l s o s u i t a b l ef o rs o l v i n gl a r g es c a l ep r o b l e m s w ea l s ob r i e f l yi n t r o d u c et h eb a c k g r o u n do f t h em o n o t o n en o n l i n e a re q u a t i o n sw i t hc o n v e xc o n s t r a i n t s i n c h a p t e r2 ，w ep r o p o s eam p r pm e t h o df o rs o l v i n gm o n o t o n en o n l i n e a r e q u a t i o n sw i t hc o n v e xc o n s t r a i n t s u n d e rr e a s o n a b l ec o n d i t i o n s ，w es h o wt h a tt h e p r o p o s e d m e t h o di s g l o b a l l yc o n v e r g e n t m o r e o v e r ，w ed o s o m en u m e r i c a l e x p e r i m e n t st os h o wt h a tt h ep r o p o s e dm e t h o di se f f i c i e n t a n ds t a b l e f i n a l l y ，w e m a k es o m ei m p r o v e m e n tt ot h em e t h o d o u rn u m e r i c a le x p e r i m e n t si l l u s t r a t et h a tt h e i m p r o v e dm e t h o dh a sb e t t e rn u m e r i c a lp e r f o r m a n c e i nc h a p t e r3 ，w ep r o p o s eas c a l c gm e t h o df o rs o l v i n gm o n o t o n en o n l i n e a r e q u a t i o n sw i t hc o n v e xc o n s t r a i n t s u n d e rt h es a m ec o n d i t i o n sa st h o s ei nc h a p t e r2 ， w ep r o v ei t sg l o b a lc o n v e r g e n c e w ea l s od os o m en u m e r i c a le x p e r i m e n t ss h o wt h a t t h ep r o p o s e dm e t h o d sa r ee f f i c i e n ta n dp r o m i s i n g f i n a l l y ，w ed os o m ei m p r o v e m e n t t ot h em e t h o d al o to fn u m e r i c a le x p e r i m e n t si l l u s t r a t et h a t c o m p a r e dt o t h e s c a l c gm e t h o d ，t h ei m p r o v e dm e t h o dh a sb e t t e rn u m e r i c a lp e r f o r m a n c e k e yw o r d ：m p r pm e t h o d ；s c a l c gm e t h o d ；g l o b a lc o n v e r g e n c e ；m o n o t o n e n o n l i n e a re q u a t i o n s 求解n 约束单调的北线性方程纽的两种算法 目录 学位论文原创性声明和学位论文版权使用授权书i 摘要1 i a b s t r a c t i i i 目录i v 第1 章绪论1 1 1 求解无约束最优化问题的共轭梯度法及其修正形式1 1 2z h a n g z h o u - l i 的m p r p 算法3 1 3s c a l c g 算法4 1 4 凸约束单调非线性方程组概述5 1 5 本文的主要工作一6 第2 章求解凸约束单调的非线性方程组的m p r p 算法8 2 1 算法8 2 2 全局收敛性1 0 2 3 数值试验1 7 2 4 算法的改进1 9 2 4 1 改进算法介绍1 9 2 4 2 改进算法2 0 2 4 3 改进算法的全局收敛性2 0 2 4 4 改进算法的数值试验2 5 第3 章求解凸约束单调的非线性方程组的s c a l c g 算法2 8 3 1 算法2 8 3 2 算法的全局收敛性3 0 3 3 数值试验3 7 3 4 算法的改进3 9 3 4 1 改进算法介绍3 9 3 4 2 改进算法4 0 3 4 3 改进算法的数值试验一4 0 结论一4 3 参考文献4 4 致谢4 8 硕j j 学位论文 第1 章绪论 本文研究求解非线性方程组的数值算法由于求解非线性方程组的算法与求 解最优化问题的算法有很大关系，我们先简要的回顾一下求解最优化问题的相关 算法 1 1 求解无约束最优化问题的共轭梯度法及其修正形式 考察无约束最优化问题【1 , 2 】 m i n f ( x ) ， x r ” ( 1 1 ) 其中f ( x ) ：r ”_ r 为连续可微函数，我们用w ( x ) 表示厂在x 处的梯度 求解无约束最优化问题( 1 1 ) 常用下降算法，其步骤如下： 算法1 1 ( 求解无约束问题的下降算法) 步0 给定初始点x o r ”，精度s 0 ，令k ：= 0 步1 若l i v i ( x 。) l l 占，则算法终止，得解x k 否则，转步2 步2 确定下降方向巩，使得 w ( 以) 。吨 0 ，使得 f ( x k + 吨) r ”是连续的映射 非线性方程组的求解无论在理论上还是在解法上都还不够成熟例如对非线 性方程组是否有解，有解的话有多少解，在理论上都没有得到解决在解法上， 大部分非线性方程组是很难直接求出精确解的但是随着科学技术的发展和计算 机的广泛应用，科学家们更多的是利用这些工具用迭代法来求解非线性方程组的 解 单调的非线性方程组是非线性方程组的一种特殊情况我们称( 1 1 1 ) 为单调的 非线性方程组若f 是单调映射，即，满足 ( f ( x ) 一f ( y ) ，x y ) 0 ，v x ，y r ” 单调的非线性方程组有着很强的实用性例如在广义的带b r e g m a n 距离近似 点算法中【1 7 1 ，子问题往往是单调的非线性方程组在过去的l0 年中，无约束单 调的非线性方程组的求解得到了广泛的关注，参考文献【l8 ，19 ，2 0 ，2 2 ，2 3 ，2 5 】在已 有的众多方法中，由s o l o d o v 和s v a i t e r l l 8 j 提出的牛顿法具有非常好的全局收敛性， 该算法不需要满足正则性假设，迭代的点列就全局收敛于方程组的解随后在标 准的非奇异条件下s o l o d o v 和s v a i t e r 证明了算法是超线性收敛的s o l o d o v 和 s v a i t e r 的算法的基本思想是构造一个超平面，将当前点和问题( 1 1 1 ) 的解集分离， 再把当前点投影到超平面上产生下一迭代点在更弱的条件下，z h o u 和t o h 1 9 】 证明了算法依然保持超线性收敛最近s o l o d o v 和s v a i t e r 对单调方程组做了更深 入的研究，包括无约束单调方程和凸约束单调方程z h a n g 和z h o u 2 0 l 提出的方法 是在求解无约束最优化问题的谱梯度算法【2 1 】基础之上的z h o u 和l i i 2 2 1 提出的算 求解凸约束单调的非线性方程组的两种算法 法是基于有限记忆b f g s 算法之上的z h o u 和l i t 2 3 1 基于l i 和f u k u s h i m a 2 4 j 的修 正b f g s 算法，进一步改进了有限记忆b f g s 算法最近，y a h ，p e n g 和l i l 2 5 j 通 过结合修正h s 算法和投影方法，对于求解大规模的单调的非线性方程组提出了 无导数方法 凸约束非线性方程组，即 f ( x ) = 0 ，x q 其中q 是非空闭凸集 凸约束单调非线性方程组的求解有很重要的实际意义例如，在化学平衡问 题中与一定元素相对应的变量一般都是非负的，而在许多生态平衡问题中，映射 f 并非确定的，必须在变量上加上一些适当的约束才行w a n g 等f 2 6 ，2 7 1 改进了 s o l o d o v 和s v a i t e r ”】的算法，在凸约束的条件下求解单调方程组并在适当的条 件下，证明了算法的全局收敛性和局部的超线性收敛然而，如同s o l o d o v 和 s v a i t e r 提出的算法，即使数值试验显示算法有很好的数值结果，在每次迭代的时 候，依然需要一个线性系统决定搜索方向为了迸一步证明方法的有效性，y u 等 【2 8 】改进了谱梯度算法，在每次迭代的时候不再需要线性系统数值结果显示他们 提出的算法有更好的表现 x i a o 和z h u l 2 9 最近提出了求解大规模凸约束单调非线性方程组的一种算法， 结合了著名的共轭梯度法c g d e s c e n t 3 0 , 3 1 1 和s o l o d o v 和s v a i t e r 1 8 j 提出的投影方 法该算法的基本思想就是从给定的初始点出发，构造点列 吒l ，算法的最终 目标是使得点列 而 中的某个点或某个极限点是问题的解或稳定点其中最重要 的就是已知当前点坼，如何确定下一迭代点& + 。在【2 9 】中，己知当前点黾，在确 定下一迭代点以+ 时，先建立一个超平面， a 以= x r ”：( f ( 气) ，x - z k ) = o 超平面严格的分离了当前点x k 和问题的解集下一迭代点黾+ 。是将坼投影到超平 面o h k 上，然后再投影到q 上即 黾+ l = 晶l 吒一a k f ( z k ) 1 在每次迭代中，算法不需要计算和存储j a c o b a n 矩阵，因而适合求解大规模 问题在较弱的条件下，x i a o 和z h u 2 9 1 证明了提出的算法的全局收敛性大量数 值实验表明，提出的算法对大规模问题是有效的和稳定的 有关求解非线性方程组的其它进展，可参考文献【3 2 4 1 】 1 5 本文的主要工作 本文所作的主要工作有，提出了两种求解凸约束单调非线性方程组的方法一 种是m p r p 算法，另一种是s c a l c g 算法在较弱的条件下，我们证明两种算 硕十学位论文 法的全局收敛性，并通过数值试验对算法进行检验，结果表明两种算法在求解大 规模问题时都有良好的数值表现 本文以后的各章节安排如下： 第2 章提出求解凸约束单调非线性方程组的m p r p 算法，它是在求解无约束 最优化问题的m p r p 算法的基础上改进得到的在第l 节中我们给出了用m p r p 求解凸约束单调非线性方程组的方法第2 节中对提出的算法的全局收敛性给出 证明第3 节我们通过数值试验对提出的算法进行测试，检验其数值效果在第 4 节中我们对提出的算法进行改进，证明改进算法的全局收敛性，并利用数值试 验与原有的算法进行比较，说明了改进后的算法的优良表现 第3 章提出求解凸约束单调非线性方程组的s c a l c g 算法它是在求解无约 束最优化问题的s c a l c g 算法的基础上改进得到的第l 节提出用于解决凸约束 单调非线性方程组的s c a l c g 算法第2 节我们证明提出的算法在一定条件下的 全局收敛性第3 节给出数值试验检验算法的有效性第4 节我们给出算法的改 进，并利用数值试验与原有的算法进行比较，说明改进后的算法的优良表现 求解凸约束单调的非线性方程组的两种算法 第2 章求解凸约束单调的非线性方程组的m p r p 算法 考虑凸约束单调的非线性方程组 f ( x ) = 0 ，x q ( 2 1 ) 其中可行域q 是非空闭凸集，f ：r ”一r ”是连续单调的映射即满足 ( ，( x ) 一f ( j ，) ，x y ) 0 ，v x ，y r ”( 2 2 ) 本章我们将求解无约束最优化问题的m p r p 算法的思想加以改进，并应用于 求解单调非线性方程组( 2 1 ) ，提出一种求解凸约束单调的非线性方程组的m p r p 算法并且证明在适当条件下算法的全局收敛性我们在下一节中提出算法；在 第2 节中证明算法的全局收敛性；第3 节进行数值试验；第4 节对算法进行改进， 证明改进算法的全局收敛性，并对改进的算法进一步用数值实验加以检验 2 1 算法 本节，提出求解凸约束单调的非线性方程组的m p r p 算法 求解无约束最优化问题的m p r p 算法中，搜索方向 ，f g k ， k = 0 ， 巩2 t 一+ 剧御以一，一哦儿，七1 ， 其中群肿= 皆，吼= 皆，y k - i = g k - g k - i 借助于求解无约束最优化问题m p r p 算法的思想，我们构造求解问题( 2 1 ) 的 m p r p 算法算法中，以按如下方式确定 。 f 只，k ：0 ， 巩2 t i + 展，矾一。一幺，儿巾七1 ， q 3 其中参数孱和o k 也类似于m p r p ， 肛静叫= 背 其中，儿= 圪+ 矗l i e i i 巩，以= e + ，一只， 纠+ l l 刚m a x 卜臀 8 ( 2 4 ) 硕士学位论文 气是步长，它由线性搜索确定，将在稍后的算法中给出具体定义上面的儿的定 义同 2 0 ，2 4 类似 由定义不难看出，畋具有如下的性质 引理2 1 设序列 喀) 由( 2 3 ) 生成，则对任意的k ，有 ( e ，以) = 一i i e l l 2 证明：当k = o 时，( 矗，哦) = 一i i 冗1 1 2 当后1 时， c ，= p 最+ 静电一背 叫时+ 背( ) 一智( ) = 一蚓1 2 ( 2 5 ) 证毕 为了描述我们的算法，我们定义了一个从r ”到q 上的投影算子晶【】，即 p o x = a r g n m l l y - x l l ：yq ，帆r ” 算子晶【】是非扩张的，即 恢h 一晶洲卜y 0 ，v x ，y r ” 下面我们提出求解方程组( 2 1 ) 的m p r p 算法，其具体步骤如下： 算法2 1 ( 求解凸约束单调非线性方程组的m p r p 算法) 步0 取初始点q ，给定常数孝 0 ，盯( o ，1 ) ，户( 0 ，1 ) ，令k ：= 0 步1 若i l e l | = - ( f ( z k ) - f ( - i ) ，z k i ) o ( 2 7 ) 沿着搜索方向反采取某种线性搜索，生成点气= x k + 反，有 ( f ( z 。) ，x k 一乙) = ( f ( + 以) ，- t k d k ) = - - t k ( ，( + t k d k ) ，畋) 1 2 0 ( 2 8 ) 由( 2 7 ) 式和( 2 8 ) 式易知超平面 o h k = x r ”：( f ( 乙) ，x - z k = o 严格的分离了当前点吒和问n ( 2 1 ) 的解集基于这个事实，步3 说明，一旦超平 面确定，下一迭代点+ 。是将坼投影到超平面o h k 上，然后再投影到凸集q 上这 也是算法2 1 的核心 注2 2 由算法的步骤知( 2 4 ) 式中未定义的气其实是算法2 1 中1 土1 ( 2 6 ) 式确定 的步长 2 2 全局收敛性 本节，我们将证明算法2 1 的全局收敛性为此，我们做如下假设： 条件a ( 1 ) 单调映射f 在q 上l i p s c h i z 连续，即存在常数三 0 ，使 f i f ( x ) - f ( y ) 1 l i i x - y l i ，v x ，y q ( 2 9 ) ( 2 ) 问题( 2 1 ) 的解集s 非空 本章余下的部分中，若无特别说明，我们总假设条件a 成立 、 引理2 2 算法2 1 是适定的 证明：我们只需证明算法2 1 中的步2 是适定的事实上，在( 2 6 ) 的左边对 专0 取极限，得其极限为i i f , 1 1 2 ，而右边的极限为0 ，因此算法2 1 是适定的 证毕 引理2 3 如果假设条件a 成立，由算法2 1 产生的步长满足 忙m i n k pi i f , 1 1 2 亿 证明：如果算法在迭代k 次时终止，则0 e0 2 0 ，就是问题的解下面假设 硕十学位论文 对所有的k ，都有e 0 ，则由( 2 5 ) 式知畋0 我们下面说明了算法是成立的并 且生成了无限点列 赡) 我们也说明了线性搜索步骤( 2 6 ) 通常都是在有限步终止 若气孝，由线性搜索，知气= 户1 气不满足( 2 6 ) ，即一( f ( 乙，) ，矾) 0 f ( z 。) 一f ( k ) l l i i 畋l l + 讲。o 以1 1 2 三0 气一舯矾o + 洲。i i 以8 2 = 巩1 1 d , 1 1 2 + 盯2 = p - , ( 三+ 盯) 气慨1 1 2 由此即得( 2 1 0 ) 证毕 引理2 4 如果假设条件a 成立，序列 吒 由算法2 1 产生，则 i i e l l ) 有界即 对任意的k 0 ，存在一个正数m 0 ，便得 伊( 坼) 忙m ( 2 11 ) 证明：由单调性( 2 2 ) 式，有 ( f ( 乙) ，- y ) = ( f ( z k ) ，黾一磊+ 乙一i ) = ( f ( 气) ，吒一气) + ( f ( 乙) ，磊一i ) = ( ，( 乙) ，吒- - z k ) + ( f ( z k ) 一f ( x - ) ，气一i ) ( f ( 乙) ，- - z k ) 由投影算子的非扩张性，有 0 以+ 。一i l l 2 = i p ot x , 一f ( z ) 】一i i l 2 求解凸约束单调的非线性方程组的两种算法 易知， = 0 晶【吒一吼f ( 乙) 卜最( i ) 1 1 2 - i l 吒一a k f ( z k ) 一i i l 2 = 0 吒一i l l 2 2 a k ( f ( z k ) ，x k i ) + i l ，( 气) 0 2 - l i 一i 8 2 2 a k ( f ( 气) ，一乙) + 口；8 ，( 气) 1 1 2 = i i 一i i l 2 2 背( f ( z k ) , x k - z 。) + 瞥f ( 气) i | 2 = l l x k - i i l 2 一瞥 - l l x 。一i i l 2 x k + l _ i 0 2 - i i 坼一i i l 2 - i i x 。- l - i i l 2 - l l + 0 1 2 硕 j 学位论文 ( - f ( z k ) ，以一i ) 0 证毕 注2 3 引理2 5 说明了算法2 1 中取一，( z 膏) 为下降方向的理由 引理2 6 如果假设条件a 成立，序列 而 和 气 由算法2 1 生成，则 ( 1 ) x k ) 和 乙) 有界 ( 2 ) 下面的关系式成立 特别地， ( 3 ) 下面的关系式成立 证明：( 1 ) 由( 2 1 2 ) 式知 ! 受( 吒一乙) = o ! i m 。! ti i 以l l = o l i m ( h x k + 1 ) = 0 膏- - 4 0 0 i x k i 8 2 - 1 1 - l - i 0 2 - l l 吒一：一i 屿恢一i i l 2 所以 x k ) 有界 由( 2 2 ) 式，( 2 6 ) 式和( 2 1 1 ) 式，有 ( f ( z k ) ，坼一) = ( ，( ) ，_ f 量巩) = ( ，( 名) ，反) 所以，有 即 倒刘以0 2 = 仃0 坼一气0 2 ， ( ，( 气) ，x k - z k ) = ( f ( 磊) 一，( 屯) ，x k 一气) + ( ，( 坼) ，五一z k ) 限_ ) | i | | 坼一乙0 m 恢- z k 1 仃0 吒一z k l l 2 0 f ( 吒) i | f | 一z ku 所以 z k ) 有界 ( 2 ) 由( 2 1 2 ) 式和( 2 1 4 ) 式，有 卜气忙等 ( 2 1 3 ) ( 2 1 4 ) 求解凸约束单调的非线性方程组的两种算法 i i 吆“一i l l 2 o 砟一i i l 2 一帮 0 ，使得 舻( 乙) i | m 则有 所以 i m ( 一气) = 0 鼻 所以 特别的， i i 赡- z k l l 4 等( 卜i i l 2 氐，一i i l 2 ) 驰一乙1 1 4 k 。m 2 卜i i l 2 一i l x k + , - 叉 1 1 2 ) 佃 i m 。i k = ! i m8 x k z t l l = o ( 3 ) 由投影算子的非扩张性，有 1 1 一赡+ 。8 = 0 黾一晶( 吒- - a k f ( z k ) ) i 0 尼( 故) 一晶( - - a k f ( z k ) ) 1 - 占，v k o i l 以1 1 2 = 0 反+ e e 0 2 = i i 矾+ e 1 1 2 - 2 ( 以+ e ，a ) + l l a l l 2 - 2 ( 巩，e ) 一i i e i l 2 = 2 i i e i l 2 一i i e i l 2 = i i e i l 2 1 i 以i i - s ，v k o 因为x k q ，又由投影算子的非扩张性，有 0 五+ ，- 砟i i = i l p o x , 一f ( 乙) 卜吒0 慨- - a k f ( z k ) ) - - x k i = l i f ( z 。) l i 由吒的定义和柯西一许瓦尔兹不等式，有 恢+ ，一| i 恢- z k l i 气慨i i 由此，五的定义和( 2 9 ) 式、( 2 1 1 ) 式、( 2 1 8 ) 式，有 i l y , l l - - i i 以+ 五气0 e0 矾0 - 1 5 譬磐1 ) l l f 。l l l l s l l i 畋o m i l 2 ” ( 2 1 6 ) ( 2 1 7 ) ( 2 1 8 ) 求解凸约束举调的1 f 线性方程组的两种算法 i i 以i i + ( 1 + l i e i i 叫皆帆i i i i i 气巩i i i i 圪i i ( 1 + i i f t i i 。1 剖) i i e i i i 矧i = 2 1 1 r , l l + i i f 。l l l , d , l i = 2 1 l f ( x 。+ ，) 一f ( 砟) 0 + 0 e | | i l f 。矾0 时) ，总是存 在常数，( 。 1 ) ， 使得塑半，七一。i i 以一。i i ， 1 i 巩1 1 - m + r l l 矾一。0 m ( 1 + ，+ 厂2 + + r k - k o - 1 ) + ，“岛恢0 m 击ml i r i i k 0i i l i 玟c = m a x l l d o l l ，慨l l ，i i d , i i ，o 氏f i ，m 击+ l i 氏i i ) ，则对v 尼。，有- g l l c 而由( 2 1 0 ) 式和( 2 1 7 ) 式，有 圳岫；n p 去蝌刚 1 6 - 硕上学位论文 与( 2 1 3 ) 式矛盾所以 证毕 2 3 数值试验 戚np i p e 2 ! 觋i n f l l f , = 0 本节，我们对算法2 1 进行数值试验，检验它的数值效果我们用m a t l a b 编 程，设置终止的条件是 f ( x k ) 1 0 此外，如果当k = 5 0 0 0 时还不满足终止条件，我们也终止算法此时，算法终止 于它的非稳定点 所有的程序在2 3 g h z 处理器，2 g bd d r 内存及w i n d o w sx p 操作系统的 p c 机上运行 取f = l ，p = 0 6 ，盯= 0 0 0 0 1 下表列出了算法试验结果，表中符号定义如下： d i m ：测试问题的维数； i n i t ： 问题的初始点； i t e r ： 迭代次数； t i m e ： c p u 时间； f n ： i i f ( x 。) l i 的最终值 问题1 ：f ( x ) = ( 石( x ) ，石( x ) ，z ( x ) ) t ，这里 z ( x ) = e 而一2 ，f = 1 ，2 ，力，q = 彤， 取初始点分别为( 1 ，1 ，1 ) t ，( 2 ，2 ，2 ) t ，( 1 0 ，0 , - - - , 1 0 ) t ，( 1 ，0 ，l ，0 ，l ，0 ) t 求解凸约束单调的非线性方程组的两种算法 问题2 ： f ( x ) = ( 石( x ) ，厶( x ) ，正( x ) ) t ，这里 z ( x ) = 2 x , - s i n ( i x , - 1 1 ) i = 1 ，2 ，刀，q = 群， 取初始点分别为( 1 ，l ，1 ) t ，( 2 ，2 ，2 ) t ，( 1 0 ，1 0 ，1 0 ) t ，( 1 ，0 ，1 ，o ，1 ，0 ) t 表2 2m p r p 求解问题2 的数值结果 d i m 1 0 0 5 0 0 1 0 0 0 2 0 0 0 i t e r 7 7 7 7 t i m e f n 0 0 0 9 3 9 65 9 15 2 5 5 e 8 0 0 3 6 6 9 61 3 2 2 6 9le 一7 0 0 9 8 3 4 51 8 7 0 5 6 8 e 一7 0 2 0 012 72 6 4 5 3 8 2 e 7 l t e r 2 2 2 4 2 5 2 5 t i m e f n 0 0 314 5 08 0 10 6 3 0 e 一6 0 1 2 1 6 7 47 1 4 8 9 6 8 e 6 0 2 3 2 3 4 06 3 8 7l0 6 e 6 o 5 319 3 4 9 0 3 2 7 3 2 e - 6 5 0 0 0 7 1 6 0 7 9 4 3 4 18 2 7l7 e 一72 6 2 7 2 6 6 8 59 0 2 2 6 6 8 e 6 由上面的数值试验结果表明，本章提出的算法2 1 是求解大规模凸约束单调 非线性方程组的一种有效的算法 1 8 硕士学位论文 2 4 算法的改进 2 4 1 改进算法介绍 算法2 1 的基本思想就是从给定的初始点而出发，构造点列f 以 ，使下一迭 代点毛+ 。比当前点x k 更靠近问题的解i ，即i i x + 。一剐s0 一i | | 算法的最终目标是 使得点列 中的某个点或某个极限点是问题( 2 1 ) 的解或稳定点其中晟重要的 就是已知当前点赡，如何确定下一迭代点而+ 在算法2 1 中，已知当前点，在 确定下一迭代点五+ 时，先建立一个超平面 弧= x r ”：( ，( 气) ，x - z k ) = 0 ) ， 超平面严格的分离了当前点吒和问题的解集下一迭代点黾+ 。是将当前点x k 投影 到超平面a h k 上，然后再投影到q 上即 x k + l = 晶【- - a k f ( z k ) 1 在算法2 1 中，取2 帮那么为什么这样选取? 吼还有没有更 好的选择? 这就是我们要对算法2 1 进行改进的目的在不改变算法的收敛性及 相关的优良的性质和结果的条件下，我们对算法2 1 进行改进，数值结果显示改 进后的算法具有更好的表现 由( 2 1 2 ) 式知，要满足0 以+ ，一引1 2 - 0 ，仃( 0 ，1 ) ，p ( 0 ，1 ) ，( 1 ，2 ) ，令k 一0 步l 若0 e 忙s ，则算法终止，得到问题的解x k 否则由( 2 3 ) 计算以 步2 令t k = m a x c p 7 ：扛o ，l ， ，使之满足 令z k = x k + t k d k 一 0 ，使得 l i f ( x 。) l l - ( ，( 乙) ，收一缸) 硕_ f - 学位论文 由投影算子的非扩张性，r ( 1 ，2 ) ，有 i l 吒+ 。一i 0 2 = 0 尼 砟一吼f ( z j ) 一i l l 2 = m & 叫盹) 卜( 吖 0 坼一吼7 f ( ) 一i l l 2 = i i 砟一i l l 2 2 a k ( f ( z 七) ，x k i ) + ( ) 20 f ( 乙) 1 1 2 易知， - l l 而一i l l 2 2 吒( f ( 气) ，x k 一气) + ( 吼) 2l i f ( 气) 1 1 2 = i i 一i i l 2 一瞥7 c 2 一刁) 恢一i i l 2 0 吒+ 。一i l l 2s1 1 一i l l 2 - l l 吒一。一i i l 2 - l l x k 一：一i i l 2 1 一i 0 2 由( 2 9 ) ，有 0 f ( 吒) i l = i i f ( x k ) - - f ( z ) i 工i i 一i i i l l l x o i 0 令m = 圳一剐，则对任意k 0 ，有 i i f ( x , ) i - m 证毕 引理2 6 如果假设条件a 成立，序列 ) 和 乙) 由算法2 2 ( 1 ) 和 z k 有界 ( 2 ) 下面的关系式成立 特别的， ；i m ( x k 一缸) = 0 膏- - o o 生成，则 帜气) 1 1 2 ( 2 2 0 ) 求解凸约束单调的非线性方程组的两种算法 ( 3 ) 下面的关系式成立 证明：( 1 ) 由( 2 2 0 ) 式知， ! 觋“蚓卜0 l i m ( 一+ i ) = 0 七+ 恢一i 0 2 - 1 1 - l - i 0 2 - l l x k - 2 - i 忙i i x o - i l l 2 所以 x k 有界 由( 2 2 ) 式、( 2 6 ) 式、( 2 1 1 ) 式，有 所以 ( f ( z 。) ，x k z 。) = ( f ( 乙) ，一气以) = - - t k ( f ( z k ) ，以) 斫恻1 2 = 仃恢一气1 1 2 ( f ( z 。) ，x k 一乙) = ( f ( z k ) - f ( x k ) ，x k - - z k ) + f ( x k ) ，耳- - z k ) i i f ( ) l | l i - z k l - a 4 1 1 x