机器学习优化算法L

算法L"/>

机器学习优化算法L

最近做的科研项目需要用到L-BFGS，这段时间看了不少关于L-BFGS的博客以及论文，在此进行一下小小的总结。

在无约束优化问题中，牛顿法及拟牛顿法是常用的方法，L-BFGS属于拟牛顿法，下面从牛顿法开始说起。

牛顿法，顾名思义，是由伟大的牛顿先生首先提出的（当然有资料显示，在更早前就有人提出相同方法，但可能因为牛顿先生名气过大，冠以他的名字会更火）。我们考虑无约束问题 minf(x)x∈Rn $min f(x) x\in R^n$， 牛顿法需要使用Taylor展开，因此我们假设 f(x) $f(x)$是二阶可微实函数，把 f(x) $f(x)$在 xk $x^k$处Taylor展开并取二阶近似为

f(x)≈f(xk)+∇f(xk)T(x−xk)+12(x−xk)T∇2f(xk)(x−xk)(1) $$f(x)\approx f(x^k)+\nabla f(x^k)^T(x-x^k)+\frac{1}{2} (x-x^k)^T \nabla ^2f(x^k)(x-x^k) (1)$$
其中， ∇2f(x) $\nabla ^2f(x)$是 f(x) $f(x)$在 xk $x^k$处的 Hessen矩阵。我们的目标是求 f(x) $f(x)$的最小值，而导数为0的点极有可能为极值点，故在此对 f(x) $f(x)$求导，并令其导数为0，即 ∇f(x)=0 $\nabla f(x)=0$，可得
∇f(x)=∇f(xk)+∇2f(xk)(x−xk)=0(2) $$\nabla f(x)=\nabla f(x^k)+\nabla ^2f(x^k)(x-x^k)=0 (2)$$
设 ∇2f(x) $\nabla ^2 f(x)$可逆，由(2)可以得到牛顿法的迭代公式
xk+1=xk−∇2f(xk)−1∇f(xk)(3) $$x^{k+1}=x^k-\nabla ^2 f(x^k)^{-1}\nabla f(x^k) (3)$$ d=−∇2f(xk)−1∇f(xk) $d=-\nabla ^2 f(x^k)^{-1}\nabla f(x^k)$被称为牛顿方向，可以证明牛顿法至少是2阶收敛的，在此由于篇(neng)幅(li)所限，就不进行证明了。

细心的读者可能会发现，我们上面的推导公式，做了很多前提假设，假设了Hessen矩阵 ∇2f(x) $\nabla ^2f(x)$可逆，那么问题来了，如果 f(x) $f(x)$的Hessen矩阵奇异，或者非奇异但是不正定怎么办？这个时候，我们就需要使用拟牛顿法了，拟牛顿法，同样可以顾名思义，就是模拟牛顿法，用一个近似于 ∇2f(x)−1 $\nabla ^2f(x) ^{-1}$的矩阵 Hk+1 $H_{k+1}$来替代 ∇2f(x)−1 $\nabla ^2f(x) ^{-1}$。公式(2)在 xk+1 $x^{k+1}$附近有，

∇f(x)=∇f(xk+1)+∇2f(xk+1)(x−xk+1) $$\nabla f(x)=\nabla f(x^{k+1})+\nabla ^2f(x^{k+1})(x-x^{k+1})$$ 令 x=xk $x=x^k$，则有 ∇f(xk)=∇f(xk+1)+∇2f(xk+1)(x−xk+1) $$\nabla f(x^k)=\nabla f(x^{k+1})+\nabla ^2f(x^{k+1})(x-x^{k+1})$$ 记 pk=xk+1−xk $$p^k=x^{k+1}-x^k$$ qk=∇f(xk+1)−∇f(xk) $$q^k=\nabla f(x^{k+1})-\nabla f(x^k)$$ 代入则有， pk≈∇2f(xk+1)−1qk $$p^k\approx \nabla ^2f(x^{k+1})^{-1}q^k$$ 拟牛顿法用 Hk+1 $H_{k+1}$来替代 ∇2f(x)−1 $\nabla ^2f(x) ^{-1}$，即 pk=Hk+1qk(4) $$p^k=H_{k+1}q^k (4)$$ 这也被称为拟牛顿条件。在各种拟牛顿法中，一般的构造 Hk+1 $H_{k+1}$的策略是， H