C++ 中许多小二次问题的求解器建议

计算科学 优化 C++ 图书馆 二次规划
2021-12-18 03:18:34

我有一个 C++ 程序/模型,在某些部分已经使用 IPOPT(使用 ADOL-C 和 ColPack)来解决一些相当大的非线性问题。

现在在程序的另一部分,我需要解决大量(数万)个小二次问题。

如果您认为再次使用 IPOPT 应该更有效,我想听听您的建议,它对于大型通用非线性问题非常有用,但初始化似乎需要太多时间,或者如果您认为它应该更好使用专门的二次规划求解器,该求解器对小问题特别快(在这种情况下,名称将不胜感激)。

为了完整起见,我的二次问题是:

min: sum_i sum_j a_i,j x_i x_j
sub
sum_i x_i = 1
x_i >= 0
sum_i x_i b_i = c

i=j ~ 10

问题是独立的。

2个回答

如果您的问题很小,您可以尝试使用密集数据结构的简单求解器并使用堆栈分配(旧的 Fortran 代码)。IPOPT 使用稀疏数据结构,实际上,如果您的问题很小,初始化 IPOPT需要相对较长的时间。如果您遇到小问题,具有堆栈分配的旧 Fortran 代码速度非常快。

如果许可证对您来说不是问题,您可以查看Harwell Subroutine Library我相信VEO2 最小化二次函数,线性约束可能对你有好处。

另一个吸引人的选项是 MNHL 子例程:一般优化,需要来自PORT3的梯度和 Hessian 线性约束

连接 C++ 和 Fortran 代码既痛苦又无聊,但实际上并不是一门火箭科学。我相信这些旧的 Fortran 代码对于您的应用程序来说可能足够快。(从喜欢 C++ 的人那里得到它。)

如果性能是一个问题,我不会在您的二次程序上使用自动微分。相反,我会手动编写衍生代码。


我问:你的申请是什么?你怎么得到这么多小的二次程序?

OSQP似乎是一个不错的选择。

它的:

  1. 自由
  2. 没有外部依赖
  3. 允许您使用 Python 或其他几种语言来玩和开发模型
  4. 允许您在没有外部依赖项的情况下以 C 代码导出模型

然后可以使用您的 C++ 项目编译生成的 C 代码以获得非常好的性能。