线性规划:找到所有最佳顶点

Question

我想知道是否有一种很好的方法(最好使用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系数(凹函数)的点位于静态距离的最佳子空间的中间.

到目前为止,我试图找到最佳的P,Q对(参考我给出的例子),使算法有利于通过在该项中增加1.001的权重来缩小P [i],Q [i]之间的距离.和.它似乎在某种程度上起作用,尽管我几乎无法确定.

Answer 1

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

有关示例，请参见此处。