无约束最优化(三) 拟Newton法

作者: 小小何先生 | 来源:发表于2019-12-07 09:23 被阅读0次

Newton法的优缺点都很突出。优点：高收敛速度（二阶收敛）；缺点：对初始点、目标函数要求高，计算量、存储量大（需要计算、存储Hesse矩阵及其逆）。拟Newton法是模拟Newton法给出的一个保优去劣的算法。

拟Newton法是效果很好的一大类方法。它当中的DFP算法和BFGS算法是直到目前为止在不用Hesse矩阵的方法中的最好方法。

基本思想

考虑Newton迭代公式
$x_{k+1}=x_{k}-G_{k}^{-1} g_{k} , \ \ k=0,1, ···$
这里搜索方向为 $p_{k}=-G_{k}^{-1}g_{k}$ ，步长因子为1。

我们从以下两点考虑对Newton迭代公式的改进：

(1) 为避免求逆矩阵，设想用某种近似矩阵 $H_{k}=H(x_{k})$ 替换 $-G_{k}^{-1}$ ，上式则变为
$x_{k+1}=x_{k}-H_{k} g_{k} , \ \ k=0,1, ···$
这时搜索方向为 $p_{k}=-H_{k}g_{k}$ ，步长因子仍为1。

(2) 为了取得更大的灵活性，考虑更一般的公式
$x_{k+1}=x_{k}-t_{k}H_{k} g_{k} , \ \ k=0,1, ···$
这时搜索方向仍为 $p_{k}=-H_{k}g_{k}$ ，但步长因子取为最优步长因子。上式是代表面很广的一类迭代公式。例如，当 $H_{k}=E$ 时，它是最速下降法公式。当 $H_{k}=G_{k}^{-1}$ 时，它是阻尼Newton法公式。

这样的 $H_{k}$ 存在吗？又如何来求呢？假如存在，那么为使 $H_{k}$ 确实近似 $G_{k}^{-1}$ 并易于计算，我们要对 $H_{k}$ 人为地附加某些条件。主要是三点：

第一，为保证搜索方向 $p_{k}=-H_{k}g_{k}$ 是下降方向，如果 $\nabla f(x_{0})^{T}p < 0$ ，则 $p$ 方向是函数 $f(x)$ 在点 $x_{0}$ 处的下降方向得到：
$p_{k}^{T} g_{k}<0 \Rightarrow-g_{k}^{T} H_{k} g_{k}<0 \Rightarrow g_{k}^{T} H_{k} g_{k}>0$
要求每一个 $H_{k}$ 都是对称正定矩阵，可以保证该式成立。

第二，为易于计算，要求 $H_{k}$ 到 $H_{k+1}$ 之间具有简单的迭代形式。最简单的迭代关系为
$H_{k+1}=H_{k}+E_{k}$
$E_{k}$ 称为校正矩阵，上式称为校正公式。

第三，为使 $H_{k}$ 确实近似 $G_{k}^{-1}$ 要求每一个 $H_{k}$ 必须满足拟Newton条件。那所谓的拟Newton条件是啥呢？

我们假设目标函数 $f(x)$ 具有连续的二阶偏导数，将 $f(x)$ 在点 $x_{k+1}$ 处作Taylor级数展开：
$f(x) \approx f\left(x_{k+1}\right)+\nabla f\left(x_{k+1}\right)^{T}\left(x-x_{k+1}\right)+\frac{1}{2}\left(x-x_{k+1}\right)^{T} G_{k+1}\left(x-x_{k+1}\right)$
对上式两端求梯度有：
$\nabla f(x) \approx g_{k+1}+G_{k+1}\left(x-x_{k+1}\right)$
令 $x=x_{k}$ ，则有：
$g_{k} \approx g_{k+1}+G_{k+1}\left(x_{k}-x_{k+1}\right)$
所以，当 $G_{k+1}$ 正定时，有
$x_{k+1}-x_{k} \approx G_{k+1}^{-1}\left(g_{k+1}-g_{k}\right)$
对于正定二次函数,上式近似将变为等式。

因此，如果迫使 $H_{k+1}$ 满足类似于上式的等式
$x_{k+1}-x_{k} = H_{k+1} \left(g_{k+1}-g_{k}\right)$
那么 $H_{k+1}$ 就有可能很好地近似于 $G_{k+1}^{-1}$ 上式称为拟Newton条件或拟Newton方程。

记：
$s_{k}=x_{k+1}-x_{k} \\ y_{k} = g_{k+1}-g_{k}$
那么拟Newton条件可简记为：
$H_{k+1}y_{k}=S_{k}$
带入迭代关系式 $H_{k+1}=H_{k}+E_{k}$ 有：
$E_{k}y_{k} = S_{k} - H_{k}y_{k}$
算法中的校正矩阵 $E_{k}$ 可由确定的公式来计算，不同的公式对应不同的拟Newton算法。满足条件的 $E_{k}$ 有无穷多个，因此上述的拟Newton算法是一簇算法。

DFP算法

DFP法是首先由Davidon(1959年)提出，后由Fletcher和Powell（1963年）改进的算法。它是无约束优化方法中最有效的方法之一。DFP法虽说比共轭梯度法有效，但它对直线搜索有很高的精度要求。

考虑如下校正公式
$H_{k+1}=H_{k}+\alpha_{k}u_{k}u_{k}^{T}+\beta_{k}v_{k}v_{k}^{T}$
其中 $u_{k}$ ， $v_{k}$ 是待定列向量， $\alpha_{k}$ ， $\beta_{k}$ 是待定常数。校正矩阵
$E_{k}=\alpha_{k}u_{k}u_{k}^{T}+\beta_{k}v_{k}v_{k}^{T}$
根据拟Newton条件，有
$\alpha_{k}u_{k}u_{k}^{T}y_{k}+\beta_{k}v_{k}v_{k}^{T}y_{k} = s_{k}-H_{k}y_{k}$
上式 $u_{k}$ 和 $v_{k}$ 有很多种取法

$\alpha_{k}u_{k}u_{k}^{T}y_{k} = s_{k} \\ \beta_{k}v_{k}v_{k}^{T}y_{k} = -H_{k}y_{k}$

如果取 $u_{k}=s_{k}$ ， $v_{k}=H_{k}y_{k}$ 那么有
$\alpha_{k}=\frac{1}{s_{k}^{T}y_{k}}, \ \beta_{k}=-\frac{1}{y_{k}^{T}H_{k}y_{k}}$

$H_{k+1}=H_{k}+\frac{s_{k}s_{k}^{T}}{s_{k}^{T}y_{k}}-\frac{H_{k}y_{k}y_{k}^{T}H_{k}}{y_{k}^{T}H_{k}y_{k}}$

DFP算法的性质

定理1：在DFP算法中，若初始矩阵 $H_{0}$ 对称正定，则 $H_{k}$ 中每一个都对称正定。

定理2：设将DFP算法施用于具有对称正定矩阵 $Q$ 的二次函数 $f(x)=\frac{1}{2} x^{T} Q x+b^{T} x+c$ ，如果:

(i) 初始矩阵 $H_{0}$ 对称正定；

(ii) 迭代点互异，产生的搜索方向向量依次为 $p_{0},p_{1}，···，P_{k} \ (k \leq n-1)$ ，则有
$p_{i}^{T}Q p_{j} = 0, \ i,j = 0,1,···，k(i \neq j) \\ H_{k+1}Qp_{j} = p_{j}, \ j=0,1,···，k.$
定理3：若定理2的条件都满足，并且经过 $n$ 次迭代才求到极小点，则 $H_{n}=Q^{-1}$ 。

我的微信公众号名称：深度学习与先进智能决策
微信公众号ID：MultiAgent1024
公众号介绍：主要研究分享深度学习、机器博弈、强化学习等相关内容！期待您的关注，欢迎一起学习交流进步！

无约束最优化(三) 拟Newton法

基本思想

DFP算法

DFP算法的性质

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

最优化