最优化抄书笔记:共轭梯度法(2)

发布网友发布时间：2024-10-03 14:09

共1个回答

热心网友时间：2024-10-27 19:27

从线性方程组的视角出发，我们将重新探讨共轭梯度法，更深入地理解其核心原理。

考虑线性方程组 [公式]，其中 [公式] 是对称正定矩阵，解决策略是将其转化为优化问题：寻找使 [公式] 最小化的 [公式]。传统的最速下降法在条件数大的情况下可能效果不佳，因此，引入子空间方法，逐步扩大优化范围，形成嵌套的Krylov子空间序列 [公式]。

初始的子空间 [公式] 必须包含梯度 [公式]，随后的子空间需依次包含后续梯度，形成Krylov子空间的序列。Lanczos三对角化是关键步骤，它用于寻找这些子空间的正交基，生成的列向量 [公式] 形成了优化问题的特征。

共轭梯度法的初步版本由此构建，通过三对角矩阵的分解，找到极小值点 [公式]。算法步骤包括初始化、更新搜索方向和步长，直到达到终止条件。然而，对于大型稀疏矩阵，关键在于设计不依赖已计算Lanczos向量的方法，从而简化计算。

最后，我们得到了Lanczos共轭梯度法，它更适用于大型稀疏矩阵，通过调整搜索方向和步长计算，实现了优化过程。这种方法不仅保持了梯度的共轭性，还引入了残差作为终止准则，使得算法更为精确。

除了对称问题，共轭梯度法还可扩展到非对称问题，通过两种转化方法（CGNR和CGNE），但这需要对原方法进行适当修改，详细内容可参考文献 [1] 的P589页。

至此，我们学习了下降算法的基本策略和理论，包括最速下降法、牛顿法等，以及共轭梯度法这一关键优化工具。下篇笔记将转向无约束优化的信赖域方法，它将在球内部求解近似的二次函数极小化问题。