（计算数学专业论文）解无约束优化的非单调信赖域法和perryshanno无记忆拟牛顿法.pdf

摘要 本文对求解无约束优化问题r a i n ，( z ) 给出三个算法：( 1 ) 不重解子问 题的非单调自适应信赖域算法( 2 ) 非单调p e r r y s h a n n o 无记忆拟牛顿方 法，( 3 ) 非单调带参数的p e r r y s h a l m o 无记忆拟牛顿法。本文主要工作如下： ( 1 ) 文 2 】给出了一种自适应信赖域算法，其调整信赖域半径的公式 是a k + l = 兄。( r k ) 0 氐m 其中嘞( t ) 称为r 一函数。我们给出一个比文【2 】简单 的新的r 一函数( t ) 并采用公式a k + 1 = 忌。( r k ) a k 调整信赖域半径。在数值试 验中我们发现当试探步呶被接受时，有时以可能是f ( w ) 的一个极好的下降方 向。取x k + l = o + 也可能并没有充分利用这个好的下降方向如，对这种情 形，我们采用一种不精确线搜索来确定z + 1 。另外当试探步出不被接受时， 我们没有重解子问题或向后线搜索，而是采用了一个固定的公式给出新的迭 代点x k + 1 。对采用上述技巧的信赖域算法，在适当条件下，我们证明了它的 全局收敛性。数值试验表明该算法是有效的。 ( 2 ) 对非单调线搜索的p e t t y s h a n n o 无记忆拟牛顿法，我们不仅证明 - f f f ( x ) 是凸函数时的全局收敛性，同时在，( z ) 是非凸函数时的收敛性也作了 深入的探讨，并给出了几个收敛的充分条件。初步的数值试验表明了算法的 有效性。 ( 3 ) 在第二个工作的基础上给出了非单调带参数的p e r r y s h a n n o 无记忆拟 牛顿算法，我们不仅证明了，( z ) 是凸函数时的全局收敛性，同时在，( z ) 是非 凸函数时的收敛性也作了深入的探讨，并给出了几个收敛的充分条件。并且 可以通过参数的选取来控制解的误差，最后给出了几个演示性的算例。 关键词：无约束最优化，信赖域方法，固定步长，非单调技术，非精 确线搜索，无记忆拟牛顿法，非凸目标函数，收敛性 a b s t r a c t i n t h i s p a p e r , w ep r o p o s et h r e em e t h o d sf o r u n c o n s t r a i n e d o p t i m i z a - t i o n ( 1 ) an e wn o n m o n o t o n i cs e l f - a d a p t i v et r u s tr e g i o na l g o r i t h mw i t h o u tr e s o l v - i n gt h es u b p r o b l e m ( 2 ) n o n m o n o t o n i cp e r r y s h a n n om e m o r y l e s sq u a s i n e w t o n m e t h o d ( 3 ) n o n m o n o t o n i cp e r r y s h a n n om e m o r y l e s sq u a s i n e w t o nm e t h o dw i t hp a - r a m e t e r t h ed i s s c r t a t i o nc a nb es u m m a r i z e da sf o l l o w s ： 1 p a p e r 【2 】p r o p o s e sas e l f - a d a p t i v et r u s tr e g i o na l g o r i t h m , a n dt h ef o r m u l ao f t r u s tr e g i o nr a d i u si sa k + l = 忌2 ( ) 0 呶m w h e r e ( t ) n a m e sr - f u n c t i o n w e p r o p o s ean e wr - f u n c t i o nw h i c hi ss i m p l e rt h a np a p e r 【2 】，a n dd e f i n eaf o r m u l a a k + l2 ( r k ) a ka st r u s tr e g i o nr a d i u s w h e na t r i a ls t e pi sa c c e p t e d , s o m e t i m e s 巩i sag o o dd e s c e n dd i r e c t i o n ，w et a k eai n e x a c tl i n es e a r c ht oo b t a i nz + 1 v h e na t r i a ls t e pi sn o ta c c e p t e d ，t h em e t h o dd o e sn o tr e s l o v et h es u b p r o b l e mb u tg e n e r a t e s ai t e r a t i v ep o i n tw h o s es t e p l e n g t hi sd e f i n e db yaf o r m u l a u n d e rm i l dc o n d i t i o n s , w e p r o v e t h a tt h ea l g o r i t h mi sg l o b a lc o n v e r g e n c e n u m e r i c a lr e s u l t sa r ep r e s e n t e dw h i c h s h o wt h a tt h em e t h o di se f f e c t i v e n u m e r i c a lr e s u l t sa r ea l s op r e s e n t e d 2 t h i sc h a p t e rw i l lt r yt od i s c u s sn o n m o n o t o n i cm e m o r y l e s sq u a s i - n e w t o n m e t h o d t h ec o n v e r g e n c eo ft h i sm e t h o di sp r o v e df o rg o n v e xf u n c t i o na n dn o n - c o n v e xf u n c t i o n p r i m a r yn u m e r i c a lr e s u l t sd e m o n s t r a t et h a tt h ea l g o r i t h mi se f f i c i e n t 3 t h ec h a p t e rt a k e sn o n m o n o t o n i cp e r r y s h a n n om e m o r y l e s sq u a s i n e w t o n m e t h o dw i t hp a r a m e t e r t h ec o n v e r g e n c eo f t h i sm e t h o di sp r o v e df o rc o n v e xf u n c t i o n a n dn o n c o n v e xf u n c t i o n p r e l i m i n a r yn u m e r i c a le x p e r i m e n t ss h o wt h a tt h ep r o p o s e d a l g o r i t h mi se f f e c t i v e k e y w o r d s u n c o n s t r a i n e do p t i m i z a t i o n ，t r u s tr e g i o n ，f i x e ds t e p l e n g t h ，n o n m o n t o n i c t e c h n i q u e ，i n e x a c tl i n es e a r c h 。m e m o r y l e s sq u a s i n e w t o nm e t h o d , n o n c o n v e xf u n e - t i o n , c o n v e r g e n c e 学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究 成果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构 已经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示 了谢意。 作者签名： 日期： 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅；有权将学位论文的内容编入有关数据库进 行检索；有权将学位论文的标题和摘要汇编出版。保密的学位论文在 解密后适用本规定。 作者签名； 日期： 时言 刖菁 1 论文背景 最优化可以追溯到十分古老的极值问题，然而，它成为一门独立的学科 是在本世纪4 0 年代末，是在1 9 4 7 年d a n t z i g 提出求解一般线性规划问题的单纯 形法后。现在，解线性规划、非线性规划以及随机规划、非光滑规划、多目 标规划、几何规划、整数规划等各种最优化问题的理论的研究发展迅速，新 方法不断出现，实际应用日益广泛。在电子计算机的推动下，最优化理论与 方法在经济计划、工程管理、交通运输等方面得到广泛应用。 本文的内容属于方法研究，在结合了几类最优化算法( 如自适应信赖域 法、非精确线搜索法、无记忆拟牛顿) 的基础上对求解无约束优化问题进行 了一定的探讨。 本节将对文中方法的研究进展作一简要介绍，最后一节介绍本文的主要 工作。 2 文中方法研究现状 信赖域方法是解最优化问题的最基本的方法之一，近年来，随着各种新 的技术不断出现，出现自适应的信赖域、非单调信赖域等方法，为问题的求 解带来更好的效果。本文第一章针对这些进展提出一个改进的算法并证明其 性质。 无记忆拟牛顿方法是t 扫p e r r y ( 1 9 7 7 ) ，s h a n n o ( 1 9 7 8 ) 首先提出的。之后，这 类方法得以进一步发展出现了多种形式的无记忆拟牛顿法。与共轭梯度法 相比，无记忆拟牛顿法在内存量及计算量上均未增加多少，但效果却要好 得多。近年来许多作者对牛顿法，梯度法，拟牛顿法引进非单调线搜索技 巧。在理论与数值方面获得较大进步。例如g n p p o ( 1 9 8 6 ) ，r a y d a n ( 1 9 9 7 ) 等。 然而，对采用非单调线搜索的无记忆拟牛顿的讨论却相对较少。本文第二章 与第三章试图对非单调p e r r y s h a n n o 无记忆拟牛顿法作些探讨。 3 本文的主要工作 本文的研究重点是求解无约束优化的信赖域法和无记忆拟牛顿法，主要 内容概述如下 翦言 ( 1 ) 信赖域方法是解最优化问题的最基本的方法之一，我们在 2 】的启示 下，借助一种新的r ，函数日，( t ) 构造了一个新的信赖域半径调整公式，同时当 信赖域中试探步被接受时，并不立即接受而是继续向前寻找一个相对更好的 点作为下一步迭代点，当信赖域半径不被接受时，采用【4 】- 【6 】中的一个固定 公式给出新的迭代点，并在适当的条件下证明了算法的收敛性数值试验表 明该方法是有效的。 ( 2 ) 随着p e r r y s h a n n o 提出无记忆拟牛顿法以来，出现了多种形式的无记 忆拟牛顿方法，但与非单调线搜索结合相对较少。本文试图对非单调线搜索 的p e r f y s h a n n o 无记忆牛顿法做些探讨。研究其性质，我们不仅给出了凸函 数收敛性，同时在适当的条件下，还给出函数非凸情况的全局收敛性。初步 的数值试验表明了算法的有效性。 ( 3 ) 在第二个工作的基础上给出了非单调带参数的p e n y - s h a n n o 无记忆拟 牛顿算法，在适当条件下证明了凸函数及非凸函数的全局收敛性。并且可以 通过参数的选取来控制解的误差，最后给出了几个演示性的算例。 第1 章小重解于问题的扑单调自适麻情赖域算法 第1 章不重解子问题的非单调自适应信赖域算法 考虑求解无约束最优化问题： 1 1 引言 瓣，( z ) 其中，( z ) 是一个二次连续可微且有下界的实值函数信赖域方法是一种迭代 方法，在每个迭代点z k ，通过解如下的子问题产生一个试探步d k ： m i n 饥( d ) = g d + l d t b k d s t l ( 1 j 1 2 ) ( 1 1 3 ) 其中鲰= v ，( z ) 是目标函数在当前点z k 处的梯度j e k 尼“为精确h e s s i a n 阵 或其近似 0 是信赖域的半径， 也是子问题( 1 1 2 ) 一( 1 1 3 ) 的一个精确或近似解，得到如后计算比率 “= 畿= 铡黼 ， 检验试探步也是否被接受，然后信赖域半径根据值调整，因为“在一定程度 上反映了二次模型机( d ) 与目标函数的近似程度对于传统的信赖域方法，信赖 域半径 在给定的比率下调整，而文【2 】的信赖域法，信赖域半径却是以 连续的比率进行调整。 本文提出了一种新的自适应信赖域方法，在【2 】的启示下构造了一个新 的r - 函数( t ) ，它比【2 】中的r 一函数简单。信赖域半径根据( t ) 的值进行调 整，并采用了非单调技术。另外，当试探步d k 被接受时，我们并不象通常信 赖域法那样接受当前点作为新的迭代点而是尝试向前继续寻找一个相对较好 的迭代点( 具体见算法1 1 ) ，当试探步如不被接受时，不再重解子问题，而是通过 个固定的公式直接得到下一个迭代点。数值试验表明，这样做大大减少了计 第l 带小重解子问题的廿尊调自遥麻佶赖域算法 算量在一定的条件下，我们证明了新算法的全局收敛性 1 2 算法及性质 定义1 设一维函数( t ) 定义在r = ( - o o ，+ o 。) ，其中q ( 0 ，1 ) ，冗 ( t ) 是r f u n c t i o n 当且仅当它满足： ( 1 ) 冗q ( t ) 在( 一。，+ o o ) 不是下降的； ( 2 ) 。当岛( 扪= f l i ，其中伍( o ，1 ) 是小常数； ( 3 ) ( t ) 1 一m ，对所有t ，7 这里，y l ( 0 ，1 一岛) 是一常数； ( 4 ) 尼7 ( 叩) = 1 + 伪，其中他( 0 ，+ o o ) 是一常数； ( 5 ) 羔焉( t ) = 尻，其中岛( 1 + 他，+ o 。) 是一常数 从定义我们很容易得到以下关于r 函数的重要性质： 定理lr 一函数( ) ( 其中叩( 0 ，1 ) ) 满足： 0 历r ，7 ( t ) 1 1 1 1 ，v te ( 一o o ，z ) 1 1 + 他焉0 ) 岛 0 ，e 0 ，0 历 1 ，0 1 + 加，0 c 1 0 ，u 1 置七= 0 ，m ( o ) = 0 步l ：计算鲰= g ( x i ) 如果l 协i i ，则终止否则计算b k 和，f 步2 ：解子问题( 1 1 2 ) - ( 1 1 3 ) 使出满足( 1 2 3 ) ( 1 2 4 ) 步3 ；i ： - 算：a r e d k ，p r e d k 和n = 参麓 步4 ：如果“ c 1 ，转步5 否则计算o k = 一；畿， 置x k + l = x k + 口k 毗，转步8 步5 ：如果，如+ d k ) f ( x k ) + i u g t d k ，置z k + l = z k + d k 转步8 否则转步6 步6 ：计算，( z k + 埘如) ，如果，( z k + w d k ) o 且尸r e d k o 故 有，f ( k ) 2a + l ；当七 e h 引理1 ，i l p ( 1 3 4 ) ，又因为靠d k 0 使得对所有的k 有l l g ( x ) l i ，那么存在一个常数，y o 有 趣袁一_ 0 ，1 ( 1 3 8 ) 3 区_ f f ! m k 定义为帆2o m _ 鬈i w h i + 1 证明：令盯= , r a ( z c 2 ) 2 “由v ，( z ) 是一致连续的知对任意z k q o ，以 0 ，1 】，i l d k l l 盯的d k 有 d 蚕 v ，( z + o k 如) 一v ，( 。) 】i i 如 | 2 ( 1 一c 2 ) e l l 也1 1 2 肛 下面用归纳法证明( 1 3 8 ) 是成立的设 = 7 - ( 1 一c 2 ) s i | 出1 1 2 ( 1 3 9 ) ，y = m i n a o m o ，阮盯，风，7 | ( 1 一c 2 ) 岛) ( 1 3 1 0 ) 当七= 0 ，由( 1 3 1 0 ) 知a o _ y m o ，即( 1 3 8 ) 对七= o 成立 假设( 1 3 8 ) 对k 也成立，因 靠递增，为证明南+ 1 时( 1 3 8 ) 成立，只需证 a 导，k = 0 ，1 ， 缸 b 一 ( 1 3 1 1 ) 当2c 2 s 寸，由+ 1 = 冠c 2 ( n ) k 知k + 1 a k 击故( 1 3 1 1 ) 成立当住 c 2 时，由a k + l = 忍。( 仇) 知+ 1 p l a 如果1 l 如0 口，则k + l 卢1 a k 卢l l l d k ( 卢1 口3 1 a m o l m k 7 m k 因而下面只需要证 c 2 ，i i d kj l 盯时( 1 3 11 ) 成立 下设i | 出| | o , r k 2 ( 1 一c 2 ) 7 e m i n k ，5 2 巩) 一( 1 一c 2 ) 7 - ( 1 一c 2 ) t e 2 m i n a k ，e 川巩| i 一女 一9 一 于是 = ( 1 一0 2 ) r e m i n a k ，2 e l l b k l f 一) ( 1 3 1 6 ) k i b k l l ( 1 一e 兕) r e m i n 1 ，2 e l i i b k f l a k 一1 ) ( 1 3 1 7 ) 若乱| | 鼠，贝u a k l l b k l i ( 1 一o z ) r e ，否则l | 鼠i i 因而由( 1 3 1 0 ) 有 a k l l b k 0 r a i n c 1 一。2 ) 丁，) 7 风( 1 3 ，1 8 ) 于是女+ 1 j i a k 1 l l b k l i 7 靠 定理2 如果假设1 和( 1 3 3 ) 满足，同时 后) 满足 这里 奴2 o m 0 使得对任意七均有| | 鳜| i e 0 当七 ，时，由( 1 1 4 ) 和( 1 2 3 ) 得到 f z ( k ) 一，( z + 1 ) 之c l 眵( o ) 一c k ( d k ) 】c l t e m i n a k ，e l l b k l l ( 1 3 2 1 ) 当k j 时，由( 1 2 4 ) 和( 1 3 4 ) 得到 五( k ) 一，( z + 1 ) “1 一脚加) 吖2 ) ( 一露d k ) ( 1 一u ) 6 2 ) 丁m 打l k ，e l t b l l ( 1 3 2 2 ) 令口= m i n c l r e ，( 1 一脚加) 6 2 ，则由( 3 2 1 ) 和( 3 2 2 ) 得到对任意都有 ，l ( ) 一，( z + 1 ) o m i n a ，i i b , , , i i ( 1 3 2 3 ) 一l o 一 | | 一i 雠 第1 争小重解子问题的+ 仆荦调自适应情赖域算挂 由引理3 知对任意七均有 m i n a k ，e “b t l u m k 其中= r a i n 7 ，e ) 由氟) 递减及( 1 3 2 3 ) 和( 1 ，3 2 4 ) 知，对s = 0 ，1 ，m 均有 ( 1 3 2 4 ) f t c k ) ( t + 曲 + a + l + o m i n a k + 6 ，b + 。i i 风5 + l + 口v 慨+ 1 3 2 5 ) 根据引理2 和 慨) 递增知 l i c k ) m 厶+ + l ：0 s m + o v l m + 外1 2五( 七+ m + 1 ) + 口l ，m k + m + 1 再根据假设1 和引理2 ，即撕( k ) ) 是单调下降且收敛的故由( 1 3 2 6 ) - 得 善忐 0 使其满足： f ( x k 4 a k d k ) 。m 巯f ( x k - s ) - i - c l 口k g t d k g ( x k + a k d k ) t d k c 2 9 蚕如 ( 2 1 2 ) ( 2 1 3 ) 其中 毛为非负整数，0 c l 0 ( 2 1 4 ) ( 2 1 5 ) 2 2 算法 采用上述非单调线搜索的非单调p e n y s h 籼。无记忆拟牛顿法具体步骤如 下： 算法2 1 ：非单调p e r r y s h a n n o 无记, 忆拟牛顿法 ； 步1 选取l ，e 0 ，0 o 使 09 ( ) 一g ( z ) i i l | jy 一名0 ，v y ，z l l ( 2 3 1 ) 引理1 设假设1 满足，记，( 勋( 砷) 2 。璺甄， 一j ) ，如果，( x k + 1 ) ，( 卸( ) ) ，k = 1 ，2 ，则，( 吼( 砷) 单调减少且 z k ) cl 1 证明：f 妇f ( x k + 1 ) ，( 却( k ) ) 知 弛删20 9 m s a x 埘of ( x k - i ) m a x ，( z t ) ，。兰；2 ，( z k 。) ，( z 一- 一胁) ) m a x ( 弛虬g m s a x 蛳f ( z k - l - j ) = m a x ，( z ) ，( z l ( k 一1 ) ) ) ，( z z ( 一1 ) ) 故，( z l ( ) ) 单调减少。鼬f ( x k ) 冬f ( z l ( k 1 ) ) 5 ，( 却( 1 ) ) = ，0 1 ) 知 。k ) cl 1 引理2 设假设1 满足，且有，( z 1 ) f ( x l ( k ) ) 一m ，p k 0 ，k = 1 ，2 则 苫。r a i n 。p k c ，卅 0 ，k = l ，2 ，可 得一 于是 ，( z + 1 ) f ( x t ( k ) ) 一p k f ( x k + 2 ) sf ( x z ( k + 1 ) ) 一p k + l f ( x l ( k ) ) 一p k + 1 ，( z 蚪胁+ 1 ) ，( z “k + 胁) ) 一p k + 脑f ( z l ( k ) ) 一m + 胁 m l ( k + m o + 1 ) ) 2 。攫，( z 胁+ 1 。) 墨：兰业2 堡垒2 ：! 翌：丕! i 兰型工塑盘鲨 ，( z ) ) 一。要撬眦墙。 在上式中依次取= 1 ，( m o4 - 1 ) + 1 ，( s 一1 ) ( m o + 1 ) + 1 苛得 于是有 m z ( ( m 1 ) + 1 ) 一m 删s 一。要儿( m o + l h ，( z f ( 2 + 1 ) + 1 ) 一，( z f ( ( + 1 ) + 1 ) s 0 2 理晚，( 胁+ 1 ) 。 ，( 。f ( s ( + 1 ) + 1 ) 一i ( z z c ( s 1 ) ( 胁+ 1 ) + 1 ) 一。兰 m ( 胁+ 1 ) 。 “孤m + 1 ) ) 一f ( x z ( 1 ) ) 一o o 。然 p k ( m o p k + 1 ) - j 0 ，若非负数列m k 满足 一1 7 一 k = 1 2 七 p 口 一 。：i 翌：兰芏羔塑生型：! 竺! ：歪坚丝翌土塑立鎏 则 l i r a s u p m k o k 一+ v o ： 证明：若l i m s u p m k = 0 则对v ( 0 ，口) ，存在k e o ，当k2 时有m k 于 k + 是对v k 2 有 硒- - 1 k k o - 1 缈( i im t ) ( i ie ) = e b b + 1 ( 讹) k _ + o 。就有矛盾： i = l i = b + ：口l i mf 垒) 2 0 + + o 。 日lt m 4 用n ( a ) 表示a 的迹，则 b l ( ) e 1 一b + i = l 业皿n ( 鼠) g k r g k g k 2 1 l 。， 垮掣 o 使 其中n = 彳藩争 证明；由( 2 。1 ，4 ) 和假设2 中( 2 3 1 ) 得 ( 1 一c 2 ) i | 龇住= ( 1 一c 2 ) 口( 一靠d k ) s 看弧 一 心 。甜 由( 2 1 2 ) 与上式可得 l | 乳险 i ( z k + 1 ) m 嫩) ) + c ，劬毋呶= m 蛐沪c 川巩hr k m 船) ) - 盟住2 记m = 掣r k 2 则 由上式和引理2 得 ，( z + 1 ) y ( z l ( k ) ) 一风 再由m = 掣r 2 和上式有 按下n - - 式定义数 吾。g r a i n 测r 2 h + o 。 显然p ( 1 ) p ( 2 ) p ( g 一1 ) p ( q ) 0 使 。里钕4 ) 2 o “鲰l i sc 3 v 七21 h = 丽- g 而d ks i i o ki i c 3 v 岛1 由上式和( 2 3 7 ) 知，对v 1 有 因此有 由引理3 知 ( k + 1 ) m o ( o ) ( + 1 ) m os h t = 1 0 + ” 一2 0 一 ( 2 ，3 7 ) ( 2 3 8 ) ( 2 3 9 ) l 一 南v 0p 一 n 。：i g勺 。一 严 龟 = 铅 国b 。h 叫 很显然( 2 3 7 ) 与( 2 3 9 ) 矛盾 下面先对，( z ) 为凸函数的情况给出算法2 1 的一个收敛性定理。x 寸f ( z ) 为 非凸函数的情况，目前我们只得到一个需附加条件的收敛性定理，并由此给 出几个收敛性充分条件( 推论) 。对非凸函数，( z ) 的收敛性定理仍需要进一 步研究。 定理1 设假设1 满足，f ( x k ) 在l 1 上二阶连续可微且为凸函数， z k 由算 法2 1 产生，则 1 i ，m i n f | fg k l i = 0 # + + 证明：由于l 1 有界，且，( 。) 在l l 上二阶连续可微，故存在 o 使 0 吼i i = i | v 2 ( x ) 临l ，v x l 1 由( 2 3 1 0 ) 及g ( 可) 一g ( z ) = 詹g ( z + t ( y z ) ) ( 可一z ) d t 得 | g ( y ) 一g ( z ) 0 ll | y z0 ，v y ，z l l( 2 3 1 1 ) 因此，引理5 的条件满足由于 鲰= 鲰+ z 一乳= j 0 1 g ( x k + t s k ) d t 钆= 丽船 及 z k ) cl i ，( ) 在l 1 上二阶连续可微且为凸函数知瓦对称半正定故 掣蜂靼刮酬 ( 2 3 1 2 ) 1 r t 一2 t ，kl l i ， i ，l ，l 5 i 纨 0 瓦。2 8 1 1 2 。，i 一 7 由( 2 2 2 ) 和( 2 3 1 2 ) 知 n ( 胁警纠1 圳肛l j 2 ， s k 而t r ( b 1 ) = t r ( i ) = 凡n ( 1 + l ) 故 t r ( 玩) n ( 1 + 工) ，七= 1 ，2 由引理4 中( 2 3 3 ) 及上式知 糕瓢( 风胁( 1 圳最h k 9 k2 1 1 3 u 3 “v 1 。 即 故 由( 2 2 1 ) 得 g th k g k 2 。h ! ，谚凰剑高 谚凰肌【志 l = 1 ( 2 3 1 3 ) ( 2 3 1 4 ) n ( ) 二( 佗2 ) 淼+ 2 i j 概s k 1 1 2 ( 2 3 1 5 ) 由( s 看讥) 2 - i l 乳i 鲰1 1 2 及上式得到 州吲，警+ z 髻= 礼髻 再由s 女= q ( 一h k g k ) 及f f y k ( 1 一c 2 ) a k 鳍月i 9 得 由( 2 3 4 ) 及上式得到 t r ( h k + 1 ) 旦1 - c 2 糕 ( 2 3 】6 ) 2 毋 。汹 七 日n 罴一 一 r 。僦 砖 。鲫 一如焉h i n 一伊 一 。谢 兰：兰韭里翌：2 ：j 竺：丕譬丝丝王墼立鎏 果1 i m i n 0g k | l 0 贝0 存在p o f f | | 仇i i “i = 1 ，2 ，由( 2 3 1 9 ) 得 - 一- p 黑】t ：( 。) * ，尼：l ，2 ， n 2 ( 1 l ) 2 l 2 1 、。“7 1 。 上式与引理5 结论矛盾故必有l i m i n f0g ki i = 0 k 一十 下面对非凸函数，( 。) 讨论算法z 1 的收敛性 定理2 设假设1 和假设2 满足， z ) 由算法2 1 产生，如果存在叩 o 使 则 垂蚓半，嘻埘， 1 i r a i n f l lg k l l - 0 k + f 2 3 ，2 0 ) 证明：设l ，i m i n fi ig k | j o 则存在p 0 使| | g k0 p ，k = 1 ，2 ，m ( 2 2 1 ) 得 e + 十o o t r ( h k + 1 ) 卟- 2 ) 龠+ z 髻 ( 2 ，引) 由( s ：妇) 2 j js j 鲰1 1 2 得到 州吲，糕+ z 镂= n 警 7 再c a s k = a k ( - - h k g k ) 及霹y k ( 1 一c 2 ) a 靠风珊得 由( 2 3 4 ) 及上式得到 t r ( 日+ 1 ) 2 ( 上如+ 1 一 n 。谢 反复应用( 2 3 2 3 ) 得 七- 4 - 1 t r ( 风+ ：) r 芝m 啦 t r ( h 1 ) 捌 其中历