拟牛顿法

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

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

关于这个例子中采用的路径，首先要注意的是它沿错误的方向起始. 选择这个方向，是因为在所有方法的第一步都是沿着梯度的方向，因此它采取了最速下降的方向. 然而，在随后的步骤里，它结合了已采取步骤函数值及梯度值的信息，来建立一个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 方法. 选择合适的 值是对于收敛速度和每一步所做的工作量的折衷. 对于 ，您有可能最好使用 "共轭梯度算法".

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

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

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

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