自动驾驶小白说 🏎️5.2 数值优化基础:梯度下降法,牛顿法
type
status
slug
date
summary
tags
category
password
icon
朕四季常服, 不过八套. — 大明王朝1566 道长
🏰代码及环境配置：请参考0.2 环境配置和代码运行 | 动手学运动规划!
上一节我们介绍了数值优化的基本概念, 让大家对最优化问题有了基本的理解.
那么对于一个具体的问题, 我们应该如何求解呢? 这一节我们将介绍几个基本的求解方法, 为了简化问题, 我们会基于无约束凸优化问题来做解释. 因为无约束凸优化问题, 梯度为0的点(极值点), 就是全局最优解.
最优化问题的求解是一个迭代的过程, 从初始点(初始解)开始, 通过迭代方法(梯度下降法, 牛顿法等)逐步更新, 直至逼近最优解.
上图形象的展示了这个迭代的过程, 从初始解start点开始, 逐步迭代至最优解. 在这个1维问题上, 迭代方向只有左和右(-, +), 我们如何确定迭代的方向和步长呢? 或者更高维度的问题里, 如何确定每个维度的方向和步长呢?
接下来我们介绍几个基础的最优化求解方法
5.2.1 梯度下降法(Gradient Descent)
梯度是指函数在某一点上沿着各个方向的偏导数, 梯度代表着当前点函数值增加最快的方向. 定义如下:
梯度下降法是最常采用的方法之一, 它会沿着梯度下降(相反)的方向逐步调整决策变量. 它的更新公式如下:
其中是第k次迭代x的值, 是第k次迭代的步长.
这张动图可以清晰的展示梯度下降法更新的过程, 每次迭代, 都沿着梯度方向, 更新迭代点.
(1) 梯度下降法的优点
- 实现简单：梯度下降法只需要计算函数的梯度（一阶导数），实现简单，计算量相对较小。
- 广泛适用：对于大多数连续可导的凸函数，梯度下降法都能找到局部最小值。当目标函数是凸函数时，梯度下降法的解是全局解。
- 参数更新方向合理：梯度下降法基于梯度信息选择参数更新方向，这是函数在当前位置的最快下降方向。
(2) 梯度下降法的缺点
- 收敛速度慢：梯度下降法是一阶收敛算法，在接近最小值点时，梯度值会变得很小，导致收敛速度变慢。此外，直线搜索时可能会产生“之字形”下降路径，进一步降低收敛速度。
- 对初始值敏感：不同的初始值可能导致算法收敛到不同的局部最小值。
- 需要手动调整学习率：学习率的选择对算法的收敛速度和效果有很大影响。学习率过大可能导致算法发散，学习率过小则收敛速度过慢。
- 可能陷入局部极值点：如果目标函数不是凸函数而是含有多个极小值点的函数，梯度下降法可能会陷入局部极小点而无法继续下降。
5.2.2 牛顿法(Newton Method)
梯度下降法是一种一阶导数迭代的方法, 收敛速度较慢. 如果利用二阶导数, 是不是能够更快的逼近极值点呢?
牛顿法就是二阶导数迭代的代表, 它综合了一阶和二阶信息, 能够快速收敛. 更新公式如下:
其中是指函数的Hessian矩阵, 是一个由函数的二阶偏导数构成的矩阵,定义如下:
是Hessian矩阵的逆矩阵, 可以看出牛顿法的计算量很大.
这张图展示了梯度下降法(绿)和牛顿法(红)的对比, 可以看到牛顿法要高效的多.
(1) 牛顿法的优点
- 收敛速度快：牛顿法利用了函数的二阶导数信息（Hessian矩阵），能够在接近最小值点时快速收敛。特别是对于正定二次函数，牛顿法的一步迭代即可达到最优解。
- 对初始值不敏感：相对于梯度下降法，牛顿法对初始值的依赖性较小，更有可能找到全局最优解。
- 全局视野：牛顿法在选择下降方向时，不仅考虑当前位置的梯度，还考虑未来位置梯度的变化趋势，因此具有更强的全局视野。
(2) 牛顿法的缺点
- 计算量大：牛顿法需要计算函数的二阶导数（Hessian矩阵）及其逆矩阵，计算量相对较大
- 对Hessian矩阵要求高：Hessian矩阵必须正定，否则算法可能无法收敛。此外，当Hessian矩阵接近奇异时，算法可能会变得不稳定。
- 函数要求苛刻：牛顿法要求目标函数二阶连续可微，且Hessian矩阵可逆.
因为牛顿法的计算量较大, 为了克服这个问题, 拟牛顿法应运而生. 拟牛顿法不直接去计算Hessian矩阵, 而是通过 近似Hessian矩阵的逆矩阵 来达到类似牛顿法的效果. 常见的拟牛顿法有BFGS等.
下一节我们将使用梯度下降法和牛顿法, 解决Rosenbrock Function, 让大家更直观的看到两种方法的区别.
参考链接
Loading...
