牛顿法、拟牛顿法

牛顿法：

根据二阶泰勒展开，用一阶和二阶倒数确定参数迭代步长和方向

设初始向量\vec{x} ，它在\vec{x_k} 处的泰勒展开如下：

f(\vec{x})=f(\vec{x_k})+\nabla f(\vec{x}_k)^T(\vec{x}-\vec{x}_k) +\frac{1}{2} (\vec{x}-\vec{x}_k)^T \nabla^2 f(\vec{x}_k)(\vec{x}-\vec{x}_k)+o(x)，当\vec{x}_k\rightarrow \vec{x}时

注：矩阵求导公式：

X^TAX=2AX a^TX=a

对上式相对于\vec{x}求导：

\frac{\partial f(\vec{x})}{\partial \vec{x}} = \nabla f(\vec{x}) = \nabla f(\vec{x}_k)+\nabla^2 f(\vec{x}_k)(\vec{x}-\vec{x}_k)①

因此可以得到\vec{x}_k处的迭代方程：

\vec {x}_{k+1} = \vec {x}_k - \frac{\nabla f(\vec{x}_k)}{\nabla^2 f(\vec{x})}

对应\vec {x}_{k+1} = \vec {x}_k + \lambda_kd_k这种形式，步长\lambda_k=\nabla f(\vec{x_k})，方向d_k=-\frac{1}{\nabla^2 f(\vec{x})}

拟牛顿法：

从上述公式可以知道，牛顿法的每一次迭代都需要计算二阶海塞矩阵，当特征和数据非常多时，时间和空间开销都会比较大。

拟牛顿法只是一种方法的统称，即用一个近似矩阵B去替代逆海塞矩阵H^{-1}，然后在每一轮迭代中更新B

怎样找到逆海塞矩阵的替代矩阵？

对上一节中的①式做一下变换：

\nabla f(\vec{x}_{k+1}) - \nabla f(\vec{x}_k)=\nabla^2 f(\vec{x}_k)(\vec{x}_{k+1}-\vec{x}_k)

令g_k=\nabla f(\vec{x_k}),H_k= \nabla^2 f(\vec{x_k})，上式变成：

g_{k+1}-g_k=H_k(\vec{x}_{k+1}-\vec{x}_k)

再令g_{k+1}-g_k=y_k，S_k=\vec{x}_{k+1}-\vec{x}_k，得到：

H_k=\frac{y_k}{S_k}①

也就是说，第k步迭代的海塞矩阵可以通过第k步的迭代步长和一阶导数差值拟合。

BFGS(Broyden–Fletcher–Goldfarb–Shanno):
https://blog.csdn.net/itplus/article/details/21897443

BFGS算法

用B_k表示H_k的近似，D_k表示H^{-1}_k的近似：

那么B_{k+1}的迭代公式为B_{k+1}=B_k+\Delta B_k

设\Delta B_k= \alpha uu^T+\beta vv^T②，再根据①式得到的y_k=B_kS_k:

y_k=B_k\cdot S_k +\alpha \boldsymbol{u u^T} S_k +\beta \boldsymbol{v v^T} S_k

交换u^TS_k和u的位置：y_k=B_k\cdot S_k +\alpha \boldsymbol{ u^T} S_k \boldsymbol{u} +\beta \boldsymbol{v^T} S_k \boldsymbol{v}

令：\alpha u^T S_k=1, \beta v^T S_k=1，以及u=y_k,v=S_k

解出：\alpha=\frac{1}{y_k^TS_k},\beta=\frac{-1}{v^T S_k}=\frac{-1}{S_k^TB_k^TS_k}

再带入到②中：

\Delta B_k = \frac{y_k y_k^T}{y_k^T S_k} -\frac{B_k S_k S_k^T B_K^T}{S_K^T B_K^T S_k}

L-BFGS:

BFGS中B矩阵的每次更新都需要nXn的空间开销，L-BFGS不会直接存储B，而是①只存取需要用到的n个向量，并且②只保存了最近的m次迭代的结果，所以L-BFGS算法又做了近似。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容