数值最速下降法
1. 基础概念：优化问题的核心
数值最速下降法是一种用于求解无约束优化问题的迭代算法。无约束优化问题的目标是寻找一个多元函数 \(f(\mathbf{x})\) 的极小值点，其中 \(\mathbf{x}\) 是一个向量。我们的目标是找到 \(\mathbf{x}^*\)，使得对于所有 \(\mathbf{x}\)，有 \(f(\mathbf{x}^*) \leq f(\mathbf{x})\)。
2. 核心思想：沿着最陡峭的方向下降
想象你身处一个多变量的山谷（即函数曲面）中，目标是尽快到达谷底（最小值点）。最直观的策略是：在当前位置，环顾四周，找到坡度最陡峭的方向，然后沿着这个方向向下走一步。在数学上，函数 \(f(\mathbf{x})\) 在点 \(\mathbf{x}\) 处坡度最陡峭的方向由其梯度 \(\nabla f(\mathbf{x})\) 给出。梯度是一个向量，指向函数值增长最快的方向。因此，最速下降方向就是负梯度方向 \(-\nabla f(\mathbf{x})\)。
3. 算法步骤
基于上述思想，最速下降法的迭代过程可以分解为以下两个核心步骤：
- 步骤一：确定搜索方向
在第 \(k\) 次迭代中，我们处于点 \(\mathbf{x}_k\)。首先计算该点的梯度 \(\mathbf{g}_k = \nabla f(\mathbf{x}_k)\)。那么，当前的搜索方向 \(\mathbf{p}_k\) 就确定为负梯度方向：
\[ \mathbf{p}_k = -\nabla f(\mathbf{x}_k) = -\mathbf{g}_k \]
这个方向保证了在当前位置，函数值下降的瞬时速率是最快的。
- 步骤二：确定步长（一维线搜索）
方向确定后，我们需要决定沿着这个方向走多远。这一步被称为线搜索。我们定义一个新的单变量函数：
\[ \phi(\alpha) = f(\mathbf{x}_k + \alpha \mathbf{p}_k) \]
其中 \(\alpha > 0\) 是步长。我们的目标是找到一个最优的步长 \(\alpha_k\)，使得沿着这个方向函数值下降得最多，即：
\[ \alpha_k = \arg \min_{\alpha > 0} \phi(\alpha) = \arg \min_{\alpha > 0} f(\mathbf{x}_k + \alpha \mathbf{p}_k) \]
这种寻找精确最小值的线搜索称为**精确线搜索**。在实际应用中，为了节省计算量，也常使用**非精确线搜索**（如Wolfe条件、Armijo规则），只要求步长满足一定的下降条件，而不必是精确的最小值。
- 迭代更新
一旦确定了方向 \(\mathbf{p}_k\) 和步长 \(\alpha_k\)，我们就可以更新迭代点：
\[ \mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{p}_k \]
然后重复上述过程，直到满足收敛条件（例如，梯度的模 \(\|\nabla f(\mathbf{x}_{k+1})\|\) 小于一个给定的阈值）。
4. 一个简单的几何图像：锯齿形下降
最速下降法的一个典型特征是它的收敛路径呈“锯齿形”。这是因为每一步都严格沿着当前点的最速下降方向前进。当穿过山谷的“谷线”时，新的梯度方向会与旧的方向近乎垂直。这使得算法在接近最小值点时，进展变得非常缓慢，像锯齿一样来回震荡地逼近最优点。
5. 优缺点分析
-
优点：
- 实现简单：只需计算目标函数的梯度。
- 内存效率高：每次迭代只存储当前点和一个梯度向量，对于大规模问题很重要。
- 全局收敛性：对于性质良好的函数（如严格凸函数），它能保证从任意初始点开始都收敛到极小值。
-
缺点：
- 收敛速度慢：这是最速下降法最突出的问题。在极小值点附近，收敛速度是线性的，且收敛速率常数依赖于Hessian矩阵（函数二阶导数的矩阵）的条件数。当条件数很大时（即函数等高线是很扁的椭圆），收敛会极其缓慢。
- “锯齿”现象：如第4点所述，导致效率低下。
6. 与共轭梯度法的联系
正是由于最速下降法在收敛速度上的缺陷，催生了更高效的算法，如共轭梯度法。共轭梯度法通过巧妙地选择搜索方向，使得每个新的搜索方向与之前的所有搜索方向“共轭”，从而有效地抑制了锯齿现象，大大加快了收敛速度（对于二次函数，能在有限步内收敛）。可以认为，共轭梯度法是在最速下降法思想上的一个重要改进和升华。