2

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

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

有人可以帮我区分那里的各种 LP 包吗？我并不像速度（对于大量约束）、高精度算术和热启动那样关心用户友好性。

谢谢！

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

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

  • \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。

4

3 回答 3

2

  • 至于 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

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

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

编辑：

对非标准表示法感到抱歉——我希望我可以像在 MathOverflow.net 上那样输入 LaTeX。（顺便说一句，你可以尝试把这个贴在那里——我认为那里的数学家会对这个问题感兴趣）

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

所以你的方法是在（2，inf]中离散y的问题。我猜你正在选择一个非常大的数字来表示inf和一个精细的离散化网格。Oooo棘手。我想离散化可能是你最好的选择。也许做真实分析的人有想法。

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

于 2010-07-24T18:42:13.370 回答
1

我遇到了类似的问题。我在网上搜索了一下，刚才发现这个问题可能被归类为“半无限”问题。MATLAB 有解决这类问题的工具（函数“fseminf”）。但我没有仔细检查过这个。肯定有人遇到过这样的问题。

于 2012-02-22T23:09:13.017 回答
0

您不应该使用 LP 求解器并自己进行离散化。通过使用一个不错的通用凸求解器，您可以做得更好。例如，查看 cvxopt。这可以在您的约束中处理各种不同的函数，或者允许您编写自己的函数。这比尝试自己进行线性化要好得多。

至于热启动，它对于 LP 比一般凸程序更有意义。虽然如果您自己手动编写整个算法，热启动可能很有用，但您通常仍然需要几个牛顿步骤，因此收益并不那么显着。热启动的大部分好处来自于诸如活动集方法之类的东西，这些方法大多仅用于 LP。

于 2010-04-28T04:56:57.687 回答