7

我想知道是否有一种很好的方法（最好使用 JuMP）来获得线性程序的所有最优解（如果有多个最优解）。

一个例子

最小化两个概率分布之间的统计距离（Kolmogorov 距离）。

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 系数（凹函数）的点位于静态距离的最佳子空间的中间某处。

到目前为止，我已经尝试通过在和。它似乎在某种程度上起作用，尽管我很难确定。

4

3 回答 3

4

有一种有趣的方法可以使用标准 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

有关示例，请参见此处。

于 2016-04-05T06:46:38.340 回答
4

LP 求解器并非旨在枚举所有最优解。一旦你知道了最优目标值，你就可以定义包含所有最优解的多面体，然后使用顶点枚举算法来收集这个多面体可能非常大的一组极值点。所有最优解都是这些极值点的凸组合。从 Julia，您可以使用cdd的包装器。

于 2016-04-03T14:54:38.407 回答
3

我不知道 julia，但是有一个名为PPL的工具，您可以在求解线性程序后使用它来确定解多面体的所有顶点。

在此处查看我对类似问题的回答： Find all alternative basic solutions using existing linear-programming tool。

于 2016-04-03T01:41:53.120 回答