再开始共轭梯度法及其收敛性分析
共轭梯度法是著名的共轭方向法，它的基本思想是取当前点的负梯度方向与前面搜索方向进行共轭化，从而产生当前点的搜索方向。共轭梯度法需要较少的储存量和计算量，当问题变量的维数较多时，用这个算法求解是非常有效的。
下面给出由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-1T gk-1
步 4 确定步长，用精确线搜索法确定步长аk>0 使得
          f(xk+аkdk)= min  f(xk+аdk)
                      а≥0
步 5 计算新点 令xk+1=xk+аkdk  k=k+1 转步2 
再开始共轭梯度定义：共轭梯度法实际使用中，时常插入负梯度方向作为搜索方向作为搜索方向。对于一般非二次函数，n步以后共轭梯度法产生的搜索方向通常不具有共轭性。因此，每迭代n或n+1步后，就重新取负梯度方向作为搜索方向，这样得到的算法成为再开始共轭梯度法。
在什么情况下使用再开始共轭梯度法？
在最优解附近，目标函数与一个正定二次函数很接近。因此，当迭代点进入目标函数逼近正定二次函数的区域后，再开始方法能迅速收敛到最优解。对于大规模问题，常常每m(m<n或
m<<n)步就进行再开始。此外，当搜索方向不是下降方向时，也插入负梯度方向作为搜索方向。
一般步骤如下：
Step 1：gkT dk>0
Step 2: 如果||▽正则化共轭梯度法g(xk)||>ε
Step 3:  g(k+1)T gk/||gk||ˆ2≥0
      Step 4 直到||▽g(xk)||<ε
   

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。