Beale 函数和牛顿迭代

计算科学 优化 数值分析 收敛 牛顿法
2021-12-25 12:08:32

我试图找到由下式给出的所谓 Beale 函数的最小值

f(x1,x2)=(1.5x1+x1x2)2+(2.25x1+x1x22)2+(2.625x1+x1x23)2

使用牛顿迭代

x(k+1)=x(k)α(k)η(k)η(k)=(2fx2(x(k)))1fx(x(k))

在点 x=[4  1]Tα=0.5. 结果是xnum=[0  1]T,而真正的最小值在xmin=[3  0.5]T.

我发现问题是η指向错误的方向。它没有像渐变那样显示“下坡”。我的问题是,这怎么可能?为什么牛顿迭代在这里失败了?

编辑:顺便说一句,如果我开始的话,我会得到一些结果x=[4  0.9]T. 首先发生了一些奇怪的事情x(k)正在跳来跳去,然后又在x=[0  1]T.

3个回答

牛顿法是求解非线性方程的定点迭代法。在优化功能的背景下f(x),您应用此方法来找到必要最优性条件的解决方案f(x)=0. 但是,这种情况表征了所有固定点,例如最大化点或鞍点,因此该方法很乐意为您提供其中一个(如果存在)。此外,牛顿法只是局部收敛的,所以它会给你最接近起点的局部最小化器(或最大化器)(如果它完全收敛的话)。

Beale 的函数确实有一个鞍点(0,1), 自从xf(0,1)=yf(0,1)=0, 但黑森

(xxf(0,1)xyf(0,1)xyf(0,1)yyf(0,1))=1114(0110)
有特征值±111/4.

事实上,Beale 的方法是一种流行的折磨测试来说明为什么全局最小化器难以计算……

编辑:具有适当线搜索的梯度方法有一个额外的机制,试图强制(足够的)函数值减少,因此在大多数情况下会避免最大化。他们也倾向于避免鞍点(至少与牛顿的方法相比),但正如 Geoff Oxberry 指出的那样,并不能保证。

对于无约束的优化问题,确定性优化方法会收敛到固定点。静止点是目标函数的梯度为零的点。这些点不一定是最优的,除非满足其他条件。对于最小化问题,如果在静止点处评估的 Hessian 矩阵是半正定的,则​​该静止点是局部最小值。如果目标函数是凸的(等效地,对于两次连续可微的目标函数,Hessian 在任何地方都是半正定的),则静止点是全局最小值。

您遇到的问题是您试图最小化的目标函数是非凸的。正如 ChristianClason 指出的那样,您收敛到一个固定点,但该固定点是一个鞍点,这意味着您的目标函数不是凸的,因此不能保证收敛到全局最小值。

其他人已经提出了解决方案。我的建议是看一下 Nocedal 和 Wright 的书“数值优化”。这本书有一整节关于“Hessian 修改”,正是针对您正在观察的问题。它确实非常易读,并以简单的步骤列出了问题及其解决方案。