共轭方向法与共轭梯度法

最速下降每次只保证当前最陡，后一步可能抵消前一步的进展。共轭方向法选择一组在二次型几何下互不干扰的方向。

$Q$-共轭

对对称正定矩阵 $Q$，若

$$d_i^TQd_j=0,\qquad i\ne j,$$

称 $d_i,d_j$ 关于 $Q$ 共轭。它就是在内积

$$\langle u,v\rangle_Q=u^TQv$$

下正交。

非零两两共轭方向必线性无关，因此在 $n$ 维空间最多有 $n$ 个。

有限步终止

考虑

$$f(x)=\frac12x^TQx-b^Tx,\qquad Q\succ0.$$

沿一组 $Q$-共轭方向依次作精确一维搜索：

$$x_{k+1}=x_k+\alpha_kd_k,\qquad \alpha_k=-\frac{g_k^Td_k}{d_k^TQd_k}.$$

由于后续方向与先前方向共轭，后续移动不会破坏先前已经最小化的分量。精确算术下，至多 $n$ 步到达唯一最优解。

共轭梯度法

它不预先存储整组方向，而递推生成：

$$d_0=-g_0,$$ $$\alpha_k=-\frac{g_k^Td_k}{d_k^TQd_k},\qquad x_{k+1}=x_k+\alpha_kd_k,$$ $$g_{k+1}=Qx_{k+1}-b,$$ $$d_{k+1}=-g_{k+1}+\beta_kd_k.$$

为满足 $d_{k+1}^TQd_k=0$，可取

$$\beta_k=\frac{g_{k+1}^Tg_{k+1}}{g_k^Tg_k}$$

（Fletcher–Reeves 形式；在精确二次与精确搜索下与其他常见形式等价）。

重要正交关系

精确算术下：

$$g_i^Tg_j=0,\quad i\ne j,$$ $$d_i^TQd_j=0,\quad i\ne j,$$

且 $x_k$ 是仿射 Krylov 子空间

$$x_0+\operatorname{span}\{g_0,Qg_0,\ldots,Q^{k-1}g_0\}$$

中的最优点。

数值现实

浮点舍入会逐渐破坏正交与共轭，所以实际可能超过 $n$ 步，常在梯度小或迭代一定次数后重启。预条件矩阵 $M\approx Q$ 可把问题变得更“圆”，显著降低有效条件数。

非线性共轭梯度把 $Q$ 换成局部信息，仍用线搜索与 $\beta_k$ 递推，但不再具有严格 $n$ 步终止。

考试要点

• 普通正交是 $d_i^Td_j=0$，共轭是 $d_i^TQd_j=0$。
• 求未知共轭方向就是解若干线性方程，再任选非零尺度。
• 有限步结论要求正定二次函数、精确一维搜索和精确算术。
• 共轭梯度每步只需矩阵向量乘，适合大规模稀疏正定线性方程组。