梯度下降法，最速下降法，牛顿法，Levenberg

2024-06-18 22:09| 来源: 网络整理| 查看: 265

优化对象：凸函数

梯度下降法

顾名思义，就是沿着与梯度相反的方向迭代。（梯度方向是增长最快的方向，所以负梯度方向是下降最快的方向）。

最速下降法

最速下降法是梯度方向法的一种，与上面的梯度下降法不同的是：梯度下降法是固定的学习率，最速下降法是变化的学习率（具体见下面的介绍）。

特点：每一次迭代时的梯度方向与上一次迭代时的梯度方向正交

牛顿法

在某一个特定点处将函数泰勒展开（仅保留至二次项），用泰勒展开的二次函数代替原函数求最小点。求解最小点的方法就是：令二次函数对变量x的一阶导数等于0，求解对应的x点。

在泰勒展开时，因为保留到二次项，因此存在对原函数求二阶导数的运算，即需要用到原函数的Hessian矩阵。因为在将函数进行泰勒展开为二次函数时，可能得到的函数对原函数的拟合并不准确，所以仅仅一步迭代得到的不是真正的最小值，所以，有时候需要多迭代几次。

特点：

1. 需要用到原函数的二阶导（Hessian矩阵），因此需要原函数二阶可导。。

2. 要用到矩阵求逆，（Hessian 矩阵求逆）。矩阵求逆有时并不是很方便，因此会带来一定的计算量。

3. 牛顿法要在某个特定点处展开，如果初始点距离真正的极值点较远，算法可能不收敛。

4. 牛顿方向（见下文介绍），是“除以二阶导的负梯度方向”或"负的一阶导与二阶导的比值" $d^{(k)} =-{G(x^{(k)})}^{-1}\nabla f(x^{(k)}) = -\frac{\nabla f(x^{(k)})}{G(x^{(k)})}$ ，其中 $\nabla f(x^{(k)})$ 是一阶导数， $G(x^{(k)})$ 是二阶导数，Hessian矩阵

更正上图中的公式（3.2.3），增加一个学习率参数 $\alpha_k$ ,更新后的（3.2.3）为：

$x^{(k+1)} = x^{(k)} - \alpha_kG(x^{(k)})^{-1}\nabla f(x^{(k)})$

可见，与梯度下降法与最速下降法相比，牛顿法就是加了一个Hessian矩阵（即原函数的二阶导数）。

所以，与梯度下降法与最速下降法类比，牛顿法也可以通过变化的学习率改进成“最速牛顿法”（这个词是我杜撰的，不存在这种说法，希望不会引起误导）。真正的学术名字叫“阻尼牛顿法”（参考《最优化方法（赖炎连贺国平清华大学出版社）》3.2节）。

Levenberg-Marquardt 修正

牛顿法存在的一个缺点是，二阶导数（Hessian矩阵）不一定正定，有可能会使上面的牛顿方向变成上升方向。针对这一缺点，Levenberg-Marquardt 提出了改进方案：对Hessian矩阵增加一个正定矩阵 $D$ ，强迫新的”Hessian矩阵“（已经不是原来的Hessian矩阵了，或者已经不能用Hessian矩阵命名了，这里为了方便描述这么称呼）为正定，即,使：

$G(x^{(k)}) = G(x^{(k)})+D$

$D$ 是人为定义的一个正定矩阵，常取 $D=I_n$ 为n阶单位矩阵。

拟牛顿法

根据以上分析，牛顿法需要用到矩阵求逆，这有时很困难。拟牛顿法就是为了解决这一个问题：用一个新的矩阵 $H_k$ 来代替Hessian矩阵的逆 $G_k^{-1}$ 。具体如下：

共轭方向发，共轭梯度法

可参考共轭方向法，共轭方向法

参考：【机器学习之数学】02 梯度下降法、最速下降法、牛顿法、共轭方向法、拟牛顿法

《最优化方法（赖炎连贺国平清华大学出版社）》3.2节，3.3节

【本文地址】

公司简介

联系我们