牛顿型方法(不包括拟牛顿法)
基本牛顿法的收敛性是局部的,计算效果受初值点选取影响很大。一方面初始点选取不当可能会导致 $hesse$矩阵不正定,从而无法下降;另一方面即使海赛矩阵正定了,因为它的收敛性只在局部成立,同样不能保证函数值下降。为解决这些问题,可以使用阻尼牛顿法和修正牛顿法。
1.最速下降法
最速下降法似乎应该不算牛顿型方法,但是它的思想很重要: 找到函数下降最快的方向,然后按照这个方向迭代就能找到极小值点。后面的牛顿型方法都可以看成变度量意义下的最速下降法,即它们依然是沿着下降最快的方向迭代,只是各自对’下降最快’的定义不同,导致具体下降方法不同。
最速下降法的下降方向直接取负梯度方向: $d_k = -g_k$,这种取迭代方向为负梯度方向的算法称为负梯度方法,当搜索步长 $\alpha$ 采用精确线搜索时,就称其为最速下降法。最速下降法对初始点选取不敏感,即使从一个不太靠近最优解的点出发,它也能产生接近最优点的迭代序列,后面拟牛顿法的第一次迭代就是利用最速下降法先快速靠近最优解。同时该方法只需要计算一阶导信息,实现简单且计算量小。虽然最速下降法在每一步迭代都取当前能采取的最优策略,但贪心的未必是最好的: 它的收敛速度是线性收敛,随着迭代的进行,最速下降法靠近最优点的速度会很慢。
采用精确线搜索时,最速下降法的最优步长为 $\alpha = \frac{g_k^{T}g_k}{g_k^{T}Gg_k}$ .
下面是负梯度方法的代码(步长确定使用的是非精确搜索amijo准则而非精确搜索)
|
|
2.阻尼牛顿法
阻尼牛顿法可以改善基本牛顿法的局部收敛性,它可以保证在 hesse 矩阵正定时,${f_k}$ 单调下降,即使 $k$ 点离最优点较远。可以证明对严格凸函数,采用 Wolfe 准则的阻尼牛顿方法具有全局收敛性。
阻尼牛顿法实现很简单,只是在基本牛顿法方向确定的基础上加上步长 $\alpha$ 的一维线搜索,即迭代公式为 $x_{k+1} = x_k + \alpha_kd_k$ .
代码里只要加上一句非精确搜索就好了:
|
|
amijo 搜索的介绍在本文后面给出。
3.修正牛顿方法
修正牛顿方法针对可能出现的 hesse 矩阵非正定的情况做出修正。一种方法就是在 hesse 阵 $G_k$ 非正定时将基本牛顿法的方向 $d_k $ 换成负梯度方向;另一种则是修改 $G_k$ 使其正定: $(G_k+v_kI)d = -g_k$ , 即取新的方向为 $d = -(G_k+v_kI)^{-1}g_k$ , 其中 $v_k>0$ , $I$ 是单位阵,确定合适的 $v_k$ 使 $G_k+v_kI$ 正定即可。
下面给出修改海赛阵的代码,代码来自参考[1]书
|
|
非精确搜索
下面给出两个非精确搜索的代码。分别是 wolfe 准则和 amijo 准则,代码同样非原创。
1.Wolfe
|
|
2.Amijo
|
|
[1]: 最优化方法及其 Matlab 程序设计 马昌凤