信赖域方法

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

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

非常典型地,信赖域采取的是一个满足 的椭圆. 是一个对角缩放(通常采用近似 Hessian 的对角),而 是信赖域半径,它在每个步骤被更新.

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

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

如果 接近1,那么该二次模型是一个相当不错的预测器,该区域的大小可以扩大. 另一方面,如果 太小,则该区域的大小就要被降低. 当 低于某一阈值 时,该步骤被拒绝并重新计算. 您可以使用方法选项"AcceptableStepRatio"->η 控制这一阈值. 通常情况下, 是相当小的,以避免走向极小值的步骤也被拒绝. 然而,如果在一个点获取二次模型相当昂贵(例如,计算 Hessian 需要花费相对较长的时间),一个较大值的 将降低 Hessian 计算的次数,但是它可能增加函数计算的次数.

要开始信赖域算法,需要确定一个初始半径 . 默认情况下,Wolfram 语言使用基于受比较宽松的相对步长限制的模型(1) 的步骤的大小. 然而,在某些情况下,这可能使您离开您原来感兴趣的区域,所以您可以使用选项 指定一个初始半径 . 该选项在它的名字中包含 Scaled,因为信赖域半径使用了对角缩放 ,所以这不是一个绝对的步长.

这里加载一个包含一些功用函数的程序包.
In[1]:=
Click for copyable input
这里显示在搜索一个与Rosenbrock函数类似的函数的局部极小值的过程中,所采用的步骤和计算,用的是了利用信赖域步控制的牛顿法.
In[2]:=
Click for copyable input
Out[2]=

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

这里显示了对同样函数的步骤和计算,但这里有一个限制了的初始信赖域半径 . 这里,搜索更接近初始条件,并且沿着狭谷进行.
In[3]:=
Click for copyable input
Out[3]=

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

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

这里从 Optimization`UnconstrainedProblems` 程序包中以一种可以被 FindMinimum 求解的形式获得Freudenstein-Roth测试问题. (参见 "测试问题".)
In[4]:=
Click for copyable input
Out[4]=
这里使用默认方法对函数寻找一个局部极小值. 在这种情况下的默认方法是(信赖域)Levenberg-Marquardt 方法,因为函数是一个平方和的形式.
In[5]:=
Click for copyable input
Out[5]=

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

这里在最后找到的点沿着 方向画出变差函数图.
In[6]:=
Click for copyable input
Out[6]=

沿着一个方向的图使我们相当清楚为什么进一步的改进是不可能的. 在这种情况下 Levenberg-Marquardt 方法陷入困境的部分原因是收敛相对缓慢,因为残差在极小值处非零. 使用牛顿方法,收敛速度更快,完整的二次模型可以更好地估计步长,因此 FindMinimum 可以对默认容差得到满足更有信心.

In[52]:=
Click for copyable input
Out[52]=

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

选项名
默认值
"AcceptableStepRatio"1/10000阈值 ,使得当实际与预测减少量的比率 时,搜索移动到已计算的步骤
"MaxScaledStepSize",使得对于所有步骤,信赖域大小
"StartingScaledStepSize"Automatic初始信赖域大小

的方法选项.