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