信赖域方法

信赖域方法

信赖域方法在当前搜索点附近具有一个区域，其中关于局部极小化的二次模型

被"信赖"为正确的，并且步骤被选择留在该区域内. 在搜索的过程中，区域大小根据模型和实际函数计算的符合程度被修改.

非常典型地，信赖域采取的是一个满足的椭圆. 是一个对角缩放（通常采用近似

Hessian 的对角），而是信赖域半径，它在每个步骤被更新.

当基于二次模型的步骤本身位于信赖域之内的时候，那么就认为函数值在变小，因而采用这一步骤. 因此，正如线搜索方法中一样，步控制不会干涉算法在二次模型表现良好的极小值附近的收敛效果. 当基于二次模型的步骤位于信赖域之外时，则采用一个只到边界位置的步骤，以使得该步骤成为二次模型在信赖域边界处的近似极小化步骤.

一旦一个步骤被选择，该函数就在新的点被计算，而实际函数值与通过二次模型预测所得到的值互相对照. 真正计算的是实际与预测减少量的比率.

如果接近1，那么该二次模型是一个相当不错的预测器，该区域的大小可以扩大. 另一方面，如果太小，则该区域的大小就要被降低. 当低于某一阈值时，该步骤被拒绝并重新计算.

您可以使用方法选项"AcceptableStepRatio"->控制这一阈值. 通常情况下，是相当小的，以避免走向极小值的步骤也被拒绝. 然而，如果在一个点获取二次模型相当昂贵（例如，计算Hessian 需要花费相对较长的时间），一个较大值的将降低Hessian 计算的次数，但是它可能增加函数计算的次数.

要开始信赖域算法，需要确定一个初始半径. 默认情况下，Mathematica使用基于受比较宽松的相对步长限制的模型(1) 的步骤的大小. 然而，在某些情况下，这可能使您离开您原来感兴趣的区域，所以您可以使用选项指定一个初始半径

. 该选项在它的名字中包含Scaled，因为信赖域半径使用了对角缩放，所以这不是一个绝对的步长.

这里加载一个包含一些功用函数的程序包.

In[1]:=

这里显示在搜索一个与Rosenbrock函数类似的函数的局部极小值的过程中，所采用的步骤和计算，用的是了利用信赖域步控制的牛顿法.

In[2]:

=

Out[2]=

该图示看起来很糟糕，因为搜索在如此大的区域上延伸，以致函数的精细结构不能在这样的尺度上真正看到.

这里显示了对同样函数的步骤和计算，但这里有一个限制了的初始信赖域半径. 这里，搜索更接近初始条件，并且沿着狭谷进行.

In[3]:

=

Out[3]=

我们还可以使用选项对信赖域半径设置一个整体上限，使得对任何步，.

由于在函数计算中数值舍入的问题，信赖域方法也可能在不够光滑的函数上遇到困难. 当函数不足够平滑的时候，信赖域的半径将持续减少. 最终，它将达到一个实际上值为零的点.

这里从Optimization`UnconstrainedProblems`程序包中以一种可以被FindMinimum求解的形式获得Freudenstein-Roth测试问题. （参见"测试问题".）

In[4]:=

Out[4]=

这里使用默认方法对函数寻找一个局部极小值. 在这种情况下的默认方法是（信赖域）Levenberg-Marquardt 方法，因为函数是一个平方和的形式.

In[5]:=

Out[5]=

出现的提示信息表明，相对于搜索点的大小，信赖域的大小实际上已经变为零，所以所采取的步骤将效果甚微. 注：在某些平台上，由于机器运算的微小差异，该信息可能不会显示. 这是因为产生该信息的原因与数值的不确定性有关，这在不同的平台上可能产生不同的变化.

这里在最后找到的点沿着方向画出变差函数图.

In[6]:

=

Out[6]=

沿着一个方向的图使我们相当清楚为什么进一步的改进是不可能的. 在这种情况下

Levenberg-Marquardt 方法陷入困境的部分原因是收敛相对缓慢，因为残差在极小值处非零. 使用牛顿方法，收敛速度更快，完整的二次模型可以更好地估计步长，因此FindMinimum可以对默认容差得到满足更有信心.

In[52]:

=

Out[52]

=

下表总结了对于信赖域步骤控制的选项.

选项名默认值

"AcceptableStepRatio" 1/10000 阈值，使得当实际与预测减少量的比率时，搜索

移动到已计算的步骤

"MaxScaledStepSize" ∞值，使得对于所有步骤，信赖域大小

"StartingScaledStepSize" Automatic 初始信赖域大小

的方法选项.