拟牛顿法中的线性系统

计算科学 牛顿法 共轭梯度 准牛顿
2021-12-07 00:12:43

我已经为我的问题实现了一个准牛顿方法,我使用了基于 Hessian 矩阵近似的方法。因此,每次迭代都有一个线性系统求解。我使用共轭梯度求解线性系统,并使用准牛顿矩阵的表示及其在有限内存方法中的使用中给出的紧凑表示得到矩阵向量积。我注意到线性系统的求解次数非常少,通常是 20 到 30 次。即使是非常大的问题(一百万个变量)也会发生这种情况。在使用 Quasi Newton 时通常会观察到这种情况吗?我可以想到这种快速收敛的一个可能原因。因为,我确保了准牛顿向量对的曲率条件,保证了 Hessian 近似是严格正定的,并且共轭梯度中的二次形式具有“良好”的形状。我不确定这是否足以解释正在发生的事情。

编辑:根据下面接受的答案,我有这个问题。Quasi Newton 方法中的情况非常有趣,可以证明线性系统可以在非常少的迭代次数内求解。是否有许多作品在这方面得到了有利的利用?

1个回答

这是一个众所周知的定理,共轭梯度保证收敛(精确算术)r+1身份加等级的步骤r矩阵,不管它的大小。在有限精度下,您会发现在最坏的情况下,CG 会在第一次几乎停滞不前r+1迭代,然后在之后的每次迭代中快速收敛到解决方案。

有限的记忆 Hessian 近似正是一个身份加秩r矩阵,其中r是您当前携带的向量的数量(可能是一个小的标量倍数)。因此 CG 保证在O(r)迭代。假设与 Hessian 矩阵的矩阵向量乘积被有效地执行,这是总时间复杂度O(nr2).

实际上,CG并不是实现准牛顿的最有效方式。您可以直接形成Hessian 逆的有限内存近似,而不是形成 Hessian 的有限内存近似,然后将其反转,使用的步骤不会比您一直执行的步骤更昂贵。然后每次迭代的矩阵求解被单个矩阵向量乘法替换,可以在O(nr)复杂。

所有这些陈述的证明都可以在任何关于非线性优化的标准教科书中找到,例如 Nocedal 和 Wright。