割线法

当不能使用符号化方法计算导数时,牛顿方法将被使用,但要利用对雅可比的有限差分近似. 这会在时间和可靠性上花费成本. 和极小化中的处理一样,我们有另一种专门为不使用导数而设计的算法.

在一维空间中,割线方法的思想是使用两个连续的搜索点之间线的斜率,来计算步骤,而不是使用最新点的导数. 同样地,在 个维度上,我们使用在 个点的残差的差值来建立雅可比排序的近似. 请注意,这类似于有限差分方法,但不是为了获得尽量好的雅可比近似而试图使差异间隔变小,它实际上就像一维割线方法一样,是用一个平均导数. 最初,这 个点从在所有 个维度上不同的两个初始点构造. 在随后的步骤中,只有具有最小的优值函数值的 个点被保留下来. 有种情况,虽然罕见,但是可能,即步骤是共线的,因而雅可比的割线近似变得奇异. 在这种情况下,算法使用不同的点重新启动.

该方法需要在每个维度上有两个初始点. 事实上,如果在每个维度上给出两个初始点,割线法就是默认的方法,除了在一维空间,这时候可能会选择布伦特方法.

这里加载一个包含一些功用函数的程序包.
In[1]:=
Click for copyable input
这里显示了使用割线法,Rosenbrock问题的解.
In[2]:=
Click for copyable input
Out[2]=

请注意,与牛顿方法相比,我们需要更多的残差函数计算. 然而,该方法能够不直接使用导数信息而沿着相对狭窄的谷部移动.     

这里显示了在使用有限差分计算雅可比的牛顿方法的情况下,Rosenbrock问题的解.
In[3]:=
Click for copyable input
Out[3]=

然而,当与有限差分法牛顿法比较时,残差函数计算的次数就具有可比性. 对于较大问题的稀疏雅可比矩阵,有限差分牛顿法通常会更有效率,因为割线法不以任何方式利用稀疏的特点.