梯度下降法（Gradient Descent）是最基本、最常用的优化算法之一。其核心思想是沿目标函数梯度的反方向（即函数值下降最快的方向）进行搜索。本章详细介绍最速下降法的原理、算法步骤、收敛性分析，以及改进方法。
由第二章可知，$-\nabla f(\mathbf{x})$ 是函数值下降最快的方向。最速下降法（Steepest Descent Method）正是基于这一性质设计的。
基本迭代格式： $$\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha_k \nabla f(\mathbf{x}_k)$$
其中步长 $\alpha_k$ 可通过精确一维搜索或不精确线搜索确定。
算法 4.1（最速下降法—精确线搜索）
1. $k = 0$
2. **while** $\|\nabla f(\mathbf{x}_k)\| > \varepsilon$ **do**
- 计算搜索方向：$\mathbf{d}_k = -\nabla f(\mathbf{x}_k)$
- 一维搜索求步长：$\alpha_k = \arg\min_{\alpha > 0} f(\mathbf{x}_k + \alpha \mathbf{d}_k)$
- 更新迭代点：$\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_k$
- $k = k + 1$
3. **return** $\mathbf{x}_k$
对于二次目标函数： $$f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T Q \mathbf{x} - \mathbf{b}^T \mathbf{x}$$
其中 $Q$ 对称正定，精确线搜索的步长有闭式解。
定理 4.1
设 $f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T Q \mathbf{x} - \mathbf{b}^T \mathbf{x}$，$\mathbf{d}_k = -\nabla f(\mathbf{x}_k) = \mathbf{b} - Q\mathbf{x}_k$。则精确线搜索的最优步长为： $$\alpha_k = \frac{\mathbf{d}_k^T \mathbf{d}_k}{\mathbf{d}_k^T Q \mathbf{d}_k}$$
证明：令 $\phi(\alpha) = f(\mathbf{x}_k + \alpha \mathbf{d}_k)$，求 $\phi'(\alpha) = 0$： $$\phi'(\alpha) = \nabla f(\mathbf{x}_k + \alpha \mathbf{d}_k)^T \mathbf{d}_k = (Q(\mathbf{x}_k + \alpha \mathbf{d}_k) - \mathbf{b})^T \mathbf{d}_k = 0$$
$$(Q\mathbf{x}_k - \mathbf{b})^T \mathbf{d}_k + \alpha \mathbf{d}_k^T Q \mathbf{d}_k = -\mathbf{d}_k^T \mathbf{d}_k + \alpha \mathbf{d}_k^T Q \mathbf{d}_k = 0$$
解得：$\alpha_k = \frac{\mathbf{d}_k^T \mathbf{d}_k}{\mathbf{d}_k^T Q \mathbf{d}_k}$。$\square$
例 4.1
用最速下降法求解： $$\min f(x, y) = x^2 + 4y^2$$
初始点 $(x_0, y_0) = (2, 1)$。
解：
$Q = \begin{bmatrix} 2 & 0
0 & 8 \end{bmatrix}$，$\nabla f(x, y) = \begin{bmatrix} 2x
8y \end{bmatrix}$
第1次迭代：
第2次迭代：
定理 4.2
设 $f$ 连续可微且有下界，$\nabla f$ Lipschitz连续。若采用Wolfe条件的线搜索，则最速下降法产生的序列满足： $$\lim_{k \rightarrow \infty} \|\nabla f(\mathbf{x}_k)\| = 0$$
定理 4.3（Zoutendijk条件）
在上述条件下： $$\sum_{k=0}^{\infty} \cos^2 \theta_k \|\nabla f(\mathbf{x}_k)\|^2 < \infty$$
其中 $\cos \theta_k = \frac{-\nabla f(\mathbf{x}_k)^T \mathbf{d}_k}{\|\nabla f(\mathbf{x}_k)\| \|\mathbf{d}_k\|}$。对于最速下降法，$\cos \theta_k = 1$。
定理 4.4
对于 $f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T Q \mathbf{x} - \mathbf{b}^T \mathbf{x}$，$Q$ 的特征值为 $0 < \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$，最速下降法满足： $$f(\mathbf{x}_{k+1}) - f(\mathbf{x}^*) \leq \left(\frac{\lambda_n - \lambda_1}{\lambda_n + \lambda_1}\right)^2 (f(\mathbf{x}_k) - f(\mathbf{x}^*))$$
或等价地： $$\|\mathbf{x}_{k+1} - \mathbf{x}^*\|_Q^2 \leq \left(\frac{\kappa - 1}{\kappa + 1}\right)^2 \|\mathbf{x}_k - \mathbf{x}^*\|_Q^2$$
其中 $\kappa = \frac{\lambda_n}{\lambda_1}$ 是 $Q$ 的条件数，$\|\mathbf{x}\|_Q^2 = \mathbf{x}^T Q \mathbf{x}$。
说明：
例 4.2（锯齿现象）
对于 $f(x, y) = x^2 + 100y^2$，条件数 $\kappa = 100$。
最速下降法的迭代轨迹呈锯齿状，在 narrow valley 中来回震荡，收敛极慢。
收敛因子 $r = \left(\frac{\kappa - 1}{\kappa + 1}\right)^2$：
要达到精度 $\varepsilon$，所需迭代次数约为 $O(\kappa \log(1/\varepsilon))$。
算法：$\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha \nabla f(\mathbf{x}_k)$，$\alpha$ 固定。
收敛条件：对于 $f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^T Q \mathbf{x} - \mathbf{b}^T \mathbf{x}$，当 $0 < \alpha < \frac{2}{\lambda_{\max}}$ 时收敛。
最优固定步长：$\alpha^* = \frac{2}{\lambda_{\min} + \lambda_{\max}}$
Polyak动量： $$\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha \nabla f(\mathbf{x}_k) + \beta (\mathbf{x}_k - \mathbf{x}_{k-1})$$
或等价地： $$\mathbf{v}_{k+1} = \beta \mathbf{v}_k - \alpha \nabla f(\mathbf{x}_k)$$ $$\mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{v}_{k+1}$$
动量项 $\beta \in [0, 1)$ 累积历史梯度方向，有助于加速收敛和逃离局部极小。
NAG（Nesterov Accelerated Gradient）： $$\mathbf{y}_k = \mathbf{x}_k + \beta (\mathbf{x}_k - \mathbf{x}_{k-1})$$ $$\mathbf{x}_{k+1} = \mathbf{y}_k - \alpha \nabla f(\mathbf{y}_k)$$
Nesterov方法在计算梯度前先进行外推，具有最优的收敛速度 $O(1/k^2)$（对于凸函数）。
AdaGrad： $$\mathbf{r}_k = \mathbf{r}_{k-1} + \nabla f(\mathbf{x}_k) \odot \nabla f(\mathbf{x}_k)$$ $$\mathbf{x}_{k+1} = \mathbf{x}_k - \frac{\alpha}{\delta + \sqrt{\mathbf{r}_k}} \odot \nabla f(\mathbf{x}_k)$$
RMSProp： $$\mathbf{r}_k = \rho \mathbf{r}_{k-1} + (1-\rho) \nabla f(\mathbf{x}_k) \odot \nabla f(\mathbf{x}_k)$$
Adam（Adaptive Moment Estimation）： $$\mathbf{m}_k = \beta_1 \mathbf{m}_{k-1} + (1-\beta_1) \nabla f(\mathbf{x}_k) \quad \text{(一阶矩)}$$ $$\mathbf{v}_k = \beta_2 \mathbf{v}_{k-1} + (1-\beta_2) \nabla f(\mathbf{x}_k)^2 \quad \text{(二阶矩)}$$ $$\hat{\mathbf{m}}_k = \frac{\mathbf{m}_k}{1-\beta_1^k}, \quad \hat{\mathbf{v}}_k = \frac{\mathbf{v}_k}{1-\beta_2^k}$$ $$\mathbf{x}_{k+1} = \mathbf{x}_k - \frac{\alpha}{\sqrt{\hat{\mathbf{v}}_k} + \delta} \hat{\mathbf{m}}_k$$
定理 4.5
设 $f$ 二阶连续可微，水平集 $L = \{\mathbf{x} \mid f(\mathbf{x}) \leq f(\mathbf{x}_0)\}$ 有界，且 $f$ 在 $L$ 上满足： $$m\mathbf{I} \preceq \nabla^2 f(\mathbf{x}) \preceq M\mathbf{I}$$
则最速下降法线性收敛到最优解，收敛因子不超过 $\left(\frac{M-m}{M+m}\right)^2$。
定理 4.6
设 $f$ 下有界，$\nabla f$ Lipschitz连续。若线搜索满足Wolfe条件，则： $$\sum_{k=0}^{\infty} \|\nabla f(\mathbf{x}_k)\|^2 \cos^2 \theta_k < \infty$$
对于最速下降法，$\cos \theta_k = 1$，故 $\nabla f(\mathbf{x}_k) \rightarrow \mathbf{0}$。
$$\mathbf{x}_{k+1} = \mathbf{x}_k - \frac{\alpha_k}{N} \sum_{i=1}^N \nabla f_i(\mathbf{x}_k)$$
每次迭代使用全部数据，梯度估计准确但计算量大。
$$\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha_k \nabla f_{i_k}(\mathbf{x}_k)$$
每次迭代随机选一个样本，计算快但梯度噪声大。
$$\mathbf{x}_{k+1} = \mathbf{x}_k - \frac{\alpha_k}{|B_k|} \sum_{i \in B_k} \nabla f_i(\mathbf{x}_k)$$
折中方案，$B_k$ 是小批量样本集。
例 4.3
用最速下降法求解： $$\min f(x, y) = 2x^2 + y^2 + 2xy - 4x - 2y$$
初始点 $(0, 0)$，进行3次迭代。
解：
$\nabla f = \begin{bmatrix} 4x + 2y - 4
2y + 2x - 2 \end{bmatrix}$
迭代0：$\mathbf{x}_0 = \begin{bmatrix} 0
0 \end{bmatrix}$，$\nabla f_0 = \begin{bmatrix} -4
-2 \end{bmatrix}$
迭代1：
继续迭代2次…
理论题
1. 证明定理4.1：对于二次函数，精确线搜索的步长公式为 $\alpha_k = \frac{\mathbf{d}_k^T \mathbf{d}_k}{\mathbf{d}_k^T Q \mathbf{d}_k}$。
2. 设 $f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^T Q \mathbf{x} - \mathbf{b}^T \mathbf{x}$，$Q$ 的特征值为 $\lambda_1, \lambda_n$。证明固定步长梯度下降收敛当且仅当 $0 < \alpha < \frac{2}{\lambda_n}$。
3. 解释最速下降法的“锯齿现象”及其产生原因。
4. 证明：对于二次函数，相邻两次最速下降方向正交，即 $\nabla f(\mathbf{x}_{k+1})^T \nabla f(\mathbf{x}_k) = 0$。
计算题
5. 用最速下降法求解 $\min f(x, y) = x^2 + 9y^2$，初始点 $(9, 1)$，进行3次迭代（精确线搜索）。
6. 计算上题中 $f$ 的Hesse矩阵条件数，估计收敛到精度 $10^{-6}$ 所需的迭代次数。
7. 比较固定步长 $\alpha = 0.1$ 和最速下降法在问题 $f(x, y) = x^2 + 10y^2$ 上的表现。
编程题
8. 编写最速下降法程序，求解Rosenbrock函数：
$$f(x, y) = (1-x)^2 + 100(y-x^2)^2$$ 初始点 $(-1.2, 1)$，观察收敛行为。
9. 实现带动量的梯度下降和Nesterov加速梯度法，比较它们的收敛速度。
—
*本章完*