非线性共轭梯度法

非线性共轭梯度法的基础是有效地运用线性共轭梯度法,其中残差被梯度取代. 因为从未产生明确的二次函数模型,所以它总是和 线搜索 方法结合起来使用.

第一种非线性共轭梯度法由 Fletcher 和 Reeves 提出的. 给定一个步骤方向 ,然后使用线搜索方法找到 使得 . 然后计算

至关重要的一点是用以选择 的线搜索满足强 Wolfe 条件; 这是确保方向 是下降方向所必要的 [NW99]].     

另一种通常(但并不总是)在实践中表现更好的方法是由Polak和Ribiere提出的,其中方程(2)由如下式子替代

在方程式(3)中, 有可能变成负的,在这种情况下,Wolfram 语言使用由 修改的算法. 在 Wolfram 语言中,默认的共轭梯度法是Polak-Ribere方法,但是也可以通过方法选项

Method->{"ConjugateGradient",Method->"FletcherReeves"}

选择使用Fletcher-Reeves方法.

共轭梯度法的优势是, 它们对于大规模问题使用较少的内存而且不需要数值线性代数处理,所以每个步骤都相当快. 缺点是,它们通常收敛速度显著慢于 牛顿 或者 拟牛顿 方法. 另外,步长的尺度通常也掌握得很差,因此 线搜索 算法每次可能需要更多的迭代,以找到一个可以接受的步骤.    

这里加载一个包含一些功用函数的程序包.
In[1]:=
Click for copyable input
这里画出非线性共轭梯度法所采取的步骤. 而其相应的路径远没有牛顿法的路径直接.
In[2]:=
Click for copyable input
Out[2]=

非线性共轭梯度法带来的一个问题是何时重新启动它们. 当我们的搜索过程中,对函数的局部二次近似的性质也可能显著改变. 方法的局部收敛性取决于线性共轭梯度法的局部收敛性,对后者二次函数是不变的. 在一个具有 n 个变量的恒值二次函数和一个精确线搜索的情况下,线性算法将在 n 或更少迭代次数里达到收敛. 通过频繁的重新启动(采取 的最速下降步骤),有可能消除前面点的信息,而这些点的信息可能和目前搜索点的局部二次模型不相关. 如果您仔细查看这个例子,您可以看到方法重新启动的位置以及采取最速下降步骤的位置. 一种选择是在每 k 次迭代后,简单地重新启动,其中 . 对此您可以使用方法选项"RestartIterations"->k 具体指定. 另一个方法是根据下列测试,连续梯度不足够正交时,重新启动

其中阈值 ν 在 0 和 1之间,可以用方法选项 "RestartThreshold"->ν 具体指定.     

下表总结了在共轭梯度法中,您可以使用的选项.     

选项名
默认值
"Method""PolakRibiere"非线性共轭梯度法可以是 或者是
"RestartThreshold"1/10梯度正交性的阈值 ν,低于该值的时候将重新启动
"RestartIterations"多少个迭代次数后将重新启动
"StepControl""LineSearch"必须是 ,但您可以使用这个来指定线搜索方法

Method->"ConjugateGradient" 的方法选项.

应当指出的是,在 Wolfram 语言4 中 FindMinimum 的默认方法是结合了近似精确线搜索法的共轭梯度法. 由于历史的原因这一特点被保存下来,并且可以利用 FindMinimum 选项 Method->"Gradient" 访问. 通常,这将比更新的Method->"ConjugateGradient" 使用更多的函数和梯度求值次数,而后者本身所用的求值次数已远远超过 Wolfram 语言目前默认时所使用的方法.