====== 第四章 梯度下降法 ======

===== 本章导读 =====

梯度下降法（Gradient Descent）是最基本、最常用的优化算法之一。其核心思想是沿目标函数梯度的反方向（即函数值下降最快的方向）进行搜索。本章详细介绍最速下降法的原理、算法步骤、收敛性分析，以及改进方法。

===== 4.1 最速下降法 =====

==== 4.1.1 算法原理 ====

由第二章可知，$-\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.2 精确线搜索的最速下降法 ====

**算法 4.1**（最速下降法—精确线搜索）

  - **输入**：目标函数 $f$，梯度 $\nabla f$，初始点 $\mathbf{x}_0$，精度 $\varepsilon > 0$
  - **输出**：近似最优解 $\mathbf{x}^*$

  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$

==== 4.1.3 二次函数的精确解 ====

对于二次目标函数：
$$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次迭代**：
  - $\nabla f(2, 1) = \begin{bmatrix} 4 \\ 8 \end{bmatrix}$，$\mathbf{d}_0 = \begin{bmatrix} -4 \\ -8 \end{bmatrix}$
  - $\alpha_0 = \frac{\mathbf{d}_0^T \mathbf{d}_0}{\mathbf{d}_0^T Q \mathbf{d}_0} = \frac{16+64}{32+512} = \frac{80}{544} = \frac{5}{34}$
  - $\mathbf{x}_1 = \begin{bmatrix} 2 \\ 1 \end{bmatrix} - \frac{5}{34} \begin{bmatrix} 4 \\ 8 \end{bmatrix} = \begin{bmatrix} 2 - \frac{10}{17} \\ 1 - \frac{20}{17} \end{bmatrix} = \begin{bmatrix} \frac{24}{17} \\ -\frac{3}{17} \end{bmatrix}$

**第2次迭代**：
  - $\nabla f(\mathbf{x}_1) = \begin{bmatrix} \frac{48}{17} \\ -\frac{24}{17} \end{bmatrix}$，$\mathbf{d}_1 = \begin{bmatrix} -\frac{48}{17} \\ \frac{24}{17} \end{bmatrix}$
  - 继续计算...

===== 4.2 收敛性分析 =====

==== 4.2.1 全局收敛性 ====

**定理 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.2.2 二次函数的收敛速度 ====

**定理 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}$。

**说明**：
  - 最速下降法是**线性收敛**的
  - 收敛速度取决于条件数 $\kappa$：条件数越大，收敛越慢
  - 当 $\kappa \gg 1$（病态问题），收敛极其缓慢

**例 4.2**（锯齿现象）

对于 $f(x, y) = x^2 + 100y^2$，条件数 $\kappa = 100$。

最速下降法的迭代轨迹呈锯齿状，在 narrow valley 中来回震荡，收敛极慢。

==== 4.2.3 收敛因子分析 ====

收敛因子 $r = \left(\frac{\kappa - 1}{\kappa + 1}\right)^2$：
  - $\kappa = 1$：$r = 0$（一次收敛）
  - $\kappa = 10$：$r \approx 0.67$
  - $\kappa = 100$：$r \approx 0.96$
  - $\kappa = 1000$：$r \approx 0.996$

要达到精度 $\varepsilon$，所需迭代次数约为 $O(\kappa \log(1/\varepsilon))$。

===== 4.3 改进的梯度方法 =====

==== 4.3.1 固定步长梯度下降 ====

**算法**：$\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}}$

==== 4.3.2 带动量的梯度下降 ====

**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)$ 累积历史梯度方向，有助于加速收敛和逃离局部极小。

==== 4.3.3 Nesterov加速梯度 ====

**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)$（对于凸函数）。

==== 4.3.4 自适应学习率方法 ====

**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.4 收敛性定理 =====

==== 4.4.1 精确线搜索的收敛性 ====

**定理 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.4.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}$。

===== 4.5 应用：机器学习中的梯度下降 =====

==== 4.5.1 批量梯度下降（BGD） ====

$$\mathbf{x}_{k+1} = \mathbf{x}_k - \frac{\alpha_k}{N} \sum_{i=1}^N \nabla f_i(\mathbf{x}_k)$$

每次迭代使用全部数据，梯度估计准确但计算量大。

==== 4.5.2 随机梯度下降（SGD） ====

$$\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha_k \nabla f_{i_k}(\mathbf{x}_k)$$

每次迭代随机选一个样本，计算快但梯度噪声大。

==== 4.5.3 小批量梯度下降（Mini-batch GD） ====

$$\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.6 例题详解 =====

**例 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**：
  - $\mathbf{d}_0 = \begin{bmatrix} 4 \\ 2 \end{bmatrix}$
  - 一维搜索：$\phi(\alpha) = f(4\alpha, 2\alpha)$
  - $\phi'(\alpha) = 0$ 得 $\alpha_0 = \frac{5}{22}$
  - $\mathbf{x}_1 = \begin{bmatrix} 10/11 \\ 5/11 \end{bmatrix}$

继续迭代2次...

===== 4.7 习题 =====

**理论题**

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加速梯度法，比较它们的收敛速度。

---

*本章完*