有什么问题需要咨询?

免费在线咨询

问: 拟牛顿法和牛顿法有啥区别?
李木子
2015-07-07 00:00
牛顿
拟牛顿法和牛顿法有啥区别,各自优缺点是啥
回复 拟牛顿法和牛顿法有啥区别?
回答数858
收到赞60

牛顿法

x_{t+1} = x_t - (\nabla^2 f(x_t))^{-1}\nabla f(x_t)

这个式子是由将f(x)在 x_t 处进行二阶泰勒打开然后令其导数为零得到的,牛顿法的iteration complexity是 O(log log \frac{1}{\epsilon}) 。可是问题在于牛顿法每一步迭代所需的开支太大,即其每一步都需求求Hessian矩阵并对其求逆,其间对矩阵求逆现已需求 O(n^3) 的时刻杂乱度了。


拟牛顿法

x_{t+1} = x_t - \eta_tH_t\nabla f(x_t)

拟牛顿法就是为处理上面的运转时刻太长而发生的,其直接近似Hessian矩阵的逆,具体办法有许多,比较常用的有BFGS办法(以Broyden,Fletcher,Goldfarb,Shanno四位科学家的首字母命名),L-BFGS(Limited memory BFGS)等等。怎么判别Hessian矩阵近似地好不行呢?一个常用的criterion是gradient matching,具体来说,设 f_t(x)f(x)x_t 的二次泰勒打开(其间Hessian矩阵用近似的 H_t 替代。那么一个很天然的主意就是我让这两个函数在 x_tx_{t-1} 处一阶导持平来束缚 H_t 的近似的质量。

2018-06-09 00:00:00
上一页 1 下一页