二阶算法

• 牛顿法
• 拟牛顿法
• BFGS
• L-BFGS

1. 牛顿法

• 对于无约束问题，假设f(x)是二阶可微实函数，

* 牛顿法基础

• $\varphi = f(x_k)+f^{'}(x_k)(x-x_k)+\frac{1}{2}f^{''}(x_k)(x-x_k)^2+R(X)$

• $f^{''}(x) \ 记 \ \bigtriangledown^2f(x)$是hessian矩阵

=>

$\varphi^{'}(x)\approx f^{'}(x_k)+f^{''}(x_k)(x-x_k)$

=> => 迭代公式(前提$\bigtriangledown^2f(x)$可逆) =>

$x_{k+1}=x_k+\frac{f^{'}(x_k)}{f^{''}(x_k)}$

• 方向导数代替一阶导数
• Hessian矩阵代替二阶导数

* 牛顿法的特点

• 收敛性：无法保证（信頼域可以保证）收敛；Hessian矩阵无法保证正定，会导致算法产生的方向，不能保证$x_k$处于下降方向，从而使得牛顿法失效

• Hessian矩阵计算量大，计算复杂

• Hessian奇异矩阵，牛顿方向不存在

2. 拟牛顿算法

• 牛顿算法，$\bigtriangledown^2f(x)$可逆，若不可逆，则产生拟牛顿算法，模拟牛顿算法（逆矩阵不好计算）
• 使用近似矩阵$H_{k+1}$来代替$\bigtriangledown^2f(x)^{-1}$

对上式求导

* 拟牛顿条件：

$p^{(k)}=H_{k+1}q^{(k)}$

* $\bigtriangleup H_k$是校正矩阵

3. BFGS

4. L-BFGS

• 仅存储最近的m个n维数据（一般20个）

owl-qn

牛顿法的补充

http://blog.csdn.net/itplus/article/details/21896453