欢迎光临 x-algo
关注算法在工业界应用
Hi, 这是一个关注大数据算法在工业界应用的网站

「最优化」牛顿法

在确定搜索方向上,最速下降法只用到了目标函数的一阶导数。这种方式并非总是最高效的,在某些情况下,如果能够在迭代中引入高阶导数,其效率可能将优于最速下降法。「牛顿法」就是如此,他同时使用一阶导数和二阶导数作为搜索方向。当初始点和目标函数的极小点足够接近的时候,牛顿法的效率要优于最速下降法。牛顿法的迭代原理图:

A28002A6-741D-443F-B27B-05040877F7EE

迭代公式

前提是目标函数二阶可导,将目标函数在 \(x^k\) 处进行泰勒二阶展开,得到:

\(q(x)=f(x^k)+f'(x^k)(x-x^k)+\frac{1}{2}f''(x^k)(x-x^k)^2\)

求此函数的极小值:

\(q'(x)=f'(x^k)+f''(x^k)(x-x^k)=0\)

如果 \(f''(x^k)>0\) ,也就是正定,解得:

\(x^{k+1}=x^k-f''(x^k)^{-1}f'(x^k)=x^k-F(x^k)^{-1}g^k\)

上式就是牛顿迭代公式,是不是和「最速下降法」长得很像,差别就在于:最速下降法的步长是通过「一维搜索」求得,牛顿法是直接使用二阶导数(汉森矩阵)的逆作为"步长"。站在矩阵乘法的角度来看,可看做对一阶导数进行「行变换」。

牛顿法的性质分析

在单变量的情况下,如果函数的二阶导数 \(f''(x)<0\) 牛顿法无法收敛到极小点;再多变量的情况向,如果目标函数的汉森矩阵 \(F(x^k)\) 非正定,牛顿法的搜索方向不一定是目标函数值下降的方向。甚至在某些情况下,即使 \(F(x^k)\) 是正定的,如果当前点远离目标函数的极小点的时候,可能出现 \(f(x^{k+1})\ge f(x^k)\) 。牛顿法的优势在于当前点距离极小点比较近的情况下。

如果目标函数是二次型函数,此时牛顿法只需要一次就可以迭代到极小点。假设二次型函数为:

\(f(x)=\frac{1}{2}x^TQx-x^Tb\)

令其一阶导数为零,求得的解就是极小值点:

\(g(x)=f'(x)=Qx-b=0\)

令其为0,发现解就是线性方程组 \(Qx=b\) 的解,如果Q可逆,解可以记为: \(x=Q^{-1}b\)

上式二阶导数为:

\(F(x)=Q\)

这个结论可以记住,就是二次型函数的汉森矩阵为Q(常数矩阵,和x无关),二次型大于0的条件是Q函数正定,函数有极小值也要保证汉森矩阵正定

利用牛顿迭代式,可以得到下一个迭代点:

\(\begin{matrix}x^1&=&x^0-F(x^0)^{-1}g^0\\&=&x^0-Q^{-1}[Qx^0-b] \\&=&Q^{-1}b\end{matrix}\)

由此可见,牛顿法对二次型函数收敛的阶数为正无穷。

收敛性

没看懂。。挖坑先

牛顿局部下降

牛顿法本质上其实就是用一个二次函数「拟合」目标函数,然后使用求解二次函数的一些方法来求解目标函数。前面说过,原始牛顿法不能保证下一步迭代是下降的。接下来会证明,在当前点附近足够小的邻域内,牛顿法确定的方向一定是原函数的下降方向。这个结论保证了,通过对原始方法的一些修正,可以使得「牛顿法」每一次迭代都是下降的。牛顿法的「局部下降」可以使用更数学的方式定义如下:

\(\{x^k\}\) 是利用牛顿法求解目标函数 \(f(x)\) 极小值的迭代序列,如果 \(F(x^k)>0\) ,且 \(g^k=f'(x^k)\ne0\) ,那么 \(x^k\)\(x^{k+1}\) 的搜索方向:

\(d^k=-F(x^k)^{-1}g^k=x^{k+1}-x^k\)

是一个下降方向,即存在一个 \(\hat{a}>0\) ,使得对所有的 \(\alpha \in (0,\hat{a})\) ,都有:

\(f(x^k + \alpha d^k)< f(x^k)\)

成立。

下面开始证明

构造复合函数

\(\phi(\alpha)=f(x^k+\alpha d^k)\)

使用链式法则得到:

\(\phi'(\alpha)=f'(x^k+\alpha d^k)^Td^k\)

由于 \(F(x^k)>^{-1}>0, g^k\ne0\) ,有

\(\phi'(0)=f'(x^k)^Td^k=-g^{(k)T}F(x^k)^{-1}g^k<0\)

根据导数本身的意义,得证。

一维搜索修正牛顿法

既然我们已经得到了一个确定会下降的方向,一种直观的想法就是确定一个合适的步长即可:

\(x^{k+1}=x^k-\alpha_k F(x^k)^{-1}g^k\)

其中,

\(\alpha_k=\arg \min_{\alpha \ge 0}f(x^k-\alpha F(x^k)^{-1}g^k)\)

上式可以通过一维搜索求解。

当目标函数的维数n比较大的时候计算很森矩阵所需要的时间就比较多,同时还要求解汉森矩阵的逆,可以等价看做是求解线性方程组 \(F(x^k)d^k=-g^k\) 的解。这是牛顿法的缺陷之一。

Levenberg-Marquardt 修正

通过「一维搜索」修正了牛顿法的步长,但是如果汉森矩阵不正定,还是不能保证搜索方向是下降的。所以接下来介绍的方法是对汉森矩阵的修正。

修正之后的迭代公式为:

\(x^{k+1}=x^k-(F(x^k+u_k \mathbf{I}) g^k)\)

其中 \(u_k \ge 0\)

\(F(x^k)\) 为对阵矩阵,假设特征值为 \(\lambda_1,\lambda_2,...,\lambda_n\) ,矩阵 \(G=F+u \mathbf{I}\) 的特征值为 \(\lambda_1+u, \lambda_2+u,...,\lambda_n+u\) ,且满足:

\(\begin{matrix}Gv_i & = & (F+uI)v_i\\&=&Fv_i+uIv_i\\&=&\lambda_i v_i + uv_i\\&=&(\lambda_i + u)v_i \end{matrix}\)

所以,只要u足够大,肯定可以使得修正之后的矩阵G是正定的,加入以为搜索的过程后迭代公式可以写作:

\(x^{k+1}=x^{k}-\alpha_k(F(x^k) + u_k I)^{-1}g^k\)

如果 \(u_k \rightarrow 0\) ,修正效果可以接近牛顿法,如果 \(u_k \rightarrow \infty\) ,Levenberg-Marquardt修正基本退化为步长较小时的梯度方法。在实际应用中,优选选择 \(u_k\) 较小的值。

参考资料

《最优化导论》Edwin K.P.Chong Stanislaw H. Zak

 

 

未经允许不得转载:大数据算法 » 「最优化」牛顿法

评论 抢沙发

*

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注大数据算法在工业界应用

本站的GitHub关于本站