（应用数学专业论文）半无限约束非线性方程系统的光滑化牛顿法.pdf

摘要 约束非线性方程广泛出现于实际应用问题中，其中典型的一类问题是带半 无限约束的非线性方程系统。至今对这类问题的研究较少，针对这种研究现状， 本文讨论半无限约束方程的数值求解，其主要内容如下： 第一章绪论部分介绍了非线性方程系统典型的数值方法，数学基础和本 文的主要工作。 第二章用光滑化牛顿型方法解带半无限约束非线性方程系统。其主要技 巧是利用积分的方法将半无限约束方程系统等价转化为有限约束的非光滑方 程系统，然后通过投影技术，建立相应的牛顿型算法，在一定的假设条件下， 本文证明了该算法的全局收敛性和局部超线性收敛性。最后用数值算例来验证 该算法的可行性。 第三章根据离散化的思想转换半无限约束方程系统为有限约束非光滑方 程系统，并采用光滑化的思想建立光滑化牛顿型算法。理论上证明了算法的全 局收敛性。最后用数值实验验证了该算法的有效性。 关键词：非线性方程组；半无限约束；牛顿法；光滑化方法；收敛性 a b s t r a c t t h e s y s t e mo fn o n l i n e a re q u a t i o n sw i t hc o n s t r a i n t sh a sb e e nw i d e l yr a i s e di n p r a c t i c a lp r o b l e m s ，at y p i c a lo fw h i c hi st h es y s t e mo fn o n l i n e a re q u a t i o n so f s e m i i n f i n i t ec o n s t r a i n t s h o w e v e r ，s of a r ，t h e r ea r ef e ww o r k sr e l a t e dt ot h i s s y s t e m a c c o r d i n gt ot h ed e v e l o p m e n to fr e s e a r c hf o rt h i st y p eo fn o n l i n e a rs y s t e m s o u ra i mi st os t u d ys o m en u m e r i c a lm e t h o d sf o rs o l v i n gt h es y s t e m t h ep r i m a r y c o n t e n t sa r ea st h ef o l l o w i n g ： i nt h ef i r s ts e c t i o n ，w em a i n l yi n t r o d u c et h et y p i c a lm e t h o d so ft h i ss y s t e mo f n o n l i n e a re q u a t i o n sa sw e l la ss o m eb a s i cn o t i o n st h a tw i l lb eu s e di nt h ef o l l o w i n g i na d d i t i o n ，t h er e s e a r c hf i n d i n g so ft h i sp a p e ra r ea l s ob r i e f l yi n t r o d u c e d i nt h es e c o n ds e c t i o n ，w eu s eas m o o t h i n gp r o j e c t e dn e w t o nm e t h o df o rs o l v i n g t h es y s t e mo fn o n l i n e a re q u a t i o n sw i t hs e m i - i n f i n i t ec o n s t r a i n t s w ee q u i v a l e n t l y r e f o r m u l a t et h e e q u a t i o n sf o rs e m i i n f i n i t e c o n s t r a i ni n t oas y s t e mo ff i n i t e c o n s t r a i n e dn o n s m o o t he q u a t i o n sb yu s i n gt h ei n t e g r a lf u n c t i o n t h e nb yt h e p e r t u r b i n gt e c h n i q u e ，w ee s t a b l i s ht h ec o r r e s p o n d i n gs m o o t h i n gn e w t o na l g o r i t h m t h eg l o b a la n dl o c a ls u p e r l i n e a rc o n v e r g e n c eo ft h i sm e t h o di sp r o v e du n d e rc e r t a i n a s s u m p t i o nc o n d i t i o n s a tl a s t ，w eu s es o m en u m e r i c a le x a m p l e st os h o wt h a tt h i s a l g o r i t h ma r ef e a s i b i l i t y i nt h et h i r ds e c t i o n ，b a s e do nd i s c r e t i z a t i o nt e c h n o l o g y , w er e f o r m u l a t et h e s y s t e me q u a t i o nw i t hs e m i - i n f i n i t ec o n s t r a i n ti n t oas y s t e mo ff i n i t ec o n s t r a i n e d n o n s m o o t he q u a t i o n s ，t h e nas m o o t h i n gf u n c t i o ni sp r e s e n t e da n dt h es m o o t h i n g n e w t o nm e t h o di s e s t a b l i s h e d t h e g l o b a lc o n v e r g e n c e o ft h em e t h o di s t h e o r e t i c a l l yp r o v e da n dt h ef e a s i b i l i t yo ft h i s m e t h o d si sa l s os h o wt h r o u g h n u m e r i c a le x p e r i m e n t s k e yw o r d s ： n o n l i n e a re q u a t i o n s ，s e m i - i n f i n i t ec o n s t r a i n t ，n e w t o nm e t h o d ， s m o o t h i n g ，c o n v e r g e n c e 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研 究所取得的研究成果。除了文中特别加以标注引用的内容外，本论 文不包含任何其他个人或集体己经发表或撰写的成果作品。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律后果由本人承担。 作者签名：日期：年月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权长沙理工大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在一一一年解密后适用本授权书。 2 、不保密回。 ( 请在以上相应方框内打“4 ”) 作者签名：肖影旌、日期p 印占年，月y b 导师签名：奄1 0 酶 日期：弦“年r 月 - 日 j 第一章绪言 非线性方程系统的一般形式为： f - 0 x x c r ” ( 1 1 ) 其中f ：r 4 一r 4 。若f 是连续可导的，则称( 1 1 ) 为光滑方程系统，否则 称为非光滑方程系统。若x r 4 ，则称( 1 1 ) 为无约束方程系统，否则称为 约束方程系统。约束集合的一般形式为： x i 扛e r “l g o ，v ) s 0 ， ，q ) ( 1 2 ) 特别地，若q 中有有限个元素，则称( 1 1 ) 为有限约束方程系统。若q 中含有 无限个元素，称( 1 1 ) 为半无限约束方程系统。 非线性方程( 1 1 ) 广泛出现于实际应用问题中。如何构造有效的数值方法是 广大计算工作者和实际应用工作者所关注的问题。迄今已发展了许多行之有效 的数值方法，如：牛顿法，拟牛顿法，共栀梯度法，同伦法等( 见【1 】【2 】【3 儿4 】) 1 1 无约束光滑非线性方程组的牛顿法 考虑如f 方程形式： f o ) i 0( 1 3 ) 其中f ：r ”一彤设为连续可微。求解( 1 3 ) 经典的数值方法是牛顿法，其主要计 算思路为：在当前迭代点处，由下面的计算式子得到下一个迭代点矿“： 石“1 - 并一f 协) 4 f 0 ，)( 1 4 ) 牛顿计算式( 1 4 ) 最显著的特性表现在其收敛性，按( 1 4 ) 的计算式，有如下的收 敛定理： 定理1 1 1 5 】( 超线性收敛定理和二次收敛定理) 假设f ：d c r 4 一彤在z 的开邻域品c d 上f 可导且f u ) 非奇异，x 是方 程f o ) 0 的解，则存在闭球s 一弘，6 ) c s o ( 6 ，o ) ，使得映象 g ( x ) 一x - - 【，协) 】1 | f ) 对所有x e s 有定义，且由牛顿法( ，“- - x 一i f ) 】_ l f ( 矿) ) 生成的序列 矿) 超线性收敛到x 。 若还假定 0 f u ) 一f 协) l k c t l l z x 0 ，vx e s 其中口，0 为常数，则牛顿迭代序列 矿) 至少2 阶收敛。 至今牛顿法仍是求解非线性方程组有效的方法，其收敛条件在近段有了一 些突破性的进展，典型的工作有y a m a s h i t a f u k u s h i m a 6 的工作，该文降低 了j a e o b i a 阵的非奇异性条件，在误差界的条件下，证明了算法的超线性收敛 性结果。t o n g q ic 7 把y a m a s h i t a - f u k u s h i m a 的收敛性结论推广到了带界约束 的非线性方程组信赖域的求解上。在误差界的条件下证明了算法的超线性收敛 性。 求解方程( 1 1 ) 的拟牛顿型法也有很好的进展，如：李董辉 2 用b f g s 方法 解优化问题的k k t 系统，证明了该法的全局收敛性。此外l i y a m a s h i t a - - f u k u s h i m a 3 】用拟牛顿型方法解半光滑方程( v i p ，n c p ，m c p ) ，并证明了它 具有全局收敛性。 1 2 半光滑及光滑化牛顿法 实际应用中所提出的非线性方程组可能不满足f 光滑性的条件，典型的问 题有；分片线性函数，m a x 函数( e 0 ) - m a x o ， ) ) f 一1 ，2 ，n ，其中 g o ) - r ”一只连续可微的) ；非线性互补函数： a 0 , b 2 0a n d a r b - 0营 42 + 6 2 一a + 6 ) _ 0 等，此时，传统的牛顿法( 1 4 ) 不能直接用于求解非线性方程组，1 9 9 2 年 h a n p a n g 8 建立了如下数值方法： 卜“1 - 矿+ d t i f ( x ) + ，o ；d t ) 1 0 其中f ；畋) 为f 在点工处沿d 。方向的导数。由于d 。的求解工作仍需解非 9 线性方程系统，理论上虽然可以得到类似于牛顿法的收敛性结论，但实际求解 仍存在计算上的困难。 关于非光滑方程系统的求解，突破性的工作是o i s u n 在1 9 9 3 年提出的半 光滑牛顿法( s e m i s m o o t hn e w t o nm e t h o d ) ，其计算公式为： 2 i x “一茗一p _ 1 f o ) k a m f ( x k ) ( 1 5 ) 其中a b f ( x ) 为，在的广义导数。q i 证明了若f 0 ) 在解工处为强b d 正则 且为半光滑函数时，半光滑牛顿法具有局部的超线性收敛性( 见文章【9 】) ，同时 【9 】通过效益函数将局部半光滑牛顿法全局化，从而证明了半光滑牛顿法的全 局收敛性在q i 提出的半光滑牛顿法的基础上，各类相应问题得到很好的解 决，如：半光滑牛顿法解非线性互补问题( n c p ) 和m c p 问题( 见 5 i 1 0 1 1 1 1 ) ； 半光滑牛顿法解带半无限优化问题( 见【1 2 】) ；以及应用于交叉学科如电力系统 中的最优潮流问题1 1 3 1 。大量的实际计算表明半光滑牛顿法具有与光滑牛顿法 相似的计算效果。 由于半光滑牛顿法需要计算广义导数，该导数是一个集合，仍存在计算上 的困难，因此在半光滑牛顿法的基础上人们又发展了光滑化牛顿法。 考虑非光滑函数f o ) ，用光滑参数t 构建f ( x ) 的光滑化函数f o ，d ，使其满 足： 姆f ( f ，工) _ f o ) 则求解非线性方程f ( x ) 一o 的问题转化为逐步求解f ( t ，x ) 0 的问题。典型的光 滑化方法有两类：其一是1 9 9 8 年c h e r t q i s u n 在【1 1 】中的工作，该文将光滑参 数t 作为调整参数，在每一步计算中利用合适的调整方法将t 逐步减小到0 。在 j a c o b i a n 相容性条件下，该文理论上证明了光滑化牛顿法的全局和局部超线性 收敛性。其二是2 0 0 0 年o i s u n z h o u 在 1 4 中的工作，该文将t 作为变量，其 求解的方程系统为： g ( f ，x ，- ( f 毒，j ，) - 。 c 1 6 ， 该方法的优点在于无需确定t 的调整方式，视( f ，x ) 为联合变量整体求解，建立 了对应问题的牛顿型算法。在常规条件下证明了算法的全局收敛性。 1 3 非线性约束方程 实际问题所提出的非线性方程系统的变量通常受到一定的限制，因此需考 虑非线性的约束方程系统。有限约束非线性方程系统的一股形式为： 3 f f 一0 i g 。 ) s 0 f - 1 , 2 , - - 删 特别的一类约束方程系统为界约束， 即： f f ( 功- 0 l zs 工墨u 事实上，一般的约束方程系统( 1 7 ) 可通过引入松弛变量转化为( 1 8 ) ， 多的研究工作是讨论f 1 8 1 的数值方法。 ( 1 7 ) ( 1 8 ) 因此相当 s u n w o m e r s t e y o i 【1 5 】提出了可行域的半光滑牛顿法解m c p ，该方法克 服了投影牛顿法的解的非全局收敛性，并证明了该算法的全局收敛性和局部超 线性收敛性。k a n z o w 1 6 采用了有效集的方法求解带界约束的非线性方程系 统，并证明了该算法的收敛性。u l b r i c h 1 7 提出了解半光滑界约束方程的信 赖域法，并证明了该算法的全局收敛性和局部超线性收敛性。q i t o n g - l i 【1 8 】 采用了投影有效集的信赖域方法求解带界约束的非线性方程系统。 b e l l a v i a m a c c o n i m o r i n i 【1 9 】提出了仿射信赖域法解光滑界约束方程系统。 t o n g - z h o u 【2 0 】利用光滑化的投影牛顿型方法解半光滑的方程系统，并证明了 该算法的收敛性。 这些方法提供了求解有限约束非线性方程( 光滑或半光滑方程组) 有效的 数值方法。 1 4 本文的工作 本文考察带半无限约束的非线性方程： 脞攀。 (1-9)0 l g ，v ) s v e q 、7 其中映射f ：r 4 一r 4 至少为半光滑的，f ( x ) = 【 ) ，2 0 ) ，l ( x ) 】7 ”g ：r ”r ”一r 为连续可微，“q c r m 为紧集。由于q 中可包含无限个元素，类一。“ 似于半无限优化的概念，我们称( 1 9 ) 为半无限约束方程系统。特别地，当q 为 空集时，系统( 1 9 ) 退化为无约束方程系统；当q 为有限集时。系统( 1 9 ) 退化为 有限约束方程系统。因此( 1 9 ) 是( 1 1 ) - ( 1 3 ) 的一般化。 半无限约束非线性方程系统来源于实际的工程计算和应用问题中，如：物 4 体机械压力计算，电力系统中的动态规划，近似理论，最优控制，特征值计算 等，其典型的有半无限优化的k k t 系统 2 1 1 ，【2 2 1 。然而，不论数学上还是实 际应用上对这类问题数值方法的研究成果较少。 本文主要的目的是建立求解( 1 9 ) 有效的数值方法，并从理论上和数值计算 上证明方法的可行性。我们建立求解( 1 9 ) 的两类迭代方法，其具体工作如下； 1 根据积分函数等价转化( 1 9 ) 为有限约束半光滑方程系统，建立光滑化 牛顿型算法。理论上完成算法的全局收敛性和局部超线性收敛性，数值实验验 证算法的有效性。 2 根据离散化的思想转换无限约束方程系统( 1 9 ) 为有限约束方程系统， 对每个有限约束方程系统采用光滑化的思想，建立光滑化牛顿型算法。理论上 证明了算法的全局收敛性。数值实验验证了该算法的可行性。 1 5 基础知识 本节介绍文中所需的一些基本的数学概念和结论( 见 2 3 1 1 2 8 1 ) 。 定义1 称f ( d ：彤一在x 点沿方向 ，月“的导数存在，若对任给的v e r 。 有： f ，o ；，) 。l i m 塑幽竺塑 定义2 设，( d ：d c r ”一掣是局部l i p s c h i t z i a n 连续函数。称f 0 ) 为b 可 导的，若满足： a 。f o ) 1 l i r a v f ( 矿) ，o o ；o 。 其中d ，表示f ) 是可微的点集。， ) 的c l a r k e 广义导数定义为： a c f ( 功一c o n y # b f o ) 其中c o n y 表示凸包。 由上广义导数的定义知其广义导数为一个集合，若函数为可微的，则该集合只 包含一点，即常规的光滑函数的导数的定义。 定理2 如果函数f ( x ) ：r r 是满足局部l i p s c h t i z 条件，且l i p s c h t i z 常 数为k ，则在任意工点处有： ( a ) f o ；v ) 一m a x 亭7 v l 亭a 。f ) ，v p r “ ( b ) a ，7 0 ) 一偕r “i ，o ) 苫亭7 v ，v v e r l ) 5 ( c ) a 。f ( d 是个凸的，非空，紧的，且满足l i p s c h t i z 条件的有界集。 定义3 若f ：r 1 一r 4 在x e r “对vh 尺4 l i r a 锄， 0 6 矿“) “，i o 存在。称f 为半光滑函数。 半光滑函数是界于l i p s c h i t z 连续与光滑函数( 连续可微) 之间的函数， 它包括了相当一部分的函数，如：可微函数，凸函数，投影函数，分片光滑函 数，m a x 函数等。 引理1 若f ：r 4 一r 4 为局部l i p s c h i t z 函数且在x 处为半光滑的，则对 坳一0 , q e o f 0 + | 1 1 ) 有： f + | 1 1 ) 一f ( 】哆一q h - o ( i i hl d 若f 在z 处对v q 咿o + _ 1 1 ) 和h o 有： f ( x + | 1 ) 一f 0 0 一q h o ( i i h l l 2 ) 则称，为强半光滑。 定义4 若v v e o f ) 非奇异，则称f 在x 处b d 正则。 本文的工作主要是用光滑化的技术，由此我们给出光滑化函数的相关概念 和特殊的光滑化函数的构造。 定义5 若g g ) 在r 4 上为l i p s c h i t z 连续函数，酏，算) ：r x 科一只4 满足下面 三个条件，则称酏，石) 为g ( x ) 的光滑化函数，即： ( a ) 烈o 功i g ( x ) 。 ( b ) v t 0 ，虿o ，工) 在x e d 处为连续可微的； ( c l ，矗是享( f ，z ) 。g o ) 本文的工作中涉及到两类光滑化函数，以下分别介绍这两类典型的光滑化 函数及其性质( 见 8 1 4 1 1 2 1 2 4 ) 。 一【g ，v ) 】+ 的光滑化函数 。 。一1 ，+ ”p m ，设g ( x ，d ：r “x r “一r 上的连续可微函数，【g ，l ，) 】+ 一m a x 0 ，g ( x ，v ) ) 的光滑 化函数取为g l ( t ，五v ) ：r 掣x r ”一r 瓢小压学 ( 1 1 0 ) 6 由文献1 1 4 1 1 2 1 1 可知磊( f ，工，d 有如下性质： 引理2 由( 1 1 0 ) 定义的光滑化函数蟊( f ，x ，有如下性质： ( a ) 对于任给t ) 0 ，蚕( f ，x ，1 ，) 为二次连续可微函数； ( b ) 若t 0 ，爵o ，工，1 ，) 为半光滑函数： ( c ) 存在常数，0 使得对于任给t ，0 满足： i l 磊o ，工，v ) - g ( x ，v ) 0 s 二m a x 函数的光滑化函数 设g ( x ，v ) ：r ”r “一r 上的连续可微函数，对于任给t 毫0 ，定义 g 。 ， ，) = m a x j e ，g ，0 ，v ) 其中，。仉2 ， 的光滑化函数为 9 2 ( f ，石，v ) ：r x r 4 x r 4 一r ( 见文献【1 4 儿2 4 】) ： 蔹。，x ，v ，= h c 荟x , v e ) 旬p ”v 雪t t = 。o 。1 1 ， 当 ” 下面引理给出藐( f ，毛，) 的一些性质： 引理3 由( 1 1 1 ) 定义的光滑化函数磊( f ，工，v ) 有如下性质： ( a ) 对于f 0 ，豇o ，x ，1 ，) 为递增函数，且满足： o 磊o ，工， ，) 一g 。 ，) 薯t l n n ； ( b ) 对于任给t 0 ，g 一2 0 ，x ，) 为光滑函数； 下面给出积分的定义和性质： 定义5 称g o ) ：彤一r 为【g ( x ，v ) 】+ 的积分函数为： g o ) 。正【岳 ，v ) 】+ p ( v ) 咖 其中a + _ m a x ( o ，a ，v v e o ，p ( v ) 2 0 。 设g o ) 对应的光滑化函数为 g ( f ，z ) 正磊( f ，x ，v ) p ( v ) d v 在本文中，我们取密度函数p ( 力一1 特别地，当t - 0 函数g ( t ，曲对于变量x 的导数有 7 v g ( t ，功正e 季p ，x ，v ) 咖 下面命题给出g 的一些性质： 命题1 函数g ( t ，x ) 有如下性质： ( 1 ) 对t o ，c ( t ，功对x 是二次连续可微的。 ( 2 ) | c 0 ，使得对v x e r 4 有i i o ( t ，力- g ( x ) n c i t i 。 ( 3 ) 函数g ( t ，力对联合变量( f ，d 为半光滑的。 本文的结构如下：第二章讨论基于积分方法的光滑化牛顿型算法，通过适 当的转换来求解( 1 9 ) 的等价约束方程，理论上证明该算法的全局收敛性和局部 的超线性收敛性。最后用数值算例验证了该算法的有效性。第三章讨论基于离 散方法解半无限约束的方程( 1 9 ) ，并证明该算法的全局收敛性。最后用数值算 例验证了该算法的可行性。最后部分给出结论。 8 本文引入一些在文中用到的数学记号： m i x ) v 中0 ) m a x 缸，甜 m i n ( a ，声 i i i i o p ) d ( 盯) 兀矸，0 r + 中 ) 在z 点的雅可比矩阵 m o ) 在z 点雅可比矩阵转置 取a ，卢中最大的一个 取口，口中最小的一个 欧氏空间的模 同阶无穷小 高阶无穷小 在上的正交投影 大于0 的实数 露 第k 次投影梯度方向 妒 a r g f 0 ) 9 第k 次投影牛顿方向 空集 函数值为，0 ) 的x 的集合 第二章基于积分方法的光滑化牛顿法 本章讨论如下带半无限约束的非线性方程系统： f f g ( 嘉x 兰0 一 亿- ， l，v ) s v q ”一7 此处q 可取为q = v e r i a s ，s 埘。本章的主要思想是基于积分方法建立求解半 无限约束方程( 2 1 ) 的光滑化牛顿法 令：g o ) 。正【g 似v ) 】+ d v 其中【g o ，v ) 】+ - m a x o ，g ( x ，v ) 。 由s ( x ，v ) s 0 ，v e q 等价于条件g 0 ) 一0 。进一步为了计算的容易实现，添加 松弛变量y 0 ，不等式约束可转化为： f g + y 一0 b 皂。 则原方程转化为： - 0 g + y 。o 1 ) ，2 0 由于g ( x ) 是非光滑的，根据第一章光滑化函数及文章 2 0 的光滑化技术，定 义， ) 的光滑化函数为f f ( t ，工) ，【9 0 ，v ) l + 光滑化函数为： 手( f ，x ， ，) x g ( x , v ) 2 + _ 4 t 2 + g 一( x , v ) 令 矶，工) - 正虿v 沙 则( 2 1 ) 的光滑化方程系统为： i f 堪，砖一0 6 ( t ，工) + y ；0 ( 2 2 ) i y 2 0 , t 2 0 第一章命题1 已说明了该光滑函数的一牡性质。 2 1 光滑化投影n e w t o n 型方法 本节将给出光滑化牛顿型算法和它的可行性分析根据 2 1 3 的光滑化思 1 0 想，将t 阼为变量，则( 2 2 ) 等价于求解如下界约束方程系统： 嗽训，( 意y 卜 亿。， 明显地，若( f ，工，v ) 为( 2 3 ) 的解，则它为原问题( 2 1 ) 的解。 类似于 2 0 中的证明可得到如下结论： 命题2 1 1 2 0 当t o 时，中在( f ，工，y ) 为光滑的，当t - 0 时巾在( 0 ，x ，力为 半光滑的。 令集合彤- w l w - ( f ，z ) - ( f ，膏，y ) ，) ，- o ，定义( 2 3 ) 的效益函数： 平( 叻= 妻0 中( 叻2 则解( 2 3 ) 等价予求下面优化问题的全局解。 m i n 掣( 曲 s t y 苫0 ( 2 4 ) 由优化理论可知，为( 2 4 ) 的解，则其满足如下条件： l l d g 忙0 其中 瓦- 1 1 w ( w r y e ( w ) ) 。( i 嬲州帅) ) ( 2 5 ) 其中y 为常数，n ，0 关于矽的正交投影。 根据该光滑化方法的要求在算法的设计过程中需确保t 之0 。如下参数 展) 的选 择是保证计算过程中t 之0 的关键技术。 令口e ( o ，1 ) 为常数，且对于序列 _ l 乙，定义 成) 如下： ，。卢。= 卢( 匕2 ：口唑 1 ，l i 弦o “一。； _ 一# ， “ 。”。” & - f l ( w * ) - 岫, a k _ , a m 刺i n 1 , l 旷r o 舞删硼m 4 像e ， 求解( 2 3 ) 的算法如下： 算法2 1 1 1 步0 ( 初始化) 选择参数r ，盯( o 舢，p 2 ，口 o ，a f 0 ，矿- ( f ，z ) e w 不是( 2 4 ) 稳定点，则 w ( w t 癣s 一生盟i l 稚：c 0 ( 2 8 ) 证明： 为简单起见证明中去掉迭代指标k ，对于任何w 一“，z ) e w 。t ，0 设w 不是( 2 4 ) 稳定点，则： 一一冀譬呲端h 粥卜 其中v ，面( w ) 为孵( w ) 的第一行，由于 孑：( ：荔；：) 一。n - y ：。( z t + v 要h ( 掣w 。) 宝h 蠹( w 一) 彳) + a 卢w ) o + v ，承w ) 厅( 叻7 ) 卜r ( t + v ，承w ) 厅( w ) ) + 卢( w 矿1 一一yht + v 。后r ( w 茸( w ) 8 2 + o + v ，厅( w ) 露- ( w ) ) 芦( w ) i 一i l l r v ，掣( w ) 0 2 + i l l 一万，1 l ，( w ) i i ，( 箩 ( 2 9 ) ： ! 、 s 一三8 一厣，v ( 叻1 1 2 + i l l 一刃，1 l | ( 叻0 万无i i yy 量一i ，l l 一，掣( w ) 1 1 2 + 面吉瓦1 1 2 这里第二个不等式由引理2 i 2 得，最后一个不等式由u 一刃，1 l r ( w ) l l 硼瓦l l v ：1 l ，( ，) r 【h ：q 一：掣( w ) ) 一z 】 一一三【：一：1 l ，( w ) 一z 】r 【：( z - r v ：v ( ，) ) z 】 ( 2 1 0 ) r - 争：。一，巳掣) ) 一。一：掣( w ) ) 】【i f 。一：掣( w ) ) 卜i rl l 也。一；平( ，”吒1 1 2 一三l l n ：【z 一刃：v ( w ) ) - z i l 2 r 上式推导中第一个和第二个等式由引理2 1 1 得到，由( 2 9 ) 和( 2 1 0 ) 成立由 上两式的推导可得： w ( w ) 7 孑 ( f + v ，厅( 叻厅( ，) ) 卜r q + v ，订( 曲面( ，) ) + 芦( w ) 习+ v 。掣( w ) 7 】 + v ：v ( 叻7i l n ：( z 一心；掣( w ) ) 一z l d - 一三( 1 一奶瓦u 2 r 下面定理证明了算法2 1 的有效性 定理2 1 5 假设五，o 矿一p ，z 2 ) e w 不是( 2 4 ) 稳定点，则存在常数 a ( 叫，使得对w e ( o , z 】，扩为下降方向，且满足： 掣( 矿+ 矩。) l l ，( w ) + a 面叩( 矿穷 ( 2 1 1 ) 证明：由于f 0 ，矿- ( f ，z ) 矿不是( 2 4 ) 的稳定点，则掣与中为连续可 微函数。1 王，( w + 灯) 在w 点泰勒展开有： 掣( w + a 孑) 。i ，( 矿) + v 甲( h ，) 孑+ o ( 1 l 孑l d ( 2 1 2 ) 当矛五时，由命题2 1 4 得则( 矿谚c o ， 则矿为下降方向。对于0 盯 w ( w 穷 ( 2 1 3 ) 由( 2 1 2 ) 和( 2 1 3 ) 得j a ( o 朋，使得对v a ( o ，】有( 2 1 2 ) 成立。 当矛- 瓦时，由w ( 矿万一p i l 中( ) i i ，和v 平( 矿归墨一p i i m ( ) i v ，且w 为 非稳定点，所以有w ( 矿穷c 0 ，则五为下降方向由于0 t o r t l ，则 o v q ( w 谚 v l l ，( 穷 ( 2 1 4 ) 由( 2 1 2 ) 和( 2 1 4 ) 得j 旯t ( 叫，对v a ( 0 ，刀】可得( 2 1 1 ) 成立。 2 2 收敛性分析 本节将分析算法2 i 的全局收敛性和局部超线性收敛性。光滑化方法迭代 过程中保持t ，0 是至关重要的，它关系到算法可否继续进行下去。下面的结论 说明了算法保持t 非负性的要求： 引理2 2 1 对于每个七。k o j 2 ，由算法2 1 产生的序列p 满足 t 。尻f ( 2 1 5 ) 若矿不是( 2 5 ) 稳定点，则有 t 0( 2 1 6 ) 证明：用数学归纳法证明，算法2 i 中对于f o 和风的选择可知( 2 1 5 ) 和 ( 2 1 6 ) 成立。假设第1 次迭代，t o ，x l , y 。) ，满足( 2 1 5 ) 式。现证 “- o “1 ，x y ) 成立。由算法计算过程中搜索方向的确定，分两种情况证明 结论。 情况一当扩- 瓦时 五愀) 。g ：) ，- 一n o ，+ v ，f f ( w 。) 露( w 。) + 声( 。) d 一一y f 【f + v ，厅( - ) 厅( w ) + 卢( w ) 刁 - t 。+ 声( 矿 则有： r m 一芦 ) t - 一t + 汜) 卢( w “1 ) t - ( 1 一 y 7 + a , k w ) t - 卢( w “1 ) t - - ( 1 一 弦。一( 1 一 ) p ( w 。f 。o - a , x t 一芦( ，7 ) d 0 由于假设第，步成立，故有t - p ( w ) t - o ，因此f l & k t o 情况二若矛- 瓦，噼) ，- 一t 7 + ，( ，矿，则对于f + 1 次迭代有： t + 1 - 3 ( w 。“v f + ( 露) ( w y o - a , y + 卢( w 7 箩一p ( w “1 f ( 1 一 y 。一( 1 一 ) 卢( ，7 箩 一( 1 一 一卢( w 。) d 乏0 由假设，步成立，则上式成立。由此得( 2 1 5 ) 。 ( 2 1 s ) 加上矿不是( 2 4 ) 的稳定点，隐含着展f 0 ，由此推导出( 2 1 6 ) 成立。 证毕。 定理2 2 2 若序列 矿 由算法2 1 产生，则它的任何一个聚点是( 2 4 ) 的稳定点。 证明：由引理2 2 1 知，若不为( 2 。5 ) 的稳定点，则对妇，有f 0 ，由 此知甲和中连续可微。假设 k 为矿的子列且收敛于非稳定点帚。现证孑有 界，且 l i m s u p 刚( w i ) r 矛0( 2 1 7 ) k 丘k 情况一若矛- 瓦，有 x a p ( w 弦一p0 矛i i ， 和 w ( w ) 孑一pi im ( w ) l l ， 对所有的k k ，由柯西不等式得： l l 孑毒l i p 。i l ，9 7 掣( w ) 0 ，。 ( 2 1 8 ) ( 2 1 9 ) 以及露l is l i d ：l i ，由算法2 i 中d ：的计算知 n d 嘉l i sr 。i i v v ( w ) + 风万8 ( 2 2 0 ) 即刃有界：另一方面由 矿k 一万和函数的连续性知； l i m s u p i i m ( 矿) | i 害| l m ( 回 由于w 不是( 2 4 ) 的稳定点，则由( 2 1 9 ) 以及8 中( 回肛。可得 l i m s u p 舛( 矿) 7 口- - k 一p 中( 回l r s 0 七j k 情况二当矛- 瓦，由算法2 i 的既的计算知： i i d ；忙hi i v 平( w ) + 卢。万8 又由l l 露训d ：8 知 忍 有界，进一步，w 为非稳定点和命题2 1 4 得： l i r a s u pv 掣( 矿) 7 矿量0 七- 。c _ k 由此证明了无有界和( 2 1 7 ) 。又由算法2 i 中的( 2 7 ) 和v ( w ) 单调递减且有 界性有： l l ，( w + p ”玉) 一w ( w ) 一0 可得p “v q ( w ) 瓦一o ， 现只须证p ”不趋近于0 ，可以推出w 穷一。 设当研一m 时p “一o ，由p ”的定义知； 型鼍芦 一( 啦 若矛_ 孑- o ，取上式埘_ ，七_ 。孽：。一r n + “一 一 。一一 v v ( 刃d o v v ( 列 得w ( 面弦，o ，这样与v 掣( 归。一0 矛盾。故p “不趋近于0 ，则有 v 掣( ) 孑- - - - 0 ，这与( 2 1 7 ) 矛盾，所以谚为稳定点。 下面我们将分析算法2 1 局部超线性收敛性。 假设1w - o + ，：) 一( 0 ，z + ) 为w 2 的极限点，由算法2 1 产生的 矿) 满足 1 7 1 i n l 麒w i w w + 为方程( 2 4 ) 的解，且中在w 处为b d 正则的。 引理2 2 3 存在正常数l 和s ，对于任给的，满足w w 墨s ，则有： 1 )垂1 w ) 为非奇异且满足0 巾x 们4 帖j 已 l 2 )u 中( 叻i i = 2 v ( w ) ：- o ( 0 w - - w 1 1 ) 证明：由于m 在，处为b d 正则，则由x w ) 非奇异，且存在正常数口使得： i l 中1 w ) 。1 s 口 又由m ( 忉为半光滑函数，则存在正常数芦使得： i i m ( w ) 一中( ，) l k 卢i l w 一矿0 s 卢s 取g 充分小使得肚c 1 ，由摄动引理 1 可得：中k 们为非奇异且i l 由( 叻4 l i 有界即存在常数l 使得m l w ) “i b l 。 结论2 可由西( w ) 满足l i p s c h i t z 连续和v ( 叻一妄m ( w ) 2l 直接得到。 引理2 2 4 对于所有充分大的k k ： 1 ) ( ，) 一口( v ( w ) ) - o ( i l w 。一w 1 1 2 ) 2 ) w + d ：一w 。+ o ( l ，( w ) ) 证明：根据p ( w ) 的定义和九的选择，以及由投影性质和引理2 2 3 ，对 w 充分靠近w 时有： ( 矿) s a0 露i f s 口删- t k v , 1 = v ( w ) 1 1 2 + t i ：( z - y , v ：掣( 叻) 一：h 2 】 - a l l l n1 1 2 l l v 。掣( 们旷+ 0 圪1 1 2 1 1 v ：v ( w ) ) 1 1 2 】 口h 2 i i w ( w ) 1 1 2 s a 叼v ( 矿) 。竿h m ( ) 1 1 2 - o ( 1 1 w 一w 1 1 2 ) 下面证明结论2 ) 。 w + 砧 _ w + ( 中( w ) ) - 1 ( 一垂( w ) + 声w - ) - w 一西( w ) 1 【中( w ) 一中( w ) 一m ( w x w 一w ) 】一 ( w - - w ) + 垂( w ) 。1 卢( w ) 万 一w 。+ o ( i iw 一w l d + 口( 平( w ) ) l - w + d ( 1 i ( p ) 2 ) 引理2 2 5 对充分大t k 以及 且 i 西- 一( 矿一w ) + o ( i p ( w ) i ) w p ( w i 瑶s 一，腰( w ) ，p ( o 2 ) v l ( ，) 露- 一2 掣( ) + d ( 1 p ( ，) ) 证明：由引理2 2 4 和投影性质有 刃一n ，( w + ) 一 - i i ( w 一( l ，( w ) ) - 1 ( 一西( w ) + 芦刃一w l - h ( 妒一d ( v ( w ) ) i n l rw ) 一坩 ! - 一( ，一 ，) + 口( 1 l ( p ) 2 ) l 最后一个等式由于w + t p ( w 1 i 那么有 w p ( w ) 刃 - 一垂( w 弘似。) 一w ) + d 呷 ) ) - - 2 掣( w ) + m ( w ) 【m ( w ) 一中( w ) 一中( w ) ( w 一，) 】+ d ( 1 l r ( w ) ) 一( w ) 当w 一w 时v 掣) 刃- 一2 l l r ( w ) + d ( v ( ) ) 。 下面给出局部超线性的收敛性质： 定理2 2 。3 假设 ) 是由算法2 1 产生的w 为稳定点，满足假设1 ， 且中在点b d 正则，则 矿 超线性收敛于， 证明：首先证明由算法产生的序列 当七充分大时，下降方向为牛顿 方向，即： v v ( 矿) 露一p m a x i i 刃n 0