第五章 共轭梯度法

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

定义 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$$

性质：

1. Q-共轭向量组线性无关
2. 最多有 $n$ 个两两Q-共轭的非零向量

定理 5.1

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

考虑二次优化问题： $$\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$

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

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

1. 输入：$Q$，$\mathbf{b}$，初始点 $\mathbf{x}_0$
2. 输出：最优解 $\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}$

另一种常用的 $\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（非线性共轭梯度法）

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

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

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

定理 5.4

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

定理 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}$ 是条件数。

与最速下降法的比较：

1. 最速下降：收敛因子 $\frac{\kappa-1}{\kappa+1}$
2. 共轭梯度：收敛因子 $\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}$

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

定理 5.6

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

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

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

算法 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$

常用预条件子：

1. Jacobi预条件：$M = \text{diag}(Q)$
2. 不完全Cholesky分解
3. 多重网格预条件

例 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}{…} = …$

继续计算…

理论题

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）在非二次函数上的表现。

—

*本章完*