我很好奇优化算法(无论是单纯形、主动集二次规划、内点顺序等)是否会由于数值错误以及如何避免它们而失败。但我在网上找不到相关文献。似乎人们主要研究各种矩阵分解方法的数值稳定性和求解偏微分方程。所以我的问题是,为什么没有那么多关于迭代优化技术的研究?你能推荐一些吗?
优化算法数值稳定性的文献
大多数优化算法都被要求收敛到远离机器精度的容差,并且其中许多算法的收敛速度足够慢,以至于要求正确的机器精度答案的成本非常高。因此,与所有其他误差源相比,数值舍入不会对它们产生太大影响。
考虑与其他示例的差异:各种矩阵分解的数值稳定性很重要,因为您希望答案对机器精度正确,并且您希望答案的数学属性也满足机器精度(例如,在分解后你真的希望)。因此,当它们用作其他应用程序的构建块时,舍入会严重影响它们的有用性,例如数值优化。
求解 PDE 的方法的稳定性与这个词的含义并不完全相同,它更像是数学意义上的不因扰动而呈指数发散,其中可能包括舍入误差,但通常只包括扰动。(PDE 方法通常也有相当粗的公差,根本不接近机器精度。)这与矩阵分解不同:由于舍入误差的累积,数值不稳定的方法可能会产生不准确的结果,即使存在是一个对输入数据中的扰动不是特别敏感的单一答案——这种方法甚至不会是向后稳定的。
让我们看一下优化简单无约束凸二次函数的最简单情况. 在这种情况下,优化方法只是求解线性方程组的一个花哨的词. 众所周知,如果矩阵的条件数,求解这样的线性方程组不是很稳定炸毁。并且对于求解这种线性方程组的稳定性有很多研究。
这个想法推广到其他更高级的优化方法。原因是无论这些方法多么花哨,它们都是由线性代数步骤组成的,例如求解线性方程组。因此,它们与那些线性代数方法一样敏感,甚至更多。
如果您想要关于计算迭代中的错误的方法稳定性的更严格的结果,您可以查找这些方法的不精确版本。例如,我刚刚google了不精确内点法,发现这篇论文:https ://link.springer.com/article/10.1023/A:1022663100715 。您可以对您选择的其他优化方法执行相同的操作。请注意,不精确的方法分析通常假设您可以找到具有特定精度的迭代。但在实践中,由于我们之前讨论过的线性代数问题,例如不良条件,找到具有预先指定精度的迭代可能具有挑战性。