 |
拟牛顿法
我们有许多不同的拟牛顿方法. 在所有这些方法中，基本思想都是基于如下二次模型中的矩阵 
这里基于从该函数建立的Hessian矩阵的近似，以及从之前采取的一些或全部步骤得到的导数值的近似
| In[1]:= |
| In[2]:= |
| 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 方法. 选择合适的 
值是对于收敛速度和每一步所做的工作量的折衷. 对于 
，您有可能最好使用 "共轭梯度算法".
拟牛顿方法在 Mathematica 中被选为默认值，因为它们通常是相当快的，并且不需要计算 Hessian 矩阵，我们知道Hessian矩阵无论是符号式的计算还是数值计算都可能相当昂贵. 如果用一个足够好的线搜索，它们可以超线性地收敛 [NW99] 到一个Hessian是正定的局部极小值. 这意味着
或者，换句话说，步长越变越小. 然而，对于很高的精确度，这并不能与牛顿方法的 
-二次收敛速度相比较.
由于具有二次收敛速度，牛顿法能够使用更少的步骤数目找到10倍多的位数. 然而，拟牛顿法的收敛速度仍然是超线性的，因为误差的比率明显趋近于零.
| In[5]:= |
| Out[5]= |  |
选项名 | 默认值 | |
| "StepMemory" | Automatic | 在 Hessian 近似中需要"记住"有效步骤数目；可以是一个正整数或者是 Automatic |
| "StepControl" | "LineSearch" | 如何控制步骤; 可以是  或者 None |
Method->"QuasiNewton" 的方法选项.
