一种充分下降的prp共轭梯度法的全局收敛性

《一种充分下降的prp共轭梯度法的全局收敛性》由会员分享，可在线阅读，更多相关《一种充分下降的prp共轭梯度法的全局收敛性（11页珍藏版）》请在金锄头文库上搜索。

1、2 0 1 3 年 6月 高等学 校计 算数学学 报 第 3 5卷第 2期 一种充分下降的PRP 共轭梯度法的 全局收敛性 ：Ic 李敏 屈爱平 (怀化学院数学与应用数学系， 怀化 4 1 8 0 0 8 ) THE G LoBAL CoNV ERGEN CE 0F A SUFFI CI ENT D ESCEN T PRP C0N J U GATE G RADI ENT M ETH 0D L i Mi n Qu Ai p i n g ( D e p a r t me n t o f Ma t h e ma t i c s ， H u a i Hu a U n i v e r s i t y ,

2、 H u a i H u a 4 1 8 0 0 8 ) Ab s t r a c t Y u a n d Gu a n p r o p o s e d a s u ffic i e n t d e s c e n t P R P c o n j u g a t e g r a d i e n t m e t h o d ( D P R P me t h o d ) a n d e s t a b l i s h e d t h e g lo b a l c o n v e r g e n c e b a s e d o n s o m e c o n d i t i o n s B u t

3、n o c o n v e r g e n c e r e s u l t s w e r e o b t a i n e d f o r n o n c o n v e x o b j e c t i v e f u n c t i o n s w i t h s t a n d a r d A r mi j o l i n e s e a r c h o r Wo l f e l i n e s e a r c h I n t h i s p a p e r ， a c a u t i o us DPRP me t h od i s pr o p o s e dI t i s s h o

4、we d t ha t t he pr o po s e d me t ho d i s g l o b a l l y c o n v e r g e n t i f t h e Ar mi j o l i n e s e a r c h o r t h e Wo l f e l i n e s e a r c h i s u s e d T h e n ume r i c a l r e s u l t s s h o w t ha t t he pr o p os e d m e t ho d i s e ffic i e n t Ke y wo r d s s u ffic i e n

5、 t d e s c e n t ，P R P me t h o d ，A r mi j o l i n e s e a r c h ，Wo l f e l i n e s e a r c h，g l o ba l c on v e r g e n c e A MS ( 2 0 0 0 ) s u b j e c t c l a s s i fi c a t i o n s 6 5 K 0 5 ， 9 0 C 3 0 中图法分类号02 2 4 湖南省教育厅科学基金资助项 目 ( 1 2 C0 8 4 4 ) 收稿 日期： 2 0 1 0 0 5 0 2 2 0 1 3 年 6月 高 等 学 校

6、 计 算 数 学 学 报 1 4 9 1 引 言 假设函数 ，： R 一R连续可微， 考虑下面的无约束极小化问题 mi n 厂 ( ) ，XR 设 X O 为问题 ( 1 1 ) 的解的初始近似， 非线性共扼梯度法的迭代格式为 X k + l =X k +a k d k ( 1 2 ) 其中步长 通过某种线性搜索确定， 为搜索方向， 定义如下： r d ：一 夕 ， ： 0 ； (1 3 ) 【一g k +3 k d ， 1 ， 本文 中， 我们用 g k表示 厂在 X k处的梯度 其中参数 的计算方法不同而产生不同的共 轭梯度法 著名的共轭梯度法包括： H S方法 8 j F R方法 3 P

7、 R P方法 【1 0 ， 1 1 ， C D方法 4 及 D Y方法 2 等 P R P方法是公认的数值效果最好的共轭梯度法之一， 其参数 的 计算公式如下： P ， 这里 y k 一 1 =g k g k 一 1 ， I1 表示欧氏范数 P R P方法的收敛性一直是讨论的热点问题， P o l a k和 R i b i r e 在文献 【 1 0 】 中证明了采用精确线搜索的 P R P方法求解强凸问题的全局 收敛性 但对非凸问题， P o w e ll 1 2 构造了反例表明即使采用精确线性搜索 P R P方法也不 一定收敛， 并给出了限制 R P为非负的建议 基于 P o w e l

8、l 的工作， G i l b e r t 和 N o c e d a l 5 得出， 如果雕R P 0 且搜索方向满足充分下降条件 T d 一 c llg ll。 ， 则P R P方法全局收 敛 最近有关 P R P方法的研究主要有张丽 1 3 等人提的三项 P R P方法 喻高航和关履泰 1 5 】 提出了一种充分下降的共轭梯度法， 本文中称之为 D P R P方法， 其参数 P R P的计算公式如下 ： 即 ： 一t皆， (1 4 ) 其中常数 t 1 4 喻等人给出了如下充分下降性定理 1 5 ： 定理 1 1 设迭代方向 )由下式产生： dk= 一9 + P RPd k一1 ，d 0

9、= g 0 ( 1 5 ) 若 I 一 1 ll 0 ， 则 9 ( 1 - 1 ) Ilg k ll (1 6 ) 1 5 0 李敏等： 一种充分下降的 PR P共轭梯度法的全局收敛性 第 2期 关于 D P R P方法的收敛性， 喻 【 1 5 等人得出： 如果存在常数 0 使得 O lk 0 对所有 k成立， 且步长 满足条件 f ( x k +a k d k ) 一f ( x k ) 6 a k g T d k ， ( 0 ， 1 ) 则 DP R P方法求解非凸问题全局收敛但是， 如果采用标准 Ar mi j o搜索或 Wo l f e搜索， D P R P方法的收敛性未知 采用标准

10、 A r mij o 搜索， 即计算 O L k =ma x p J ， J=0 ， 1 ， 2 ， ) 满足 A r m ij o 条件 f ( x k +a k d k ) 一f ( x k ) T ( 1 7 ) 9f ( x k+ a kdd k )T-d f( xk )夕 1 lld 一 1 【l一 (2 9 ) I-gk+ P RP dk e l s e 其中 1 0 是一个取定的正常数 这一技巧由中国学者李董辉在文献 【9 中提出， 张丽和 周伟军 1 6 成功将此技巧应用于 H a g e r 和 Z h a n g提出的 C G D E S C E N T方法 6 由定 理

11、1 1 可知， 保守 D P R P方法产生的搜索方向为下降方向， 且搜索方向满足充分下降条件 ( 1 6 ) 具体算法步骤如下： 算法( 保守 DP R P方法) S t e p 0 给定常数， E0 ， E 1 0 给出解 的初始近似 0R 置 k： =0 ； 2 0 1 3 年 6月 高 等 学 校 计 算 数 学 学 报 1 5 1 St e p 1 St e p 2 St ep 3 St e p 4 St e p 5 如果 l IIo 。 E ， 结束； 按 ( 2 9 ) 计算 ； 由A r mij o搜索或 Wo l f e 搜索确定步长 O L ； 置 X k + l = +a

12、 k d k ， 如果 l_ + 1 l_o 。 E ， 终止 置 k： = +1 ， 转 S t e p 2 3 全局收敛性 本节， 我们证明算法 2 1 的全局收敛性 若无特殊说明， 我们总假设如下假设 A成立 假设 A I 水平集 Q= f ， ( ) ， ( 0 ) ， R ) 有界 I I 在 Q的某邻域 中， ，连续可微， 且导数 L i p s c h i t z 连续， 即存在常数 L0 使得： IIg ( x ) 一g ( y ) l l L IIx 一 ll， Y x ， Y N ( 3 1 ) 由假设 A可知， 存在常数 1使得： lW ( x ) lI 0使得： ( 3

13、 4 ) 这里分两种情况证明 ( 3 4 ) 1 5 2 李敏等： 一种充分下降的 P RP共轭梯度法的全局收敛性 第 2期 情 形 i 1 由 (1 6 ) 和 c a u c h y -S ch w a rtz 不 等 式 可 得 ： ( 1 一 1 ) ll9 lld k ll， 取 c =( 1 一 1 ) 有 ( 34 ) 成立情形 i i 6 a k p 一 9 T d ( 3 5 ) 由中值定理及 L i p s c h it z 条件 ( 3 1 ) ， 必存在 0 ， 1 ， 使得 I ( x +p - 1 a k d ) 一， ( ) = p - 1 c k g ( x +

14、C k p 一 d ) T d k =p-1 9 T d +p - 1 (9 ( z + p 一 a k d k ) 一g k ) d k p - 1 a k g T d k +L p 一 2 lld lI 将上式代入 ( 3 5 ) ， 结合充分下降条件 ( 1 6 ) 可得 ( 一 ) 只 要 令 c = m in (1 一 击 ) ， ( 1 一 1 ) ) 即 有 (3 _4 ) 成 立 由 ( 1 7 ) 和假设 A， 有 一C k g T d k c s 7 按照使用 A r m o搜索时相同的方法， 可得 Z o u t e n d i j k 条件 ( 3 3 ) 成立 定理得

15、证 基于这个 引理， 我们有下面的定理 定理 3 1 设，满足假设 A ， 由算法 2 1 产生， 且步长 由A r m ij o 搜索或 Wo lf e 搜索确定， 则有对某些指标 k 有 ll II =0 或 l i n f Il l ：0 ( 3 8 ) 2 0 1 3 年 6月 高 等 学 校 计 算 数 学 学 报 1 5 3 证明反设定理的结论不成立， 即存在 0使得 II _l ， y ， V k 0 ( 3 9 ) 如果 d k= 一 g k对无穷多个指标 k成立， 由 ( 3 3 ) 可得：l i m i n f k 。 。 IIg k lf ：0 ， 这与 ( 3 9 ) 矛盾， 所以在下面的证明过程中， 我们总假设 d k=一 9 k只是对有限个指标 惫成立由 ( 1 5 ) ， ( 2 9 ) ，( 3