拟牛顿法

我们有许多不同的拟牛顿方法. 在所有这些方法中,基本思想都是基于如下二次模型中的矩阵

这里基于从该函数建立的Hessian矩阵的近似,以及从之前采取的一些或全部步骤得到的导数值的近似

这里加载一个包含一些功用函数的程序包.
In[1]:=
Click for copyable input
这里画出拟牛顿法所采取的步骤. 我们可以看到,该路径远没有牛顿法的路径直接. 对于不是平方和形式的问题,拟牛顿法被 FindMinimum 作为默认值使用.     
In[2]:=
Click for copyable input
Out[2]=

关于这个例子中采用的路径,首先要注意的是它沿错误的方向起始. 选择这个方向,是因为在所有方法的第一步都是沿着梯度的方向,因此它采取了最速下降的方向. 然而,在随后的步骤里,它结合了已采取步骤函数值及梯度值的信息,来建立一个Hessian的近似模型.

Mathematica 所采用的方法是 Broyden-Fletcher-Goldfarb-Shanno (BGFS) 更新,而对于大型系统,则使用有限内存的BFGS (L-BFGS) 方法. 对后者,模型 没有被明确地存储,而是通过从过去的步骤存储的梯度和步骤方向来计算 .

在 BFGS 方法的执行中,并不是在每个步骤形成模型 Hessian ,而是计算Cholesky 因子 ,使得 ,因此对于一个具有 个变量的问题,只需要 操作来求解系统 [DS96].

对于大型稀疏问题,BFGS 方法可能会产生问题,因为一般而言,Cholesky 因子(或者Hessian 近似 或者它的逆矩阵) 是密集的,因此 的内存和操作要求与可以利用稀疏优点的算法相比,变得令人难以承受. L-BFGS 算法[NW99] 基于过去 步存储的信息建立一个 Hessian 矩阵的逆矩阵的近似. 该 Hessian 近似可能不是完整的,但是内存和操作的次数对于一个具有 个变量的问题,可以限制在 . 在 Mathematica 5中,对于超过250个变量的问题,该算法自动切换至L-BFGS. 您可以通过方法选项 "StepMemory"->m 对此进行控制. 对于 ,我们将总是使用完全 BFGS 方法. 选择合适的 值是对于收敛速度和每一步所做的工作量的折衷. 对于 ,您有可能最好使用 "共轭梯度算法".

这里显示了与前面的例子相同的函数,极小值是用 L-BFGS 方法在 的情况下计算的.
In[3]:=
Click for copyable input

Out[3]=

拟牛顿方法在 Mathematica 中被选为默认值,因为它们通常是相当快的,并且不需要计算 Hessian 矩阵,我们知道Hessian矩阵无论是符号式的计算还是数值计算都可能相当昂贵. 如果用一个足够好的线搜索,它们可以超线性地收敛 [NW99] 到一个Hessian是正定的局部极小值. 这意味着

或者,换句话说,步长越变越小. 然而,对于很高的精确度,这并不能与牛顿方法的 -二次收敛速度相比较.

这里显示了对于以上所示的问题,要找到高精确度的极小值所需的步骤数目和函数求值次数.
In[4]:=
Click for copyable input
Out[4]=

由于具有二次收敛速度,牛顿法能够使用更少的步骤数目找到10倍多的位数. 然而,拟牛顿法的收敛速度仍然是超线性的,因为误差的比率明显趋近于零.     

这里画图显示计算中的误差比率. 误差比率以对数坐标显示,以便在很大范围内看到其变化趋势.
In[5]:=
Click for copyable input
Out[5]=

下表总结了使用拟牛顿方法时可以使用的选项.     

选项名
默认值
"StepMemory"Automatic在 Hessian 近似中需要"记住"有效步骤数目;可以是一个正整数或者是 Automatic
"StepControl""LineSearch"如何控制步骤; 可以是 或者 None

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

New to Mathematica? Find your learning path »
Have a question? Ask support »