最先进的活动集优化算法?

计算科学 线性代数 优化 数值分析 约束优化
2021-12-07 17:43:15

鉴于这样的问题:

min ||Exf|| s.t.
Gx0
Cx=d

并且假设矩阵是中等大小的(低至数千)和密集的,解决这个系统的最先进的技术是什么(想象在实时系统中使用)?最好使用诸如活动集算法之类的东西,而不是梯度下降。

我有一些经典书籍(例如:Numerical Methods for Least Squared ProblemsSolving Least Squares Problems)列出了一些算法,但它们已有数十年历史,专注于更简单问题的算法(从更复杂的形式转换)并且倾向于只掩盖重要的细节,如存储、缓存使用和数值考虑。

二次编程方面有一些资源(例如: Matlab 中的quadprod)。我订购了“实用优化”一书(列在 quadprod 的脚注中),看看它有哪些方法。但同样,它是从 80 年代开始的。

大多数谷歌搜索为最近的研究提供了点击,但它们往往集中在大型稀疏系统、梯度下降等内点方法,或两者​​兼而有之。

所以我很好奇对于密集的活动集风格算法,哪些方法被认为是现代的?

1个回答

通读 Nocedal 和 Wright 的《数值优化》一书,了解活动集方法的一般工作原理。更现代的变体使用 Kunisch 等人的原始对偶方法。预测哪些约束将/不会激活。