====== 第五章 共轭梯度法 ======

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

共轭梯度法（Conjugate Gradient Method）是求解大规模对称正定线性方程组和二次优化问题的高效算法。与最速下降法相比，它具有更快的收敛速度；与Newton法相比，它不需要存储和计算Hesse矩阵。本章介绍共轭方向、共轭梯度法的原理及其收敛性分析。

===== 5.1 共轭方向 =====

==== 5.1.1 共轭的定义 ====

**定义 5.1**（Q-共轭/共轭）

设 $Q$ 是 $n \times n$ 对称正定矩阵。非零向量 $\mathbf{d}_1, \mathbf{d}_2, \ldots, \mathbf{d}_k$ 称为**Q-共轭**（或关于 $Q$ 共轭），如果：
$$\mathbf{d}_i^T Q \mathbf{d}_j = 0, \quad \forall i \neq j$$

**性质**：
  - Q-共轭向量组线性无关
  - 最多有 $n$ 个两两Q-共轭的非零向量

**定理 5.1**

若 $\mathbf{d}_1, \ldots, \mathbf{d}_n$ 是Q-共轭向量组，则它们构成 $\mathbb{R}^n$ 的一组基。

==== 5.1.2 共轭方向法的原理 ====

考虑二次优化问题：
$$\min f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T Q \mathbf{x} - \mathbf{b}^T \mathbf{x}$$

**定理 5.2**（共轭方向法的基本定理）

设 $\mathbf{d}_0, \mathbf{d}_1, \ldots, \mathbf{d}_{n-1}$ 是Q-共轭向量组。从任意 $\mathbf{x}_0$ 出发，按
$$\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_k$$

其中 $\alpha_k$ 是精确线搜索步长，则：
1. $\nabla f(\mathbf{x}_k)^T \mathbf{d}_j = 0$，$j = 0, 1, \ldots, k-1$
2. 至多 $n$ 步收敛到最优解 $\mathbf{x}^*$

**证明**：由精确线搜索，$\nabla f(\mathbf{x}_{k+1})^T \mathbf{d}_k = 0$。

对二次函数，$\nabla f(\mathbf{x}_{k+1}) = Q\mathbf{x}_{k+1} - \mathbf{b} = \nabla f(\mathbf{x}_k) + \alpha_k Q\mathbf{d}_k$。

对 $j < k$：
$$\nabla f(\mathbf{x}_{k+1})^T \mathbf{d}_j = \nabla f(\mathbf{x}_k)^T \mathbf{d}_j + \alpha_k \mathbf{d}_k^T Q \mathbf{d}_j = 0 + 0 = 0$$

（归纳假设 + Q-共轭性质）

因此 $\nabla f(\mathbf{x}_n)^T \mathbf{d}_j = 0$，$j = 0, \ldots, n-1$。由于 $\{\mathbf{d}_j\}$ 是基，$\nabla f(\mathbf{x}_n) = \mathbf{0}$。$\square$

===== 5.2 共轭梯度法 =====

==== 5.2.1 算法思想 ====

共轭梯度法的核心思想是：
1. 第1步沿负梯度方向搜索
2. 后续各步的搜索方向是当前负梯度与前面搜索方向的线性组合，使得新方向与前面所有方向Q-共轭

==== 5.2.2 Fletcher-Reeves (F-R) 公式 ====

**算法 5.1**（F-R共轭梯度法）

  - **输入**：$Q$，$\mathbf{b}$，初始点 $\mathbf{x}_0$
  - **输出**：最优解 $\mathbf{x}^*$

  1. $\mathbf{g}_0 = Q\mathbf{x}_0 - \mathbf{b}$，$\mathbf{d}_0 = -\mathbf{g}_0$
  2. **for** $k = 0, 1, 2, \ldots, n-1$ **do**
     - **if** $\|\mathbf{g}_k\| = 0$ **then** **break**
     - $\alpha_k = \frac{\mathbf{g}_k^T \mathbf{g}_k}{\mathbf{d}_k^T Q \mathbf{d}_k}$
     - $\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_k$
     - $\mathbf{g}_{k+1} = \mathbf{g}_k + \alpha_k Q \mathbf{d}_k$
     - $\beta_{k+1} = \frac{\mathbf{g}_{k+1}^T \mathbf{g}_{k+1}}{\mathbf{g}_k^T \mathbf{g}_k}$
     - $\mathbf{d}_{k+1} = -\mathbf{g}_{k+1} + \beta_{k+1} \mathbf{d}_k$
  3. **return** $\mathbf{x}_{k+1}$

==== 5.2.3 Polak-Ribière (P-R) 公式 ====

另一种常用的 $\beta_k$ 计算公式：
$$\beta_{k+1}^{PR} = \frac{\mathbf{g}_{k+1}^T (\mathbf{g}_{k+1} - \mathbf{g}_k)}{\mathbf{g}_k^T \mathbf{g}_k}$$

对于二次函数，F-R和P-R公式等价；对于非二次函数，P-R通常表现更好。

==== 5.2.4 非线性共轭梯度法 ====

**算法 5.2**（非线性共轭梯度法）

  - **输入**：$f$，$\nabla f$，初始点 $\mathbf{x}_0$，精度 $\varepsilon$
  - **输出**：近似最优解

  1. $\mathbf{g}_0 = \nabla f(\mathbf{x}_0)$，$\mathbf{d}_0 = -\mathbf{g}_0$
  2. **for** $k = 0, 1, 2, \ldots$ **do**
     - **if** $\|\mathbf{g}_k\| < \varepsilon$ **then** **break**
     - 线搜索求 $\alpha_k$（满足Wolfe条件）
     - $\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_k$
     - $\mathbf{g}_{k+1} = \nabla f(\mathbf{x}_{k+1})$
     - 计算 $\beta_{k+1}$（F-R或P-R公式）
     - $\mathbf{d}_{k+1} = -\mathbf{g}_{k+1} + \beta_{k+1} \mathbf{d}_k$
     - **if** $k+1 \equiv 0 \pmod n$ **then** $\mathbf{d}_{k+1} = -\mathbf{g}_{k+1}$（重启）
  3. **return** $\mathbf{x}_{k+1}$

**重启策略**：每 $n$ 步将搜索方向重置为负梯度，保证全局收敛性。

===== 5.3 收敛性分析 =====

==== 5.3.1 二次函数的收敛性 ====

**定理 5.3**

对于 $n$ 维二次函数，共轭梯度法至多 $n$ 步收敛到精确解。

**定理 5.4**

共轭梯度法的收敛速度与 $Q$ 的谱分布有关。设 $Q$ 有 $m$ 个不同的特征值，则共轭梯度法至多 $m$ 步收敛。

==== 5.3.2 收敛速度估计 ====

**定理 5.5**

对于二次函数，共轭梯度法满足：
$$\|\mathbf{x}_k - \mathbf{x}^*\|_Q \leq 2\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^k \|\mathbf{x}_0 - \mathbf{x}^*\|_Q$$

其中 $\kappa = \lambda_{\max}/\lambda_{\min}$ 是条件数。

与最速下降法的比较：
  - 最速下降：收敛因子 $\frac{\kappa-1}{\kappa+1}$
  - 共轭梯度：收敛因子 $\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}$

当 $\kappa = 100$：最速下降 $0.98$，共轭梯度 $0.82$

==== 5.3.3 非线性问题的收敛性 ====

**定理 5.6**

设 $f$ 二阶连续可微，水平集有界，采用Wolfe条件线搜索。则：
1. F-R方法：$\liminf_{k \rightarrow \infty} \|\nabla f(\mathbf{x}_k)\| = 0$
2. P-R方法（适当修正后）：全局收敛

===== 5.4 预条件共轭梯度法 =====

==== 5.4.1 预条件思想 ====

共轭梯度法的收敛速度与 $\sqrt{\kappa}$ 有关。通过**预条件**降低条件数，可加速收敛。

设 $M$ 是对称正定矩阵（预条件子），解等价问题：
$$M^{-1/2} Q M^{-1/2} \tilde{\mathbf{x}} = M^{-1/2} \mathbf{b}$$

==== 5.4.2 预条件共轭梯度算法 ====

**算法 5.3**（预条件共轭梯度法）

  1. $\mathbf{g}_0 = Q\mathbf{x}_0 - \mathbf{b}$，$\mathbf{h}_0 = M^{-1}\mathbf{g}_0$，$\mathbf{d}_0 = -\mathbf{h}_0$
  2. **for** $k = 0, 1, \ldots$ **do**
     - $\alpha_k = \frac{\mathbf{g}_k^T \mathbf{h}_k}{\mathbf{d}_k^T Q \mathbf{d}_k}$
     - $\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_k$
     - $\mathbf{g}_{k+1} = \mathbf{g}_k + \alpha_k Q\mathbf{d}_k$
     - $\mathbf{h}_{k+1} = M^{-1}\mathbf{g}_{k+1}$
     - $\beta_{k+1} = \frac{\mathbf{g}_{k+1}^T \mathbf{h}_{k+1}}{\mathbf{g}_k^T \mathbf{h}_k}$
     - $\mathbf{d}_{k+1} = -\mathbf{h}_{k+1} + \beta_{k+1} \mathbf{d}_k$

**常用预条件子**：
  - Jacobi预条件：$M = \text{diag}(Q)$
  - 不完全Cholesky分解
  - 多重网格预条件

===== 5.5 例题详解 =====

**例 5.1**

用F-R共轭梯度法求解：
$$\min f(x, y, z) = x^2 + 2y^2 + 3z^2 + 2xy + 2xz$$

初始点 $\mathbf{x}_0 = (1, 1, 1)^T$。

**解**：

$Q = \begin{bmatrix} 2 & 2 & 2 \\ 2 & 4 & 0 \\ 2 & 0 & 6 \end{bmatrix}$，$\mathbf{g}_0 = Q\mathbf{x}_0 = \begin{bmatrix} 6 \\ 6 \\ 8 \end{bmatrix}$

**第0步**：$\mathbf{d}_0 = -\mathbf{g}_0 = \begin{bmatrix} -6 \\ -6 \\ -8 \end{bmatrix}$

$\alpha_0 = \frac{\mathbf{g}_0^T\mathbf{g}_0}{\mathbf{d}_0^T Q \mathbf{d}_0} = \frac{136}{...} = ...$

继续计算...

===== 5.6 习题 =====

**理论题**

1. 证明：Q-共轭的非零向量组线性无关。

2. 证明：对于二次函数，F-R公式和P-R公式等价。

3. 证明共轭梯度法的展开子空间性质：$\text{span}\{\mathbf{g}_0, \ldots, \mathbf{g}_k\} = \text{span}\{\mathbf{g}_0, Q\mathbf{g}_0, \ldots, Q^k\mathbf{g}_0\}$。

4. 解释为什么共轭梯度法每 $n$ 步需要重启。

**计算题**

5. 用F-R共轭梯度法求解：
   $$\min f(x, y) = 2x^2 + y^2 + 2xy - 6x - 2y$$
   初始点 $(0, 0)$。

6. 比较最速下降法和共轭梯度法在问题 $f(x, y) = 10x^2 + y^2$ 上的收敛速度。

7. 设 $Q = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}$，构造两个Q-共轭向量。

**应用题**

8. 共轭梯度法在深度学习中的应用：讨论为什么批量优化中很少直接使用共轭梯度法。

9. 设计一个数值实验，比较不同 $\beta$ 计算公式（F-R、P-R、Hestenes-Stiefel）在非二次函数上的表现。

---

*本章完*