再开始共轭梯度法及其收敛性分析

《再开始共轭梯度法及其收敛性分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、再开始共轭梯度法及其收敛性分析共轭梯度法是著名的共轭方向法，它的基本思想是取当前点的负梯度方向与前面搜索方向进行共轭化，从而产生当前点的搜索方向。共轭梯度法需要较少的储存量和计算量，当问题变量的维数较多时，用这个算法求解是非常有效的。下面给出由FR公式确立的具有代表性的共轭梯度法，其中g(x)=▽f(x)算法FR共轭梯度法步1选初值，给定初始点x0∈Rˆn令k=0步2检查终止条件如果gk=0,则xˆ*=xk,停止迭代步3计算搜索方向当k≥1时dk=-gk+βk-1dk-1当k=0时dk=-gk其中当k≥1时。βk-1=gkTgk/gk-1Tgk-1步4确定步长，用精确线搜索

2、法确定步长аk>0使得f(xk+аkdk)=minf(xk+аdk)а≥0步5计算新点令xk+1=xk+аkdkk=k+1转步2再开始共轭梯度定义：共轭梯度法实际使用中，时常插入负梯度方向作为搜索方向作为搜索方向。对于一般非二次函数，n步以后共轭梯度法产生的搜索方向通常不具有共轭性。因此，每迭代n或n+1步后，就重新取负梯度方向作为搜索方向，这样得到的算法成为再开始共轭梯度法。在什么情况下使用再开始共轭梯度法？在最优解附近，目标函数与一个正定二次函数很接近。因此，当迭代点进入目标函数逼近正定二次函数的区域后，再开始方法能迅速收敛到最优解。对于大规模问题，常常每m(m

3、<0Step2:如果

4、

5、▽g(xk)

6、

7、>εStep3:g(k+1)Tgk/

8、

9、gk

10、

11、ˆ2≥0Step4直到

12、

13、▽g(xk)

14、

15、<ε