非线性共轭梯度法

非线性共轭梯度法是一种用于求解无约束非线性优化问题的迭代算法。它通过将线性共轭梯度法的思想推广到非线性函数，在每一步利用函数的梯度信息构造共轭方向，从而实现对目标函数的高效优化。

1. 基本问题形式

   • 考虑无约束优化问题：min f(x)，其中 f: Rⁿ → R 是连续可微的非线性函数
   • 与线性系统不同，非线性函数的海塞矩阵不是常数，这导致共轭方向的构造更加复杂
   • 算法目标：找到使 f(x) 局部最小的点 x*

2. 核心思想：共轭方向

   • 共轭方向定义：对于正定矩阵 A，若方向集 {d₀, d₁, ..., dₖ} 满足 dᵢᵀAdⱼ = 0 (i≠j)，则称这些方向关于 A 共轭
   • 在非线性情形中，A 通常取当前点处的海塞矩阵 ∇²f(xₖ) 的近似
   • 共轭方向的重要性：沿共轭方向搜索可保证在 n 步内找到二次函数的极小点

3. 算法框架

   • 初始化：选择初始点 x₀，计算梯度 g₀ = ∇f(x₀)，设初始搜索方向 d₀ = -g₀
   • 迭代步骤（对 k=0,1,2,...）：
     a. 线搜索：沿方向 dₖ 精确或非精确搜索，求步长 αₖ = argmin f(xₖ + αdₖ)
     b. 更新迭代点：xₖ₊₁ = xₖ + αₖdₖ
     c. 计算新梯度：gₖ₊₁ = ∇f(xₖ₊₁)
     d. 计算共轭参数 βₖ（不同公式对应不同变体）
     e. 构造新搜索方向：dₖ₊₁ = -gₖ₊₁ + βₖdₖ

4. 重要参数 βₖ 的计算公式

   • FR (Fletcher-Reeves)：βₖ = (gₖ₊₁ᵀgₖ₊₁)/(gₖᵀgₖ)
   • PRP (Polak-Ribière-Polyak)：βₖ = (gₖ₊₁ᵀ(gₖ₊₁ - gₖ))/(gₖᵀgₖ)
   • HS (Hestenes-Stiefel)：βₖ = (gₖ₊₁ᵀ(gₖ₊₁ - gₖ))/(dₖᵀ(gₖ₊₁ - gₖ))
   • DY (Dai-Yuan)：βₖ = (gₖ₊₁ᵀgₖ₊₁)/(dₖᵀ(gₖ₊₁ - gₖ))

5. 收敛性分析

   • 强 Wolfe 条件：为保证全局收敛，线搜索需满足：
     f(xₖ + αₖdₖ) ≤ f(xₖ) + c₁αₖgₖᵀdₖ (充分下降)
     |∇f(xₖ + αₖdₖ)ᵀdₖ| ≤ c₂|gₖᵀdₖ| (曲率条件)
     其中 0 < c₁ < c₂ < 1
   • FR 方法在强 Wolfe 条件下具有全局收敛性
   • PRP 方法通常表现更好但理论保证较弱

6. 重启策略

   • 周期性重启：每 n 次迭代后重置 βₖ = 0，即 dₖ = -gₖ
   • 梯度正交性重启：当 |gₖ₊₁ᵀgₖ| ≥ 0.2||gₖ₊₁||² 时重启
   • 重启目的：克服有限精度计算导致的共轭性损失，提高数值稳定性

7. 实际应用考虑

   • 预处理技术：使用预处理矩阵 M 改善条件数，将问题转化为 min f(M^{-1/2}x)
   • 非精确线搜索：实际中常使用 Wolfe 条件或 Armijo 条件，而非精确最小化
   • 大规模问题优势：仅需存储向量，内存需求 O(n)，适合高维问题

非线性共轭梯度法因其较低的内存需求和良好的收敛性能，在机器学习、信号处理和大规模科学计算中得到了广泛应用。