高德资讯

Pytorch优化器全总结（三）牛顿法、BFGS、L-BFGS 含代码

优化器系列文章列表

Pytorch优化器全总结（一）SGD、ASGD、Rprop、Adagrad

Pytorch优化器全总结（二）Adadelta、RMSprop、Adam、Adamax、AdamW、NAdam、SparseAdam

Pytorch优化器全总结（四）常用优化器性能对比含代码

这篇文章是优化器系列的第三篇，主要介绍牛顿法、BFGS和L-BFGS，其中BFGS是拟牛顿法的一种，而L-BFGS是对BFGS的优化，那么事情还要从牛顿法开始说起。?

函数最优化算法方法不唯一，其中耳熟能详的包括梯度下降法，梯度下降法是一种基于迭代的一阶优化方法，优点是计算简单；牛顿法也是一种很重要的优化方法，是基于迭代的二阶优化方法，优点是迭代次数少，收敛速度很快。下面我们简要介绍一下牛顿法。

? ? ? ? 最优化问题就是寻找能使函数最小化的x，所以目标函数应当是一个凸函数（起码是局部凸函数），假如一个函数如下图：

?图1

? ? ? ? ?他的一阶导数可能长下面这个样子：

?图2

? ? ? ? ?很显然函数在 $x_n$ 处取得最小值，同时这个点的导数等于0，如果使用梯度下降，经过多次迭代，x的取值会慢慢接近 $x_n$ ，我们都能想象这个过程。

? ? ? ? 如果使用牛顿法，x也会逼近 $x_n$ ，不过速度会快很多，示例图如下：

图3

这个过程可以这样描述：

a.在X轴上随机一点 $x_{1}$ ,经过 $x_{1}$ 做X轴的垂线,得到垂线与函数图像的交点 $f(x_{1})$ .

? ? ? ? b.通过 $f(x_{1})$ 做函数的切线,得到切线与X轴的交点 $x_{2}$ .

? ? ? ? c.迭代a/b两步，当前后两次求的x相同或者两个值的差小于一个阈值的时候，我们就认为找到了 $x_n$ 。

? ? ? ? 三个步骤的难点在于b，如何快速的找到切线与X轴的交点，下面有两种计算方式，思想不同但结果是一样的。

图4

? ? ? ? 如图4，蓝色的线是函数的 $f(x)$ 的导数 $f^{'}(x)$ ，则曲线在 $x_1$ 处的导数为 $f^{''}(x_1)$ ，我们要求 $x_2$ ，根据三角函数有：

$f^{''}(x_1)=\frac{f^{'}(x_1)}{x_1-x_2}$ （1）

? ? ? ? 得出：

$x_2=x_1-\frac{f^{'}(x_1)}{f^{''}(x_1)}$ （2）

? ? ? ? 利用 $x_2$ 开始进行下一轮的迭代。迭代公式可以简化如下：

$x_{n+1}=x_{n}-\frac{f^{'}(x_{n})}{f^{''}(x_{n})}$ （3）

任意一点在 $x_k$ 附近的二阶泰勒展开公式为：

$f(x)=f(x_n)+f^{'}(x_n)(x-x_n)+\frac{1}{2}f^{''}(x_n)(x-x_n)^2$ （4）

? ? ? ? 对 $f(x)$ 求导：

$f^{'}(x)=f^{'}(x_n)+f^{''}(x_n)(x-x_n)$ （5）

? ? ? ? 令 $f^{'}(x)=0$ :

? $x=x_{n}-\frac{f^{'}(x_{n})}{f^{''}(x_{n})}$ （6）

? ? ? ? 写成迭代形式：

$x_{n+1}=x_{n}-\frac{f^{'}(x_{n})}{f^{''}(x_{n})}$ （7）

? ? ? ? 可以看到使用三角函数和二阶泰勒展开最终得到的结果是一样的。虽然牛顿法收敛速度很快，但是当x的维度特别多的时候，我们想求得 $f^{''}(x)$ 是非常困难的，而牛顿法又是一个迭代算法,所以这个困难我们还要面临无限多次，导致了直接使用牛顿法最为优化算法很难实际落地。为了解决这个问题出现了拟牛顿法，下面介绍一种拟牛顿法BFGS，主要就是想办法一种方法代替二阶导数。

函数? $f(x)$ 在? $x=x_{k+1}$ 处的二阶泰勒展开式为：

$f(x)=f(x_{n+1})+f^{'}(x_{n+1})(x-x_{n+1})+\frac{1}{2}f^{''}(x_{n+1})(x-x_{n+1})^2$ （8）

当x为向量的时候，上式写成：

$f(x)=f(x_{n+1})+\bigtriangledown f(x_{n+1})(x-x_{n+1})+\frac{1}{2}\bigtriangledown^2 f(x_{n+1})(x-x_{n+1})^2$

? ? ? ? （9）

? ? ? ? 令 $G_{n+1}=\bigtriangledown ^2f(x_{n+1})$ ，同时对 $f(x)$ 求导：

$\bigtriangledown f(x)=\bigtriangledown f(x_{n+1})+G_{n+1}(x-x_{n+1})$ ? ? ? ? ? ? ? ? （10）

? ? ? ? ?接下来我们要想办法去掉 $G_{n+1}$ ，我们使用 $B_{n+1}$ 代替 $G_{n+1}$ ， $B_{n+1}$ 是在迭代中一点点计算出来的而不使用二阶导数。

? ? ? ? 上式变为:

$\bigtriangledown f(x)=\bigtriangledown f(x_{n+1})+B_{n+1}(x-x_{n+1})$ ? ? ? ? ? ? ? ? （11）

$B_{n+1}(x_{n+1}-x)=\bigtriangledown f(x_{n+1})-\bigtriangledown f(x)$ ? ? ? ? ? ? ? ? （12）

? ? ? ? 我们认为每次迭代 $B_k$ 与上次变化 $E_k$ ，形式如下：

$B_{n+1}=B_{n}+E_{n}$ ? ? ? ? ? ? ? ? ? ? ? ? （13）

令：

$y_n=\bigtriangledown f(x_{n+1})-\bigtriangledown f(x_n)$ ， $s_n=x_{n+1}-x_n$ ? ? ? ? ? ? ? ? （14）

将式（13）（14）带入式子（12）：

$(B_n+E_n)s_n = y_n$ ? ? ? ? ? ? ? ? ? ? ? ? （15）

令：

$E_n=\alpha u_nu_{n}^{T}+\beta v_nv_{n}^{T}$ ? ? ? ? ? ? ? ?（16）

?其中? $u_n,v_n$ 均为?n维的向量，带入（15）

$(B_n+\alpha u_nu_{n}^{T}+\beta v_nv_{n}^{T})s_n=y_n$ ? ? ? ? ? ? ? ? （17）

$\alpha (u_{n}^{T}s_n)u_n+\beta (v_{n}^{T}s_n)v_n=y_n-B_ns_n$ ? ? ?（18）

?已知： $u_{n}^{T}s_n,v_{n}^{T}s_n$ ?为实数， $y_n-B_ns_n$ ?为向量。式（18）中，参数? $u_{n}$ 和? $v_{n}$ 解的可能性有很多，我们取特殊的情况，假设? $u_n=rB_ns_n,v_n= heta y_n$ 。带入（16）得：

$E_n=\alpha r^2B_ns_ns_{n}^{T}B_n+\beta heta^2 y_ny_{n}^{T}$ ? ? ? ? ? ? ? ? ? ? ? ? （19）

将? $u_n=rB_ns_n,v_n= heta y_n$ 带入（18）得：

$\alpha [(rB_ns_n)^Ts_n](rB_ns_n)+\beta [( heta y_n)^T]( heta y_n)=y_n-B_ns_n$ （20）

$[\alpha r^2(s_{n}^{T}B_ns_n)+1]+[\beta heta ^2(y_{n}^{T}s_n)-1](y_n)=0$ ? ? ? ? （21）

?令? $\alpha r^2(s_{n}^{T}B_ns_n)+1=0$ ，则：

$\alpha r^2=-\frac{1}{s_{n}^{T}B_ns_n}$ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （22）

? ? ? ? 令 $\beta heta ^2(y_{n}^{T}s_n)-1=0$ ，则

$\beta heta ^2=\frac{1}{y_{n}^{T}s_n}$ ? ? ? ? ? ? ? ? ? ? ? ? （23）

? ? ? ? 将式（22）和（23）带入（19）：

$E_n=-\frac{B_ns_ns_{n}^{T}B_n}{s_{n}^TB_ns_n}+\frac{y_ny_{n}^{T}}{y_{n}^{T}s_k}$ ? ? ? ? ? ? ? ? ? ? ? ? ? ?（24）

? ? ? ? 将（24）带入（13）得到 $B_n$ 的迭代公式：

$B_{n+1}=B_n-\frac{B_ns_ns_{n}^{T}B_n}{s_{n}^TB_ns_n}+\frac{y_ny_{n}^{T}}{y_{n}^{T}s_k}$ ? ? ? ? ? ? ? ? ? ? ? ? （24）

? ? ? ? 当x为向量的时候，式（7）写成：

$x_{n+1}=x_n-B_{n}^{-1}\bigtriangledown f(x_n)$ ? ? ? ? ? ? ? ? ? ? ? ? （25）

? ? ? ? 加上学习率得到BFGS的迭代公式：

$x_{n+1}=x_n-\eta(B_{n}^{-1}\bigtriangledown f(x_n))$ ? ? ? ? ? ? ? ? ? ? ? ? ?（26）

? ? ? ? 我们发现，还需要求 $B_n$ 的逆，这里可以引入sherman-morrism公式，求解 $B_n$ 的逆：

$B_{n+1}^{-1}=(I-\frac{s_ny_n}{y_{n}^{T}s_n})^TB_{n}^{-1}(I-\frac{y_ns_{n}^{T}}{y_{n}^{T}s_n})+\frac{s_ns_{n}^{T}}{y_{n}^{T}s_n}$ ? ? ? ? ? ? ? ? （27）

我们用 $H$ 代替 $B^{-1}$ ，得到最终的BFGS迭代公式和 $H$ 的迭代公式：

? $x_{n+1}=x_n-\eta(H_{n}\bigtriangledown f(x_n)$ ? ? ? ? ? ? ? ? （28）

$H_{n+1}=(I-\frac{s_ny_n}{y_{n}^{T}s_n})^TH_{n}(I-\frac{y_ns_{n}^{T}}{y_{n}^{T}s_n})+\frac{s_ns_{n}^{T}}{y_{n}^{T}s_n}$ ? ? ? （29）

? ? ? ? 其中 $s_n$ 是本轮x与上一轮x的差， $y_n$ 是本轮梯度与上一轮梯度的差。

在BFGS算法中，仍然有缺陷，每次迭代计算需要前次迭代得到的 $H_n$ ， $H_n$ 的存储空间至少为N(N+1)/2（N为特征维数），对于高维的应用场景，需要的存储空间将是非常巨大的。为了解决这个问题，就有了L-BFGS算法。L-BFGS即Limited-memory BFGS。 L-BFGS的基本思想就是通过存储前m次迭代的少量数据来替代前一次的矩阵，从而大大减少数据的存储空间。

? ? ? ? 令 $\rho _n=\frac{1}{y_{n}^{T}s_n},V_k=I-\frac{y_ns_{n}^{T}}{y_{n}^{T}s_k}$ ，则式（29）可以表示为：

? $H_{n+1}=V_{n}^{T}H_nV_n+\rho _ns_ns_{n}^{T}$ ? ? ? ? ? ? ? ? ? ? ? ? （30）

若在初始时，假定初始的矩阵 $H_0=I$ ，则我们可以得到：

? $H_1=V_{0}^{T}H_0V_0+\rho _0s_0s_{0}^{T}$ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（31）

$H_2=V_{1}^{T}H_1V_1+\rho _1s_1s_{1}^{T}$

$=V_{1}^{T}(V_{0}^{T}H_0V_0+\rho _0s_0s_{0}^{T})+\rho _1s_1s_{1}^{T}$

$=V_{1}^{T}V_{0}^{T}H_0V_1+V_{1}^{T}\rho _0s_0s_{0}^{T}V_1+\rho _1s_1s_{1}^{T}$ ? ? ? ? （32）

$H_{n+1}=(V_{n}^{T}V_{n-1}^{T}\cdots V_{1}^{T}V_{0}^{T})H_0(V_0V_1\cdots V_{n-1}V_n)$

$+(V_{n}^{T}V_{n-1}^{T}\cdots V_{1}^{T})\rho _1s_1s_{1}^{T}(V_1\cdots V_{n-1}V_n)$

$+ \cdots$

$+V_{n}^{T}\rho _{n-1}s_{n-1}s_{n-1}^{T}V_n$

$+\rho _ns_ns_{n}^{T}$

?假设当前迭代为n，只保存最近的m次迭代信息，按照上面的方式迭代m次，可以得到如下的公式：

$H_{n+1}=(V_{n}^{T}V_{n-1}^{T}\cdots V_{n-m}^{T})H_0(V_{n-m}\cdots V_{n-1}V_n)$

$+(V_{n}^{T}V_{n-1}^{T}\cdots V_{n-m}^{T})\rho _1s_1s_{1}^{T}(V_{n-m}\cdots V_{n-1}V_n)$

$+ \cdots$

$+V_{n}^{T}\rho _{n-1}s_{n-1}s_{n-1}^{T}V_n$

$+\rho _ns_ns_{n}^{T}$

由于 $\rho ,V$ 这些变量都最终可以由s、y两个向量计算得到，因此，我们只需存储最后m次的s、y向量即可算出 $H_{n+1}$ ，加上对角阵 $H_0$ ?，总共需要存储2*m+1个N维向量（实际应用中m一般取4到7之间的值，因此需要存储的数据远小于Hesse矩阵）。

1. 选初始点 $x_0$ ，最小梯度阈值 $\varepsilon > 0$ ，存储最近 m 次的选代数据；

2.初始化 $n=0,H_0=I,r=\bigtriangledown f(x_0)$ ；

3.如果 $||\bigtriangledown f(x_{n+1})||\leqslant \varepsilon$ ，则返回最优解 x，否则转入步骤4；

4.计算本次选代的可行方向 $p+n=-r_k$ ；

? ? ? ? 5.计算步长 $\alpha _k$ ，用下面的式子进行线搜索；

$f(x_n+\alpha _np_n)=minf(x_n-\alpha p_n)$

? ? ? ? 6.用下面的更新公式更新x；

$x_{n+1}=x_n+\alpha _np_n$

? ? ? ? 7.如果 n大于 m，保留最近 m 次的向量对，删除 $s_{n-m},y_{n-m}$ ；

8.计算并保存向量对

$s_n=x_{n+1}-x_n$

$y_n=\bigtriangledown f(x_{n+1})-\bigtriangledown f(x_{n})$

9.用 two-loop recursion算法求：

$r_n=B_n\bigtriangledown f(x_n)$

? ? ? ? 10.设置 $n=n+1$ ，转到步骤3

该类实现 LBFGS优化方法。LBFGS是什么已经不用多说了。? ?

? ? ? ? Pytorch说明文档：LBFGS — PyTorch 1.13 documentation

? ? ? ? 我们用一个简单的全连接网络并使用LBFGS优化，下面是代码和运行结果，可以看到，损失下降的速度还是很快的。

?牛顿法、BFGS和L-BFGS就介绍到这里，后面我将对比所有优化算法的性能，收藏关注不迷路。

优化器系列文章列表

Pytorch优化器全总结（一）SGD、ASGD、Rprop、Adagrad

Pytorch优化器全总结（二）Adadelta、RMSprop、Adam、Adamax、AdamW、NAdam、SparseAdam

Pytorch优化器全总结（三）牛顿法、BFGS、L-BFGS 含代码

Pytorch优化器全总结（四）常用优化器性能对比含代码

关注订阅号了解更多精品文章

交流探讨、商务合作请加微信

上一篇：盘前有料丨深圳优化住房限购政策；九部门发文支持新能源汽车贸易合作……重要消息还有这些下一篇：产业结构优化升级大全11篇

栏目导航

高德资讯

联系我们

电话：13988888888

传真：海南省海口市

手机：0898-66889888

邮箱：88889999

地址：/public/upload/system/2018/07/28/2091301cca30ff8c6fd3ecd09c8d4b02.jpg

高德资讯

Pytorch优化器全总结（三）牛顿法、BFGS、L-BFGS 含代码

相关新闻

栏目导航

高德资讯

联系我们