拟牛顿算法
在牛顿算法中我们要面对逆向的Hessian以及二阶的偏导。导致我们的计算量很大,为了提高效率,如果无法使用Hessian矩阵H(x),或者如果计算逆矩阵的计算量太大(复杂度为O(N ^ 3),则拟牛顿法可以 仅可用于基于一阶导数,f( x)(具有复杂度 O(N ^ 2))的梯度g来建立一个近似Hessian的矩阵或其逆的近似矩阵 ,类似于先前考虑的Broyden方法。我们可以使用拟牛顿算法。
下面我们考虑最小化函数f(x)。 围绕点X_n+1进行泰勒展开得到如下方程:

讯享网
下面对X求导我们可以得到:

Evaluating at x=x_n,并且设g(x_n) = g_n那么上面的式子就可以变为:

其中矩阵B _n 是Hessian矩阵H_n 的正割近似,最后的等式称为割线方程。 为了方便起见,我们进一步定义:

那么上面的公式可以变为:

那么我们有了Hessian的近似矩阵,这样我们就可以达成了拟牛顿算法 的条件。
拟牛顿步骤:
- 初始化x_0 以及B_0 设置n=0
- 计算梯度g_n 并且找到向量:

- 计算:

是我们的步长。 - 更新公式来满足拟牛顿算法:

- 如果达到终止条件,则结束,没达到条件则返回第二步N=N+1。
在我们的这个求解局部最小值中, B_n也就是我们的近似矩阵,要是一个正定举证。(正定矩阵的定义看我的另一篇文章)
SR1(Symmetric Rank 1)
SR1 是拟牛顿算法中的一种,这里B_n的更新需要添加一个附加项。

在这里u是一个向量。uut 是第一级的矩阵。以及加上我们的割线条件,就可以得到:

该方程式表示u与w=y_n - B_n s_n的方向相同,因此可以写成 u = cw 。 换回来我们得到:

然后我们求的c等于:

那么Bn就会变成:

接下来反转B_n+1我们可以得到:

要想得到上面的结果,我们还可以使用对偶分割条件的方法:

但是SR1 算法有个问题就是需要Bn的逆向保持正定。

在整个迭代过程中可能很难维持这一要求。 在以下DFP和BFGS方法中可以避免此问题。
BFGS(Broyden-Fletcher-Goldfarb-Shanno)
在这个算法中需要添加两个额外附加项:

更具割线定理,我们可以得到:

然后将简化拓展:


DFP







是我们的步长。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/79435.html