manjhok 阅读(29) 评论(0)

一.牛顿法

Taylor公式 – Maclaurin公式:



1.求根问题:

牛顿法的最初提出是用来求解方程的根的。我们假设点

xx∗为函数f(x)f(x)的根,那么有f(x)=0f(x∗)=0。现在我们把函数f(x)f(x)在点xkxk处一阶泰勒展开有:

f(x)=f(xk)+f′(xk)(x−xk            

那么假设点xk+1xk+1为该方程的根,则有

            

那么就可以得到

                

这样我们就得到了一个递归方程,我们可以通过迭代的方式不断的让xx趋近于xx∗从而求得方程f(x)f(x)

的解。该递归式同样可以通过下图的方式得到:

 在该图中我们可以看到xn+1xn+1是要比xnxn更接近于xx∗,而xn+1xn+1

利用三角形特征可以知。其中,

f(xn)   f′(xn)在三角形中表示点(xn,f(xn))(xn,f(xn))    切线的斜率。 


2.优化问题:

对于最优化问题,其极值点处有一个特性就是在极值点处函数的一阶导数为0。因此我们可以在一阶导数处利用牛顿法通过迭代的方式来求得最优解,即相当于求一阶导数对应函数的根。 
首先,我们对函数在xkxk点处进行二阶泰勒展开


因此,当xxk


这里假设点xk+1xk+1是一阶导数的根,那么就有


依据上式可以得到


这样我们就得到了一个不断更新xx迭代求得最优解的方法。这个也很好理解,假设我们上面的第一张图的曲线表示的是函数f(x)f(x)一阶导数的曲线,那么其二阶导数就是一阶导数对应函数在某点的斜率,也就是那条切线的斜率,那么该公式就和上面求根的公式本质是一样的。 

我们这里讨论的都是在低维度的情形下,那么对于高维函数,其二阶导数就变为了一个海森矩阵,那么迭代公式就变为了


我们可以看到,当HkHk为正定(H1kHk−1

也为正定)的时候,可以保证牛顿法的搜索方向是向下搜索的

牛顿法求最优值的步骤如下: 
1. 随机选取起始点x0

2. 计算目标函数f(x)f(x)在该点xkxk的一阶导数和海森矩阵

3. 依据迭代公式更新x

        

如果  则收敛返回,否则继续步骤2,3直至收敛 ,我们可以看到,当我们的特征特别多的时候,求海森矩阵的逆的运算量是非常大且慢的,这对于在实际应用中是不可忍受的,因此我们想能否用一个矩阵来代替海森矩阵的逆呢,这就是拟牛顿法的基本思路。

E(f(xk+1)−f(xk))<ϵ

二.拟牛顿法

因为我们要选择一个矩阵来代替海森矩阵的逆,那么我们首先要研究一下海森矩阵需要具有什么样的特征才能保证牛顿法成功的应用。通过上面的描述我们知道


上式我们称之为拟牛顿条件。


DFP算法



其中定义:

最终:


实现代码:


BFGS

矩阵迭代公式





实现代码:




L-BFGS

BFGS需要存储n×n的方阵Ck用于近似Hessian阵的逆矩阵;而L-BFGS仅需要存储最近m(m约为10,m=20足够)个             用于近似Ck即可。
L-BFGS的空间复杂度O(mn),若将m看做常数则为线性,适用于特征巨大的优化问题。