我想知道是否有一种好的方式(最好使用JuMP)来获取线性规划的所有最优解(如果有多个最优解的话)。
一个例子是,最小化两个概率分布之间的统计距离(科尔莫戈洛夫距离)。
请注意,我们可以将优化问题表述为线性规划问题,目标函数为:
这个问题没有唯一解,相反最优解的子空间由以下组成。
两个解的最小距离为0.5,这两个解的任何凸组合都是最优解。
我想知道是否有一种好的方法来找到所有这些最优极点(张成最优子空间的点)?
我为什么对此感兴趣; 给出最大Bhattacharyya系数(凹函数)的点位于统计距离的最优子空间中心位置。
到目前为止,我尝试通过使算法偏向于最小化P[i],Q[i]之间的距离,在总和中添加1.001的权重来查找最佳的P,Q对(参考我给出的示例)。虽然我几乎无法确定,但它似乎在某种程度上起作用。
一个例子是,最小化两个概率分布之间的统计距离(科尔莫戈洛夫距离)。
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对(参考我给出的示例)。虽然我几乎无法确定,但它似乎在某种程度上起作用。
min sum A[i]
满足A[i] >= P[i] - Q[i]
和A[i] >= Q[i] - P[i]
,其中1 <= i <= 4
。 - Nicolas Grebille