gpt4 book ai didi

julia - 线性规划 : Find all optimal vertices

转载 作者:行者123 更新时间:2023-12-04 10:48:20 24 4
gpt4 key购买 nike

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

到目前为止,我已经尝试通过使算法有利于最小化 P[i],Q[i] 之间的距离来找到最佳 P,Q 对(引用我给出的示例),方法是在和。它似乎在某种程度上有效,尽管我很难确定。

最佳答案

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

关于julia - 线性规划 : Find all optimal vertices,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36376956/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com