牛顿法与拟牛顿法（DFP BFGS LBFGS VLBFGS） | 源码分享博客

2015年阅读书单每个人的金线读《红楼梦》 2014年阅读书单 2013年阅读书单 2012年阅读书单 2011年阅读书单 2010年阅读书单

黑椒牛排

租房奇遇记海岸公路

Mac以及Windows上搭建C++工作环境 Git常用命令速查表

从二次型最优化问题中理解矩阵特征值的意义牛顿法与拟牛顿法（DFP BFGS LBFGS VLBFGS）

吉他上弦枕的DIY调节找工作总结

捡代码论坛官方微信,不定期分享免费优质资源下载

随感 2

每个人的金线读《红楼梦》

Git 1

Git常用命令速查表

Mac 1

Mac以及Windows上搭建C++工作环境

Math 2

从二次型最优化问题中理解矩阵特征值的意义牛顿法与拟牛顿法（DFP BFGS LBFGS VLBFGS）

Optimization 2

从二次型最优化问题中理解矩阵特征值的意义牛顿法与拟牛顿法（DFP BFGS LBFGS VLBFGS）

年终总结 2

吉他上弦枕的DIY调节找工作总结

捡代码论坛 1

捡代码论坛官方微信,不定期分享免费优质资源下载

牛顿法与拟牛顿法（DFP BFGS LBFGS VLBFGS）

2015年03月23日

最近做LBFGS的并行，顺便把牛顿法、拟牛顿法顺理一下。

拟牛顿法是求解非线性优化问题最有效的方法之一。考虑无约束的极小化问题 $\min\limits_x f(x)$ ，假设 $f(x)$ 为凸函数，且二阶连续可导。

原始牛顿法

基本思想：在现有极小点估计值的附近对f(x)进行二阶泰勒展开，进而找到下一个极小点的估计值

$x_{k+1}=x_{k}-(H_k)^{-1}g_{k}, k=0,1,\cdots$

牛顿法具有二次收敛性，但当目标函数非二次型时，牛顿法不能保证函数稳定地下降（缺点）。

阻尼牛顿法

每次迭代前需要沿迭代方向 $d_k=-(H_k)^{-1}g_k$ 做线搜索，寻求最优的步长因子 $\lambda_k$ ，即

$\lambda_k = \arg\min\limits_{\lambda} f(x_k+\lambda d_k)$

拟牛顿法

基本思想：不使用二阶偏导数而构造出可以近似Hession或Hession的逆的正定对称阵，在“拟牛顿”的条件下优化目标函数。

先推导拟牛顿条件：在 $x_{k+1}$ 附近对 $f(x)$ 做泰勒展开，取二阶近似项

$f(x)=f(x_{k+1})+\nabla f(x_{k+1})(x-x_{k+1})+\frac{1}{2}(x-x_{k+1})^T\nabla^2 f(x_{k+1})(x-x_{k+1})$ 推出

$\nabla f(x)\approx \nabla f(x_{k+1})+H_{k+1}(x-x_{k+1})$ 取 $x=x_k$ ，推出

$g_{k+1}-g_{k}\approx H_{k+1}(x_{k+1}-x_k)$

引入记号 $s_k=x_{k+1}-x_{k}, y_k=g_{k+1}-g_{k}$ ，推出

$y_k=H_{k+1}s_k , s_k=H^{-1}_{k+1}y_k$ (拟牛顿条件)

它迭代过程中的hession矩阵做约束，因此，对hession对近似的 $B_{k+1}$ ，以及对hession的逆做近似的 $D_{k+1}$ ，可以将

$y_{k}=B_{k+1}s_k$ 或 $s_{k}=D_{k+1}y_k$ 作为指导。

DFP算法（Davidon–Fletcher–Powell formula）

核心：通过迭代的方法，对hession的逆做近似。迭代格式为

$D_{k+1}=D_k+\Delta D_k$ （通常 $D_0=I$ ）

猜想 $\Delta D_k$ 待定为 $\Delta D_k=\alpha \mathbf{u} \mathbf{u}^{\mathrm{T}}+\beta\mathbf{v}\mathbf{v}^{\mathrm{T}}$ （具有对称性）

$\Rightarrow s_k=D_ky_k+\alpha\mathbf{u}\mathbf{u}^{\mathrm{T}}y_k+\beta\mathbf{v}\mathbf{v}^{\mathrm{T}}y_k=D_ky_k+(\alpha\mathbf{u}^{\mathrm{T}}y_k)\mathbf{u}+(\beta\mathbf{v}^{\mathrm{T}}y_k)\mathbf{v}$

括号中是数值，将其分别简单赋值为1，-1，即

$\alpha=\frac{1}{\mathbf{u}^{\mathrm{T}}y_k},\beta=-\frac{1}{\mathbf{v}^{\mathrm{T}}y_k}$

其中向量u,v仍有待确定，由上面

$\Rightarrow \mathbf{u}-\mathbf{v}=s_k-D_ky_k$ （要此式成立，不妨直接取 $\mathbf{u}=s_k,\mathbf{v}=D_ky_k$ ）

$\Rightarrow \alpha=\frac{1}{s^{\mathrm{T}}_ky_k},\beta=-\frac{1}{y^{\mathrm{T}}_kD_ky_k}$

至此，校正矩阵 $\Delta D_k$ 就已经构造出来了

$\Rightarrow \Delta D_k=\frac{s_ks_k^{\mathrm{T}}}{s_k^{\mathrm{T}}y_k}-\frac{D_ky_ky_k^{\mathrm{T}}D_k}{y_k^{\mathrm{T}}D_ky_k}$

BFGS算法（Broyden–Fletcher–Goldfarb–Shanno algorithm）

核心公式的推导过程与DFP完全类似，只是互换了其中s{k}和y{k}的位置。BFGS直接逼近Hession矩阵B_k。(公式敲起来太累了，请自行推导)

LBFGS算法(limited-memory BFGS)

不再存储完整的Dk，而是存储计算过程中的向量序列{s}，{y}。当需要矩阵Dk时，利用向量序列的计算来代替。并且，向量序列也不是全部存储，而是固定存最新的m个。

若要实现并行，需要同时在x与梯度（影响y的计算）那儿求一致平均。

资料

【1】DFP算法

【2】BFGS算法

【3】LBFGS算法

【4】Large-scale L-BFGS using MapReduce