linear-programming - 对于大量约束和 "warm starts"，我应该使用哪个线性编程包

Question

关闭。这个问题不满足Stack Overflow guidelines .它目前不接受答案。












想改善这个问题吗？更新问题，使其成为 on-topic对于堆栈溢出。

6年前关闭。




Improve this question




我有一个“连续”线性规划问题，涉及最大化弯曲凸空间上的线性函数。在典型的 LP 问题中，凸空间是多面体，但在这种情况下，凸空间是分段弯曲的——也就是说，它有面、边和顶点，但边不直，面也不平.不是由有限数量的线性不等式指定，我有一个连续无限的数字。我目前正在通过用多面体逼近表面来处理这个问题，这意味着将连续无限的约束离散为非常大的有限数量的约束。

我也想知道答案在对潜在问题的小扰动下如何变化。因此，我希望能够根据附近的解决方案为求解器提供初始条件。我相信这种能力被称为“热启动”。

有人可以帮我区分各种 LP 包吗？我不太关心用户友好性，而不是速度(对于大量约束)、高精度算术和热启动。

谢谢!

编辑:从到目前为止与问答者的对话来看，我应该更清楚我要解决的问题。简化版本如下:

我有单个实变量 y 的 N 个固定函数 f_i(y)。我想找到最小化\sum_{i=1}^N x_i f_i(0) 的 x_i (i=1,...,N)，受约束:

\sum_{i=1}^N x_i f_i(1) = 1，和

\sum_{i=1}^N x_i f_i(y) >= 0 对于所有 y>2

更简洁地说，如果我们定义函数 F(y)=\sum_{i=1}^N x_i f_i(y)，那么我想在 F(1)=1 的条件下最小化 F(0)，并且F(y) 在整个区间 [2,infinity) 上为正。请注意，后一个正条件实际上是 无限 x_i 上的线性约束数，每个 y 一个。您可以将 y 视为一个标签——它不是一个优化变量。特定的 y_0 将我限制在 x_i 的空间中的半空间 F(y_0) >= 0。当我在 2 和无穷大之间改变 y_0 时，这些半空间不断变化，雕刻出弯曲的凸面形状。这个形状的几何形状隐含地(并且以一种复杂的方式)依赖于函数 f_i。

Answer 1

至于 LP 求解器推荐，最好的两个是 Gurobi 和 CPLEX(谷歌他们)。它们对学术用户免费，并且能够解决大规模问题。我相信他们拥有您需要的所有功能。您可以从影子价格(即拉格朗日乘数)中获得敏感性信息(对扰动)。

但我对你原来的问题更感兴趣。据我了解，它看起来像这样:

让 S = {1,2,...,N} 其中 N 是函数的总数。 y 是一个标量。 f_{i}:R^{1} -> R^{1}。

minimize sum{i in S} (x_{i} * f_{i}(0))
   x_{i}
s.t.
(1) sum {i in S} x_{i} * f_{i}(1) = 1
(2) sum {i in S} x_{i} * f_{i}(y) >= 0 for all y in (2,inf]

在我看来，您可能想尝试将这个问题作为凸 NLP 而不是 LP 来解决。像IPOPT这样的大规模内点NLP求解器应该能够轻松处理这些问题。我强烈建议尝试IPOPT http://www.coin-or.org/Ipopt

从数值的角度来看:对于凸问题，内点求解器不需要热启动；并且您不必担心事件集的组合循环。您所描述的“热启动”实际上扰乱了解决方案——这更类似于敏感性分析。在优化用语中，热启动通常意味着为求解器提供初始猜测——求解器将采用该猜测并最终得到相同的解决方案，这并不是您真正想要的。唯一的异常(exception)是，如果事件集随不同的初始猜测而变化——但对于具有唯一最优值的凸问题，这是不可能发生的。

如果您需要更多信息，我很乐意提供。

编辑:

抱歉非标准符号——我希望我能像在 MathOverflow.net 上一样输入 LaTeX。 (顺便说一句，您可以尝试将其发布在那里 - 我认为那里的数学家会对这个问题感兴趣)

啊现在我看到了“y > 2”。它实际上并不是一个优化约束，而是一个定义空间的间隔(我已经编辑了上面的描述)。我的错。我想知道您是否可以以某种方式将问题从无限转换/投影到有限？我现在想不出任何事情，但我只是想知道这是否可能。

所以你的方法是在 (2,inf] 中对 y 的问题进行离散化。我猜你选择了一个非常大的数字来表示 inf 和一个很好的离散化网格。太棘手了。我想离散化可能是你最好的选择。也许做实分析的人有想法。

我已经看到对涉及 Lyapunov 函数的问题做了类似的事情，其中​​有必要在凸包内的每个点强制执行一个属性。但那个空间是有限的。