线性规划：找到所有最优顶点
Linear Programming: Find all optimal vertices
我想知道是否有一个好的方法（最好使用 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
注意我们可以将优化表述为线性程序，objective 变为
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 coefficient（凹函数）的点位于静态距离的最佳子空间的中间某处。
到目前为止，我已经尝试通过添加 1.001 的权重使算法有利于最小化 P[i]、Q[i] 之间的距离来找到最佳 P、Q 对（参考我给出的示例）到这一项的总和。它似乎在一定程度上起作用，虽然我很难确定。
我不知道 julia，但是有一个工具叫 PPL，你可以用它来确定求解线性程序后多面体的所有顶点。
在此处查看我对类似问题的回答：
.
LP 求解器并非旨在枚举所有最优解。一旦知道最优 objective 值，就可以定义包含所有最优解的多面体，然后使用顶点枚举算法来收集该多面体可能非常大的一组极值点。所有最优解都是这些极值点的凸组合。在 Julia 中，您可以使用 wrapper for cdd.
有一种有趣的方法可以使用标准 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
有关示例，请参见 here。
我想知道是否有一个好的方法（最好使用 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
注意我们可以将优化表述为线性程序，objective 变为
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 coefficient（凹函数）的点位于静态距离的最佳子空间的中间某处。
到目前为止，我已经尝试通过添加 1.001 的权重使算法有利于最小化 P[i]、Q[i] 之间的距离来找到最佳 P、Q 对（参考我给出的示例）到这一项的总和。它似乎在一定程度上起作用，虽然我很难确定。
我不知道 julia，但是有一个工具叫 PPL，你可以用它来确定求解线性程序后多面体的所有顶点。
在此处查看我对类似问题的回答：
LP 求解器并非旨在枚举所有最优解。一旦知道最优 objective 值，就可以定义包含所有最优解的多面体，然后使用顶点枚举算法来收集该多面体可能非常大的一组极值点。所有最优解都是这些极值点的凸组合。在 Julia 中，您可以使用 wrapper for cdd.
有一种有趣的方法可以使用标准 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
有关示例，请参见 here。