【动手学运动规划】 5.2 数值优化基础:梯度下降法,牛顿法

朕四季常服, 不过八套. — 大明王朝1566 道长

🏰代码及环境配置：请参考 环境配置和代码运行!

---

上一节我们介绍了数值优化的基本概念, 让大家对最优化问题有了基本的理解.

那么对于一个具体的问题, 我们应该如何求解呢? 这一节我们将介绍几个基本的求解方法, 为了简化问题, 我们会基于无约束凸优化问题来做解释. 因为无约束凸优化问题, 梯度为0的点(极值点), 就是全局最优解.

最优化问题的求解是一个迭代的过程, 从初始点(初始解)$x_0$开始, 通过迭代方法(梯度下降法, 牛顿法等)逐步更新$x_i$, 直至逼近最优解$x^{\ast }$.

上图形象的展示了这个迭代的过程, 从初始解start点开始, 逐步迭代至最优解. 在这个1维问题上, 迭代方向只有左和右(-, +), 我们如何确定迭代的方向和步长呢? 或者更高维度的问题里, 如何确定每个维度的方向和步长呢?

接下来我们介绍几个基础的最优化求解方法

5.2.1 梯度下降法(Gradient Descent)

梯度是指函数在某一点上沿着各个方向的偏导数, 梯度代表着当前点函数值增加最快的方向. 定义如下:

$$\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)$$

梯度下降法是最常采用的方法之一, 它会沿着梯度下降(相反)的方向逐步调整决策变量. 它的更新公式如下:

$$x^{k+1}=x^k-{\alpha }_k\nabla f\left(x^k\right)\text{. }$$

其中$x^k$是第k次迭代x的值, ${\alpha }_k$是第k次迭代的步长.

这张动图可以清晰的展示梯度下降法更新的过程, 每次迭代, 都沿着梯度方向, 更新迭代点.

(1) 梯度下降法的优点

• 实现简单：梯度下降法只需要计算函数的梯度（一阶导数），实现简单，计算量相对较小。
• 广泛适用：对于大多数连续可导的凸函数，梯度下降法都能找到局部最小值。当目标函数是凸函数时，梯度下降法的解是全局解。
• 参数更新方向合理：梯度下降法基于梯度信息选择参数更新方向，这是函数在当前位置的最快下降方向。

(2) 梯度下降法的缺点

• 收敛速度慢：梯度下降法是一阶收敛算法，在接近最小值点时，梯度值会变得很小，导致收敛速度变慢。此外，直线搜索时可能会产生“之字形”下降路径，进一步降低收敛速度。
• 对初始值敏感：不同的初始值可能导致算法收敛到不同的局部最小值。
• 需要手动调整学习率：学习率的选择对算法的收敛速度和效果有很大影响。学习率过大可能导致算法发散，学习率过小则收敛速度过慢。
• 可能陷入局部极值点：如果目标函数不是凸函数而是含有多个极小值点的函数，梯度下降法可能会陷入局部极小点而无法继续下降。

5.2.2 牛顿法(Newton Method)

梯度下降法是一种一阶导数迭代的方法, 收敛速度较慢. 如果利用二阶导数, 是不是能够更快的逼近极值点呢?

牛顿法就是二阶导数迭代的代表, 它综合了一阶和二阶信息, 能够快速收敛. 更新公式如下:

$$x^{k+1}=x^k-{\nabla }^{2}f{\left(x^k\right)}^{-1}\nabla f\left(x^k\right)$$

其中${\nabla }^2$是指函数的Hessian矩阵, 是一个由函数的二阶偏导数构成的矩阵,定义如下:

$${\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}\\ ⋮& ⋮& \ddots & ⋮\\ \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]$$

${\nabla }^{2}f{\left(x^k\right)}^{-1}$是Hessian矩阵的逆矩阵, 可以看出牛顿法的计算量很大.

这张图展示了梯度下降法(绿)和牛顿法(红)的对比, 可以看到牛顿法要高效的多.

(1) 牛顿法的优点

• 收敛速度快：牛顿法利用了函数的二阶导数信息（Hessian矩阵），能够在接近最小值点时快速收敛。特别是对于正定二次函数，牛顿法的一步迭代即可达到最优解。
• 对初始值不敏感：相对于梯度下降法，牛顿法对初始值的依赖性较小，更有可能找到全局最优解。
• 全局视野：牛顿法在选择下降方向时，不仅考虑当前位置的梯度，还考虑未来位置梯度的变化趋势，因此具有更强的全局视野。

(2) 牛顿法的缺点

• 计算量大：牛顿法需要计算函数的二阶导数（Hessian矩阵）及其逆矩阵，计算量相对较大
• 对Hessian矩阵要求高：Hessian矩阵必须正定，否则算法可能无法收敛。此外，当Hessian矩阵接近奇异时，算法可能会变得不稳定。
• 函数要求苛刻：牛顿法要求目标函数二阶连续可微，且Hessian矩阵可逆.

因为牛顿法的计算量较大, 为了克服这个问题, 拟牛顿法应运而生. 拟牛顿法不直接去计算Hessian矩阵, 而是通过 近似Hessian矩阵的逆矩阵 来达到类似牛顿法的效果. 常见的拟牛顿法有BFGS等.

下一节我们将使用梯度下降法和牛顿法, 解决Rosenbrock Function, 让大家更直观的看到两种方法的区别.

参考链接

• 刘浩洋. 最优化: 建模, 算法与理论. 高等教育出版社, 2020.

---

🏎️自动驾驶小白说官网：https://www.helloxiaobai.cn