logo标签列表

线性规划：寻找所有最优顶点

julialinear-programmingjulia-jump
7
我想知道是否有一种好的方式（最好使用JuMP）来获取线性规划的所有最优解（如果有多个最优解的话）。
一个例子是，最小化两个概率分布之间的统计距离（科尔莫戈洛夫距离）。
min sum_{i=1}^{4} |P[i] - Q[i]| over free variable Q
P = [0.25,0.25,0.25,0.25]
sum_i P[i] = 1
Q[1] + Q[4] = 1
sum_i Q[i] = 1 -> Q[2],Q[3] = 0

请注意，我们可以将优化问题表述为线性规划问题，目标函数为：
min S >= sum_i S[i]
S[i] >= P[i]-Q[i]
S[i] >= Q[i]-P[i]

这个问题没有唯一解，相反最优解的子空间由以下组成。
Q1 = [0.75,0,0,0.25]
Q2 = [0.25,0,0,0.75]

两个解的最小距离为0.5，这两个解的任何凸组合都是最优解。
我想知道是否有一种好的方法来找到所有这些最优极点（张成最优子空间的点）？
我为什么对此感兴趣; 给出最大Bhattacharyya系数（凹函数）的点位于统计距离的最优子空间中心位置。
到目前为止，我尝试通过使算法偏向于最小化P[i]，Q[i]之间的距离，在总和中添加1.001的权重来查找最佳的P，Q对（参考我给出的示例）。虽然我几乎无法确定，但它似乎在某种程度上起作用。
1
您可以尝试解决LP问题，然后尝试最大化Bhattacharyya系数，给定您解决的LP的目标函数值。即使您拥有所有最优解（顶点），也不清楚您将如何找到底层多面体的最优面，并且您将如何执行搜索（在这些面上）以最大化Bhattacharyya系数。如果最优解位于“中间”，这可能是因为函数是凹的，那么最优顶点本身就没有什么用处。 - Ioannis
1
我尝试直接编辑问题，但显然我不能这样做；在您的线性规划中，目标函数的每个项都必须分解绝对值，即min sum A[i]满足A[i] >= P[i] - Q[i]和A[i] >= Q[i] - P[i]，其中1 <= i <= 4。 - Nicolas Grebille
我修复了错误，谢谢;-) - balletpiraat
请注意，顶点数量可能非常大：例如，Klee-Minty立方体是一个D x D的线性规划问题，具有2^D个顶点。但是我不知道有多少可以具有相同的c .x. - denis
3个回答
5

有一种有趣的方法可以使用标准MIP求解器枚举所有可能的最优LP解（或者说所有最优LP基）。基本上，该算法如下：

step 1. solve LP/MIP
step 2. if infeasible or if objective starts to deteriorate: stop
step 3. add cuts (constraints) to the model to forbid current optimal solution
step 4. goto step 1

以这里为例。


（翻译：此处提供一个示例，详见链接）
谢谢！我们会尝试这种方法 :) 看起来非常简单，好奇我们会找到多少个 bfs！ - balletpiraat
现在我正在尝试实现这样的方案，但我不太确定我是否完全理解你的意思；我们是否必须假设我们的解决方案是0-1整数解？还是我们使用0-1整数来跟踪我们已知的基本可行点？ - balletpiraat
你为什么认为x的解只能是0-1呢？ - Erwin Kalvelagen
这不是我所相信的。然而，当查看链接时，我被引导相信这应该在某种程度上成立。我不确定在我提出的问题中哪种类型的割应该是合适的。 - balletpiraat
在简单情况下，我可以假设我的变量Q[i]在极点上是0-1的，我可以将这些信息提供给求解器。在这种情况下，你提出的约束条件：sum_{i s.t. knownP[i] = 1} Q[i} <= n - 1，非常有效。但是当0<= Q[i] <= 1时，在极点上，我不清楚应该如何制定约束条件来找到所有的极点。直觉告诉我们，约束条件应该通过另一个极点，以确保我们不会得到一个在极点之间的顶点上的解。 - balletpiraat
我认为你完全错过了这个算法的整个重点。变量x是连续的。变量beta（用于编码基础状态）是二进制的。我们在基础变量beta上进行切割。 - Erwin Kalvelagen
4
LP求解器并不是为了枚举所有最优解而设计的。一旦您知道了最优目标值，您可以定义包含所有最优解的多面体，然后使用顶点枚举算法来收集该多面体的可能非常大的极点集合。所有最优解都是这些极点的凸组合。从Julia中，您可以使用wrapper来调用cdd。
你是否知道Polyhedra.jl + cdd的最小工作示例？我在文档中找不到有关如何使用Polyhedra的任何信息。 - balletpiraat
我建议在相应的代码库中打开一个问题（issue）。 - mlubin
3
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接