主轴法

高斯-牛顿共轭梯度方法使用导数信息. 当 Wolfram 语言不能计算符号化表示的导数时,则使用有限差分法. 使用有限差分计算导数信息在某些情况下将产生显著的成本增加,而且也肯定会影响导数的可靠性,最终可以对达到的极小值的近似程度产生影响. 对于不能获得符号化表示的导数的函数,另一种方法是使用一个无导数算法,只使用函数求值来建立近似模型.     

Wolfram 语言使用 Brent 的主轴法 [Br02] 作为无导数算法. 对于一个具有 个变量的问题,取一个由搜索方向 构成的集合和一个点 . 让 作为沿着方向 最小化 的点(即从 进行一个线搜索),然后用 代替 . 结束时,用 代替 . 理想的情况是,新的 应该是线性无关的,所以可以进行一轮新的迭代,但是在实践中,它们不是线性无关的. Brent 算法包含了在矩阵 上使用奇异值分解(SVD),以将它们调整到局部二次模型的主方向上.(本来也可以使用特征分解,但是Brent证明SVD更有效.)利用获得的 的新集合,我们可以进行另一轮迭代.     

对于这种方法来说,每个变量需要两个不同的初始条件,因为这些是用来定义向量 的大小的. 事实上,只要您在每个变量上指定两个初始条件,FindMinimumFindMaximumFindFit 将默认地使用主轴算法.

这里加载一个包含一些功用函数的程序包.
In[1]:=
Click for copyable input
这里显示了在寻找函数 的一个局部极小值时,FindMinimum 的搜索路径及对函数的求值.
In[2]:=
Click for copyable input
Out[2]=

搜索算法的基本信息可以从图示中很清楚地看到,因为无导数的线性搜索算法需要大量的函数求值. 首先,在 方向进行一个线搜索,然后从该点在 方向进行一个线搜索,从而确定步骤的方向. 一旦采取了步骤,我们就根据局部二次近似的主方向对向量 进行适当的调整,然后下一步进行同样的计算.

该算法就收敛速度而言是有效的;在步骤方面它具有二次收敛速度. 但是,就对函数求值次数,这是很昂贵的,因为需要无导数的线搜索方法. 请注意,由于所给的线搜索的方向(特别是在开始的时候)不一定是下降方向,线搜索必须能够在两个方向进行搜索. 对于有许多变量的问题,在所有方向的单独线搜索变得非常昂贵,因此这种方法通常更适合没有太多变量的问题.