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

河南大学硕士学位论一文 摘要 本论文研究求解凸约束非线性单调方程组的b f g s 算法和有限记忆b f g s 算法， 建立算法的收敛性，并通过数值实验验证算法的有效性 第一章，介绍求解无约束优化问题和非线性方程组的拟牛顿算法，介绍b f g s 方 法和有限记z b f g s 方法的研究及发展现状；简单介绍凸函数与凸集的理论基础 第二章，提出求解凸约束非线性单调方程组的b f g s 方法该算法的重要特点是 不需要计算方程组的j o c o b i a n 矩阵；不需要求解一个线性系统子问题来确定搜索方 向，因此可以用来求解非光滑的方程组在适当的条件下，我们证明算法的全局收敛 性，并通过数值试验验证算法的有效性 第三章，提出求解凸约束的非线性单调方程组的有限记忆的b f g s 方法，相比于 第二章中的算法，本章所提算法不需要存储矩阵，节省存储空间，加快算法运行速度， 提高数值效率，从而更容易应用到求解大规模的问题最后证明算法的全局收敛性， 并使用大规模的问题对算法进行测试，验证了算法的有效性 第四章，给出本论文的总结，并提出一些值得继续探讨的方向 关键词：非线性方程组；拟牛顿法；b f g s 方法；有限记忆的b f g s 方法；全局收敛 性 河南大学硕士学位论文 a b s t r a c t i nt h i st h e s i s ，w es t u d yt h eb f g sa n dl i m i t e dm e m o r yb f g sm e t h o df o rs o l v i n g m 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 ，a n dt h e nw ee s t a b l i s ht h ec 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 dm e t h o dw h o s ee f f e c t i v e n e s sc a l lb ev e r i f i e db yn u m e r i c a l e x p e r i m e n t s i nc h a p t e r1 ，w ei n t r o d u c en e w t o nm e t h o d sf o ru n c o n s t r a i n e do p t i m i z a t i o nn o n l i n e a r e q u a t i o n sp r o b l e m s w ea l s od e s c r i b es o m er e c e n tp r o g r e s so fb f g sm e t h o da n dl i m i t e d m e m o r yb f g sm e t h o d m o r e o v e r ，s o m ep r i m a r yp r o p e r t i e so fc o n v e xf u n c t i o n sa n d c o n v e xs e ta r es o m ei n c l u d e d i nc h a p t e r2 ，w ep r o p o s eab f g sm e t h o df o rs o l v i n gn o n l i n e a rm o n o t o n ee q u a t i o n s w i t hc o n v e xc o n s t r a i n t s a na t t r a c t i v ef e a t u r eo ft h ep r o p o s e da l g o r i t h mi st h a ti ti sn o t n e c e s s a r yt oc o m p u t eo rs t o r et h ej o c o b i a nm a t r i x m o r e o v e r ，t h ep r o p o s e dm e t h o di sn o t n e e dt os o l v eal i n e a rs y s t e mt od e t e r m i n et h es e a r c hd i r e c t i o n sa te a c hi t e r a t i o n h e n c e ， i ti sp o t e n t i a l l yt os o l v en o n - s m o o t he q u a t i o n s u n d e rs o m ea p p r o p r i a t ec o n d i t i o n s ，w e p r o v et h eg l o b a lc o n v e r g e n c eo ft h ea l g o r i t h m a tl a s t ，n u m e r i c a le x p e r i m e n t sw h i c hs h o w t h ee f f i c i e n c ya r ea l s or e p o r t e d i nc h a p t e r3 ，w ep r o p o s el i m i t e dm e m o r yb f g sm e t h o df o rs o l v i n gc o n v e xc o n - s t r a i n e dn o n l i n e a rm o n o t o n ee q u a t i o n s c o m p a r e dt ot h ea l g o r i t h mi np r e v i o u sc h a p t e r ， t h ep r o p o s e da l g o r i t h mi sn o tn e c e s s a r yt os t o r ea n ym a t r i x ，w h i c hi tc a ni m p r o v ei t s p e r f o r m a n c ea n ds u i tf o rs o l v i n gl a r g e - s c a l ep r o b l e m s f i n a l l y , w ee s t a b l i s ht h eg l o b a l l y c o n v e r g e n c eo fa l g o r i t h m ，a n dt e s ti t se f f e c t i v e n e s sb yu s i n gs o m el a r g e - s c a l ep r o b l e m s i nc h a p t e r4 ，w eg i v eas u m m a r yo ft h i sp a p e ra n ds o m ef u r t h e rr e s e a r c ht o p i c s k e yw o r d s ：m o n o t o n ee q u a t i o n s ；q u a s i - n e w t o nm e t h o d s ；b f g sm e t h o d s ；i 广b f g s m e t h o d s ；g l o b a lc o n v e r g e n c e i i 关于学位论文独立完成和内容创新的声明 了蚋僦= 瑟蝌i 霪 ：，爹溅爹差矗， 学位砷请表。嫦住论交作者釜名：，鉴超监盟3 一鬻； 鼍锄辫菇糍矽“遘荸 学住获得者( 学位论文作者) 釜名：蟹堡豳 2 0年 月 日 学位论文指导教师签名：至煌! 盈 2 0 o 年 月 日 第一章绪论 最优化理论与方法是一门应用性很强的学科，它研究如何从某些实际问题的众 多可行方案中找出最优的方案最优化广泛应用于工程设计、经济规划、生产管理、 交通运输、国防等重要领域近年来，由于生产和科学研究突飞猛进地发展，特别是 电子计算机日益广泛的应用，使最优化理论与方法的研究不仅成为一种迫切需要，而 且有了求解的有力工具因此最优化理论和算法迅速发展起来，形成一个新的学科 非线性方程组的数值解法在实际中有较多的应用，特别是各种非线性问题在科 学计算中更显现出它的重要性而且，随着计算机的广泛应用，有更多的领域涉及到 非线性方程组的求解问题例如，动力系统、非线性有限元问题、非线性力学问题， 还有非线性最优化与非线性规划问题等因此，研究非线性方程组的解法就具有重 要的实际意义 1 1 无约束优化问题 1 1 1 求解无约束问题的牛顿法 无约束最优化问题的基本形式 m i n f ( z ) z 舻 ( 1 1 ) 其中，：舻_ 跄称为目标函数( 1 1 ) 的最优解定义如下： 如果存在6 0 ，使得对所有满足忙一z + i i ，( 矿) ) ， 则称矿为( 1 1 ) 的局部( 严格局部) 最优解 如果对所有的z 舻，( z ) 厂( z + ) ( ，( z ) ，( 矿) ) ，则称矿为( 1 1 ) 的全局( 严格全 局) 最优解 求解无约束最优化问题( 1 1 ) ，我们一般采用迭代法，其基本思想是：给出一个初 始点x o 舻，按照一定的准则产生一个点列 z 知 ，使当钆是有限点列时，其最后一点 是问题( 1 1 ) 的最优解；当是无穷点列时，它有极限点，且其极限点是问题( 1 1 ) 的最 优解目前已经有许多有效的求解方法，如：牛顿法、拟牛顿法、共轭梯度法、谱梯 度法等 】 河南大学硕士学位论文 牛顿法是求解上述优化问题( 1 1 ) 古老而有效的方法，相对于其它的求解无约束 问题的方法，该方法在找到最优点时需要较少的迭代次数和函数值计算次数，其基 本思想是利用目标函数的二阶泰勒展开，并将其极小化即： ，( z 七十s ) g ( 动( s ) = ，( z 七) + v ，( z 七) t s + 丢s t v 2 ，( z 七) s ( 1 2 ) 其中，s = z z 知，g ( 七) ( s ) 为，( z ) 的二次近似将上式右边极小化，便得 x k + l = x k 一 v 2 ，( z 七) 】_ 1 v f ( x k ) ，( 1 3 ) 这就是牛顿法迭代公式古典的牛顿法具有如下的迭代形式 x k + l2x k + d k ，k = 0 ，1 ， ( 1 4 ) 令g ( x k ) = v f ( x k ) f f i g ( z k ) = v 2 i ( x k ) 分别表示函数，( z ) 在点z 七的梯度和h e s s i a n 矩阵 根据( 1 4 ) 贝i j ( 1 3 ) 式也可以写成 d k = 一c ( x k ) g ( x k ) ( 1 5 ) 牛顿法的一个显著优点就是具有局部的超线性甚至二阶收敛速度，由于牛顿法 这一优点，使其成为颇受欢迎的算法之一当c ( x 知) 稀疏时，牛顿法需要较少的存储 量，因而，牛顿法可用于求解当c ( x k ) 稀疏时的优化问题 1 】然而，牛顿法要求计算 目标函数的二阶导数，并且当迭代点远离问题( 1 1 ) 的解时，( z ) 的h e s s i a n 矩阵可能 不正定甚至奇异，此时( 1 2 ) 式可能无解，从而导致牛顿法失败【l ，2 】克服牛顿法这 一缺陷的一个主要途径是采用拟牛顿法，拟牛顿法在构造搜索方向时只需要利用 目标函数值及其一阶导数的信息，避免t h e s s i a n 矩阵的计算，减少了计算量，并且 保持超线性收敛的优点【1 ，2 】对拟牛顿法求解无约束优化问题也取得了很大的进 展7 ，9 ，1 7 ，1 8 ，1 9 ，2 0 ，接下来我们将介绍有关拟牛顿法 1 1 2 求解无约束问题的拟牛顿法 拟牛顿法是在牛顿法的基础上发展起来的，其基本思想是利用某个矩阵风作 为g ( 飘) 的某个近似取代拟牛顿法的般格式为： x k + l2z 七4 - 乜七d k ， 2 ( 1 6 ) 河南大学硕士学位论文 其中d 缸是在点z 惫处的牛顿方向： 如= 一巧1 9 ( z 鬼) ， ( 1 7 ) 其中q 七是步长，通常由某种线性搜索确定吼是a ( x 南) 的近似它满足下面的拟牛顿 方程： b k + l s k = y k ， ( 1 8 ) 其中讥= g ( x k + 1 ) 一夕( z 知) ，s 奄= z 知+ 1 一z 七 拟牛顿矩阵b k + l 的不同的校正公式导致不同的拟牛顿法著名的拟牛顿校正公 式有b r o y d e n 秩一校正公式( r 1 ) 27 】，对称秩一校正公式( s r l ) 2 7 ，d f p 校正公式【l0 】， b f g s 校正公式【1 2 】，p s b 校正公式 2 】，它们分别由下面这些公式定义： b 群1 ：b k + ( y k - f b k s k ) s t 。b 惫s + m ，= b 七+ 鱼竺二若孑兰毫掣 一b 惫d + f ，p = 风+ 鱼竺二鍪兰立茧毛砉差掣一鱼铲鲰露 b b f g s = 反一髻+ 舞 b 南p + s 。b = 风+ 鱼丝二塾璺立窭蠹善巡一鱼铲跃8 丢 很明显看到，d f p , p s b ，b f g s ，s r i 校正公式都是对称的，它们适合求解对称问 题，而b r o y d e n 秩一校正公式r 1 是不对称的，它常用于求解不对称问题如果醒s 七 0 ， 贝, i j d f p 和b f g s 公式保持迭代矩阵风是对称正定性，而其它几种方法不具有这种性 质b f g s 方法具有d f p 校正所具有的各种性质，大量的数值结果表明b f g s 方法的数 值效果优于其它的拟牛顿法，它是求解无约束优化问题的拟牛顿方法中最有效的方 法之一由q ：b f g s 公式的正定性，因此，常用来求解最优化问题( 1 1 ) 它由b r o y d e n 4 ， f l e t c h e r 8 ，g o l d f a v b 1 1 和s h a n n o 5 所提出求解问题( 1 i ) 的b f g s 方法的算法步骤如 下： b f g s 算法 步0 选择初始点x o 舻，初始对称正定矩阵b o 咿黼，计算梯度9 ( z o ) ，令：= 0 步1 如果9 ( z 七) = 0 ，则算法终止否则，令如之霹1 9 ( x k ) 河南大学硕士学位论文 步2 对函数，( z ) 在点z 七处沿着方i f i - j d k 进行某种线性搜索，得到步长o i 七，令 z 后+ 1 = z 七+ a k d k 计算g ( x k + 1 ) 步3 由如下公式计算b k + 1 ： b k + l ：风一訾+ 襄， 其中s 知= z 七+ 1 一z j c ，瓤= 9 ( z 血+ 1 ) 一g ( x k ) 步4 令竞：= k + 1 ，转步1 b f g s 方法中矩阵b 七十1 满足拟牛顿条件( 1 8 ) 式众所周知，拟牛顿方程满足 b k d k + v f ( x k ) = 0 可以看出 v f ( x k ) t d k = 一v f ( x k ) t 巧1 v ，( z 七) 若圾对称正定的，贝1 v f ( x k ) d k 0 ，即如是，( 。) 在z 南处的一个下降方向计算步长a 所 使用的线搜索通常有如下几种方式 a r m i j o 线搜索：给定6 ( 0 ，1 ) ，求q = m a x ，歹= 0 ，1 ，2 ，) 满足 f ( x k + t 誓k d k ) f ( z k ) + j n 知打比，( 1 9 ) 其中p ( 0 ，1 ) w o l f e 线搜索：即q 七同时满足下面的两个不等式 其中盯1 ，0 2 为常数，满足0 仃1 吾盯1 o 满足下面的w o l f e - p o w e l l 条件： f ( x k + o e k d k ) f ( x k ) + a l a k g t d k 玉1 d k c r 2 夕蚕札 令x k + 1 = z 知+ 0 t k d k 步3 令俞= m i n 七+ 1 ，m ) ，取磺= 躲， 风+ 1 = ( 昭唾俞) 日1 0 ( k 前一圪) 肃 俞一j 一1 俞一，一1 + m 一俞钾( i i 曙z ) s 七一州s 州( i i 昭。) ( 1 1 6 ) ( 1 1 7 ) ( 1 1 8 ) 步4 k = k + 1 ，转步1 在上面的算法中，只需要存储m + 1 个向量 8 t ，玑) 叁七一m ，就能计算矩阵风+ 1 ，而 其中最主要的是计算毗= - - h k f ( x k ) ，计算凰f ( 现) 的一个有效的公式见n o c e d a l 【2 3 】 在实际计算中，可以根据问题规模的大小以及机器容许的内存，通过适当选择m 来控 制所需的存储量一般情况下，m 的取值为3 2 0 【2 8 】 1 2非线性方程组 许多非线性问题的求解都可以转化为对形如： f ( x ) = 0( 1 1 9 ) 的非线性方程组的求解其中，f 是蹰竹一舻的连续可微函数 研究如何求解问题( 1 1 9 ) 在理论和实际应用上都有很大的意义非线性方程组的 求解并不像线性方程组那么简单，大部分方程组都很难直接求出其精确解，因此我 们主要考虑应用迭代解法求解非线性方程组的数值解在求解非线性方程组的迭代 方法中，牛顿法是古老而有效的方法之一很多有效的迭代法都是以牛顿法为基础 并由它发展而得到的 6 河南大学硕士学位论文 1 2 1求解非线性方程组的牛顿法 牛顿法是求解非线性方程组( 1 1 9 ) 经典的方法之一，类似于无约束最优化问题， 其迭代格式为： 其中如是下列线性方程组的解 x k + l = z 知+ d k ，( 1 2 0 ) f ( z 七) + f 7 ( 。七) d k = 0 ，( 1 2 1 ) f 7 ( ) 是f 在x k 点j a c o b i a n 阵 由于牛顿法需要计算j a c o b i a n 矩阵，所以比较麻烦而且当j a c o b i a n 矩阵奇异时 和近似奇异时，牛顿法可能失败由于牛顿法的以上不足，许多学者对牛顿法进行了 研究与改进，取得了丰富的成果，拟牛顿法是这些成果中的杰出代表 1 2 2 求解非线性方程组的拟牛顿法 拟牛顿法是在牛顿法基础上发展起来的求解非线性方程组的有效方法，求方程 组的拟牛顿法的迭代与求无约束最优化问题的格式相同只需要将( 1 8 ) 中y k 的定义 改为： y k = f ( x k + 1 ) 一f ( 瓢) 其中，既是f 的j a c o b i a n 矩阵f 7 ( z j c ) 的的某个近似注意到玑f 7 ( x k + 1 ) 8 k ，因此，取+ 1 与f 7 ( z 七+ 1 ) 沿方向乳很接近如果f ( x k ) = v ，( 七) ，即f 是函数，的的梯度，则上面的 算法即为求解( 1 1 ) 无约束最优化问题 拟牛顿法不需要明显计算j a c o b i a n 阵，同时保持牛顿法的快速收敛性质自2 0 世 纪6 0 年代b r o y d e n 第一次提出求解非线性方程组的拟牛顿法后 7 ，因为此方法理论性 和实际计算中的有效性，很快受到最优化工作者和计算数学家的特别关注，特别是 拟牛顿法的局部收敛性得到了广泛的研究【2 ，3 ，6 ，1 5 1 拟牛顿法把j a c o b i a n 矩阵用 某个性质好的矩阵代替，它不但克服了牛顿法需要求导的缺点，同时还能保证迭代 的超线性收敛速度 2 4 】近年来，许多学者已经成功地把优化方法运用到求解非线 性方程组中，z h o u 和l i 2 4 应用t s o l o d o v 和s v a i t e r 投影策略的b f g s 方法提出了有限 记忆的b f g s 方法z h a n g 和z h o u 4 6 提出了谱梯度投影法对于求解非线性性方程组 7 河南大学硕士学位论文 w e i s s 2 5 推广了无约束优化的共轭梯度法，提出了求解非线性方程组的正交化方法， f l e t c h e r 1 6 提出了求解非线性方程组和不等式组的过滤器型方法 1 2 3 单调非线性方程组 接下来我们再简单考虑非线性方程组一种特殊情况，即单调的非线性方程组 也就是方程组( 1 1 9 ) 具有单调性，所谓的单调性，指的是 ( f ( z ) 一f ( 可) ，z y o ，vz ，掣舻 单调的非线性方程组有很强的实用性例如在广义的带b r e g m a n 距离近似点算 法中，子问题往往是单调的非线性方程组【4 8 对于求解单调方程组可以通过多种方 式来例如，在【3 1 ，3 6 ，4 6 ，5 0 s o l o d o v $ i l s v a i t e r 3 1 提出了一种求解单调的非线性方 程组的不精确牛顿型算法该算法的一个重要特征是在没有其它正则条件下，算法 产生的序列整个收敛于问题的解并且，在标准假设下此算法具有超线性收敛性与 经典全局化不同的是，在算法中利用线搜索不是计算步长使得某效益函数值充分下 降，而是构造一超平面使当前点与解集分离，再把当前点投影到此超平面产生下一 迭代点z h o u - t o h 5 0 给出了满足在局部误差界的假设下算法具有超线性收敛性，它 是弱于标准的非奇异性的假设最近，y a h ，p e n g 和l i 通过结合修正h s 共轭梯度法投 影方法，提出了无导数的方法对于求解大规模的非线性单调方程组。 1 3凸分析理论基础 1 3 1 凸集 定义：设集合cc 舻，如果对任意x l ，x 2 c 有 q z l + ( 1 一a ) x 2 gv q 【0 ，1 】，( 1 2 2 ) 则称c 是凸集 这个定义表明，如果x l ，x 2 c ，则连接。l 和z 2 的线段属于d 1 3 2凸集的性质 我们先来介绍一下凸集的一些重要性质： 8 河南大学硕士学位论文 ( 1 ) 若c 冬咿是凸集，则对任意口乳，集合 a c 圭 口x l x c 】 是渺中的凸集 ( 2 ) 若q ，q 渺是凸集，则集合qn q ， q + q 圭 z = z 1 + x 2 i x l a ，z 2 c 2 】- 都是咿中的凸集 ( 3 ) 映射c 是舻上的一个非空闭凸子集，其中，i l 表示2 一范数，一个重要的性质是 i i p e x 】一p c y i l i i x 一矽i i ，v z ，y 渺 ( 1 2 3 ) 对于问题( 1 1 9 ) 如果存在凸集c ，则问题可归于有约束的单调方程组求解约束 非线性方程组具有特殊的重要意义例如，在化学平衡问题中与一定元素相对应的 变量一般都是非负的，而在许多生态平衡问题中，映射f 并非确定的，必须加一些适 当的约束在变量上才行出于对s o l o d o v 和s v a i t e r 3 1 求解单调方程组的动机，w a n ge t a 1 【3 2 提出了投影方法对于有约束的单调方程组，它的方法的显著优点是对于解 决每个迭代都是线性的，而且可以成为对于求解近似问题的一个判断准则在某些 适当的条件下，他们列出了全局收敛性和局部的超线性收敛速度数值实验表明，其 算法是有效的和有希望的为了提高w a n g 等方法的有用性最近，y u 等【4 7 提出了谱 梯度法对于凸约束的单调方程组，计算结果表明，提出的算法是有用的 9 、，q 2 zq 1 z 2 z l z = z r t 1 i q q 和 河南大学硕士学位论文 1 4本文主要工作 本文就是在上述工作的基础上作了进一步的研究，主要贡献及创新点如下： 第2 章，基于w a n g 等的投影方法【3 2 ，提出一种求解具有凸约束的单调非线性方 程组的b f g s 算法，该算法的重要特点是不需要计算方程组的j a c o b i a n 矩阵；不需要 求解一个线性系统子问题来确定搜索方向，因此可以用来求解非光滑的方程组最 后，在不假设方程组的j a c o b i a n 矩阵非奇异的条件下得到方法的全局收敛性并通过 数值试验验证算法的适定性 第3 章，提出了一种求解单调非线性方程组的有限记忆的b f g s 方法并建立了全 局收敛性定理，动机主要来自于有限记忆的b f g s 算法对于具有高维的无约束优化 问题是非常有效的，与第二章提到的方法相比较，该方法不需要存储矩阵，节省存储 空间，加快算法运行速度，提高数值效率，从而更容易应用到求解大规模的问题。 1 0 河南大学硕士学位论文 1 5本文所用的记号 实变量 目标函数 函数的维数 全体实数组成的集合 全体札维实向量组成的集合 函数，在点z 的梯度 函数，的h e s s i a n 矩阵 目标函数，的h e s s i a n 矩阵逆近似 方程组f 的j a c o b i a n 矩阵 f 7 ( z ) 的拟牛顿近似 矩阵a 的转置 单位矩阵 向量的欧氏范数 1 1 就胁化融舭擀荆砂蹦琢小 第二章求解凸约束的非线性单调方程组的b f g s 方法及其收 敛性 2 1引言 考虑下面的非线性方程组的求解： f ( x ) = 0 ，z c ，( 2 1 ) 其中f ：咿一舻连续和单调的，并且( f ( z ) 一f ( 可) ，x - - y ) 0 ，vz ，y 渺，且cc 舻是 非空闭凸集对于这个问题，我们基于文献 3 1 的超平面投影的思想和文献【3 6 中 的b f g s 方法，提出一种适于求解凸约束的非线性单调方程组的b f g s 方法，该方法的 一个显著特点就是不利用任何度量函数此外，该方法也不需要假设f ( z ) 可微，因而， 本文的方法还能够求解非光滑的非线性方程组最后，在不假设方程组的j a c o b i a n 矩 阵非奇异的条件下得到算法的全局收敛性 2 2b f g s 算法设计 本节具体描叙b f g s 算法首先，回顾一下文献 3 1 中求解单调非线性方程组( 2 1 ) 的 超平面投影的思想，其中f 是单调的，有 ( f ( 纨) ，牙一z k ) 0 对于任意的孟，使得f ( 牙) = 0 ，假设给定某个搜索方向呶，通过沿搜索方向如实施 某种线性搜索，产生点z k = x k + a k d k ，若 ( f ( z k ) ，x k z k ) 0 则有超平面 h k = 【z r n i ( f ( z 知) ，z z k ) = o 】 从方程组( 2 1 ) 的解集严格分离当前迭代点z 庇因此，为了加速算法的收敛，可将x k 往 该超平面上做投影，作为下一个迭代点z 七+ 。利用此思想，我们提出一个求解凸约束 1 3 河南大学硕士学位论文 的非线性单调方程组的b f g s ，为了引入我们的算法，先介绍下投影算子的定义：从 映射c 是舻上的一个非空闭凸子集： p c z 】：= 甜g r a 倒i n 炉z z 舻 ( 2 2 ) 其中，i | i i 表示2 一范数，算子的一个重要的性质是不放大性，也即， p c x 】一p c y 】| | | l z 一i i ，vz ，y 虢n ( 2 3 ) 真法2 2 1 ( b f g s 算法) 步0 选择初始点z o 舻和常数卢( 0 ，1 ) ，仃( 0 ，1 ) ，h 0 ，r20 阵b o = 弹位矩阵夕让尼：= 0 步1 解方程组 巩d k = 一f ( z 七) 计算方向d 七。 步2 ：蜾l l f ( x k ) l i = o ，然后停止 步3 确定步长如= 眇一使得m 七是最小的非负整数且m 满足 一( f ( z 七+ f f n d k ) ，d k ) a 妒l l f ( x k + m d k ) l l l l d k l l 2 令z k ：= z 七+ t k d k 步4 计算 其中 步5 计算 其中 x k + l = p c 陋七一a k f ( z k ) 一帮 选取初始矩 ( 2 4 ) ( 2 5 ) ( 2 6 ) ( 2 7 ) b k + l = 风一鬻+ 舞 仁8 ， s 南= 孙一z 詹，y k = f ( z k ) 一f ( x k ) + h l l f ( x k ) 1 1 7 8 k ( 2 9 ) 步6 当七：= k + 1 转步i 1 4 河南大学硕士学位论文 该算法具有很好的几何解释，假设是( 2 1 ) 的一个当前近似解首先用a r m i j o 型 线搜索计算不放大的过程寻找试验点，下一次迭代z 奄+ 1 的计算是通过z 七投影到这 个超平面上，其中可行域c 与超平面毗= z r n l ( f ( 钰) ，z 一张) = o ) 相交 2 3全局收敛性分析 为了证明算法2 2 1 的全局收敛性，首先给出假设： 假设2 3 1 如果f 在凸集c 上是满足l 动s 矾i 避续的，存在一个常数l o t 得 由纨的定义知 f ( x ) 一f ( y ) l i l 0 z 一可nv 正，y c h l l f ( m ) l l s r s k y t s k ( l + h l l f ( x ) l l r ) s 蚕s 七 ( 2 1 0 ) 为了证明算法2 2 1 的全局收敛性，我们引入了一些有用的引理 3 4 】 引理2 3 1 设鼠由刷嘞正公式似砂确定，假设玩是对称正定的如果存在正 的常数m m 使得对于所有的七0 ，鲰和s 七满足 繇狐襞姐 仁 因此对于任意的( o ，1 ) ，存在正常数卢1 ，励，仍和风，使得不等式 p l l l s k l l l i b 七s 知0 f i 2 l l s k l l ，风i | s 七1 1 2 8 t b k s k 良l l s k l l 2 ( 2 1 2 ) 对j 七中至少有【七k 个指标成立 对每一个，我们定义指标甄和k ，如下 冠= 1 拧+ 最后一个不等式与( 2 1 6 ) 相矛盾证毕 引理2 3 3 如果假设2 3 睇，假设2 ，嬲5 足，序列 z 七) 和 魂) 由算法2 2 j 生成，那 么 x k 和 魂) 都是有界的，则我们有 和 证明：从( 2 5 ) 我们有 。l i ml i x k z k l i = 0 詹- - - - o o 。l i ml | z 七+ 1 一z 忌0 = 0 拧- 叫 0 0 ( 2 1 7 ) ( 2 1 8 ) ( f ( 魂) ，z 七一镪) = 一轧( f ( 讯) ，d k ) 盯t 钏f ( 讯) l 如1 1 2 = o l l f ( z k ) l l l l x 知一z k l l 2 0 ( 2 1 9 ) 1 6 河南大学硕士学位论文 当牙s 通过( 2 3 ) 和( 2 6 ) ，得到 i l 。七+ 1 5 1 1 2 = i i p c ：e k o l k f ( z k ) 】一牙1 1 2 1 l z 知一c t k f ( z k ) 一牙1 1 2 = i i z 七一孟| 1 2 2 a k ( f ( z k ) ，z 七一面) + a 21 1 f ( z k ) 1 1 2 ，( 2 2 0 ) 通过f 是单调的和孟s ，满足 ( f ( z k ) ，z 七一牙) = ( f ( 魂) ，z 七一z k - - 0 ，因此 i i f ( z d i i m ，v 后1 ( 2 2 4 ) c a u c h y - s c h w a r z 不等式，f 是单调和( 2 1 9 ) ，我们有 酬耸蛰铲 、( f ( z k ) ，t , k z 南) ： i i z 七一张i l o l l f c z 七) l i i i x k 一魂i i o l l x 免一z k l l ，( 2 2 5 ) 1 7 河南大学硕士学位论文 由( 2 2 4 ) 和( 2 2 5 ) 我们得到序列 ) 也是有界的因此从( 2 2 2 ) 和( 2 2 4 ) 得 也就是 9 岳慨= z k l l 4 ( 恢一牙肛i l x k + 1 一孟喃 ， k = l k = l 。l i m 忙七一z k l i = 0 拧+ 从钆c ，由( 2 3 ) ，( 2 7 ) 和c a u c h y - s c h w a r z 不等式，我们得到 i l x k + x - - z k l l = i i p e x k - - a k f ( 张) 】一z 知i i 收敛于某个聚点撒得f ( ) ： 0 由( 2 1 6 ) j 晰y l j l z k 一划) 收敛从而， 钆) 收敛于岔 如果( i i ) 满足，又由【z 七) 是有界的和f 是连续的，存在正常数 使得 i i f ( x k ) l j ，vk ( 2 2 8 ) 1 8 河南大学硕士学位论文 从( 2 1 0 ) 和( 2 2 8 ) ，我们有 需猁，警警 由上面的不等式及引理2 3 1 ，不等式( 2 1 2 ) ，( 2 1 4 ) 和( 2 2 7 ) 对任意的七k 均成立因 而由( 2 1 4 ) 及( 2 2 6 ) 我们有 l i m i n f i i t k l l = 0 k e k ，k - - - , o o 。 对于任意k k 充分大，m 一1 不满足线搜( 2 5 ) 的条件也就是 一( f ( z 七+ 矿一1 d k ) ，d 知) 0 上面两个不等式矛盾因此，l i m i n f o ol i f ( x 七) l | 0 是不可能的证毕 2 4 数值试验结果 本节我们给出三个简单问题来测试算法2 2 1 的有效性该算法是用m a t l a b 在 在双精度下编写而成，在c p u 处理器为1 6 g h z ，r a m p 寸存# 3 5 1 2 m i c j 个人电脑上实现， 对于每个测试问题，算法终止的条件是： f ( x 七) 恪1 0 ( 2 3 0 ) 问题1 和2 的取自【3 2 】问题3 是问题2 稍加修改而得到的，取自【4 6 】 问题1 f 定义如下：f ( z ) = ( ( z ) ， ( z ) ) t ，其中 ( z ) = 矿t 一1 ，i = 1 ，n ， 和c = 眺 1 9 河南大学硕士学位论文 问题2 f 是严格单调的 f ( z ) = 00 11 11 00 ( 三 + ( ：蓁| + i - 1 凸集c 如下： 4 c = 【z 群：兢3 ，兢0 ，江1 ，4 卜 i = 1 问题3 f 是下面的定义： f ( x ) = ( ( z ) ，尼( z ) ，厶( z ) ) ? ，其中 ( z ) = 翰一s i n l x i 一1 1 ，l = 1 ，2 ，n ， 和 n c = 【z 渺i 翰几，玩0 ，i = 1 柚l t = 1 选择非光滑问题的初始点( o ，0 ，0 ) t 对于算法2 2 1 ，常用参数如下：7 = 2 ，盯= 1 0 ，和p = 0 5 表z 是关于问题1 具有 不同的维数和不同的初始点其中表中各列的意义如下： p r o b l e m ：测试问题的名称； d i m ： 测试问题的维数； i t e r ：迭代次数； t i m e ：c p u 运算时间( 秒) ； f n ： 最终函数梯度的范数； ( 1 ，1 ，1 ) t ( 2 ，2 ，2 ) t( 1 ，1 5 ，1 肪) r d i mi t e rt i m ef ni t e rt i m ef ni t e rt i m ef n 1 0 02 36 3 4 4 0 0 07 0 0 9 4 e - 0 0 680 1 4 0 0 0 0 2 8 4 5 & 0 0 630 0 4 7 0 0 03 7 3 5 6 e - 0 0 6 2 2 23 1 8 7 0 0 09 2 6 0 1 e - 0 0 633 9 5 3 0 0 0 0 0 0 0 e + 0 0 30 1 7 1 0 0 0 6 6 1 6 5 e - 0 0 7 3 0 02 1 5 2 1 8 0 0 0 0 0 0 0 e + 0 021 5 0 4 7 0 0 0 0 0 0 0 e + 0 0 30 3 4 4 0 ( ) o2 4 0 2 6 e - 7 伽 23 7 7 3 5 0 0 00 0 0 0 e + 0 02 3 7 7 9 7 0 0 0 0 0 0 0 e + 0 0 30 6 5 6 0 0 01 1 7 0 8 e - 0 0 7 5 0 027 6 7 3 5 0 0 00 0 0 0 e + 0 02 7 6 7 0 3 0 0 0 0 0 0 0 e + 0 0 31 1 7 2 0 0 06 7 0 3 1 e 0 0 8 河南大学硕士学位论文 表2 是关于问题2 具有固定的维数4 和不同的初始点 表2 关于问题2 的数值结果 表娓关于问题3 具有不同的初始点和不同的维数 表7 关于问题3 的数值结果 ( 0 ，0 ，0 ，0 ) t( 1 ，1 ，1 ，1 ) ?u n i f r n d ( o ，1 ，几，1 ) d i m i t e rt i m ef ni t e rt i m ef ni t e rt i m ef n 1 0 04 0o 8 1 2 0 0 06 7 0 8 6 e - 0 0 66 21 9 6 8 0 0 06 8 1 1 2 e 0 0 64 40 6 8 7 0 0 07 7 3 3 5 e 0 0 6 2 0 07 83 3 1 3 0 0 03 4 9 5 6 e - 0 0 63 41 5 4 1 6 0 0 06 9 7 0 0 e - 0 0 6 8 93 5 1 6 0 0 09 4 1 2 8 e 0 0 6 3 3 33 5 3 1 0 0 09 3 1 5 6 e - 0 0 63 63 9 3 7 0 0 08 2 6 5 9 e - 0 0 64 04 3 4 4 0 0 0 4 6 3 7 3 争0 0 6 4 0 03 0 6 8 5 9 0 0 08 3 4 0 4 e 0 0 63 37 4 5 3 咖4 3 6 6 2 e 0 0 63 27 3 9 0 0 0 05 5 6 3 4 e - 6 5 0 03 61 4 8 1 2 0 0 02 9 1 6 0 7 争0 6 3 01 2 5 0 0 0 0 09 4 8 2 4 e 0 0 63 61 7 3 1 3 0 0 07 0 0 1 7 e - 0 0 6 表1 壕明我们的算法对于求解凸约束的非线性单调方程组是非常好的 2 1 第三章求解凸约束的非线性单调方程组的有限记，i z b f g s 方 法及其收敛性 3 1 引言 考虑下面的约束非线性方程组问题： f ( z ) = 0 ，z c ，( 3 1 ) 其中f