7

線形プログラムのすべての最適解を取得するための良い方法 (できれば JuMP を使用) があるかどうか疑問に思っていました (複数の最適解がある場合)。

例

2 つの確率分布間の統計的距離 (コルモゴロフ距離) を最小化します。

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 の最小距離を持ち、これら 2 つのソリューションの任意の凸結合が最適です。

これらすべての最適な極値 (最適な部分空間にまたがる点) を見つける良い方法があるかどうか疑問に思っていましたか?

なぜこれに興味があるのですか？最大のBhattacharyya 係数(凹関数)を与える点は、静的距離の最適部分空間の中間のどこかにあります。

これまでのところ、最適な P,Q のペア (私が示した例を参照) を見つけようとしました和。確かなことはほとんどわかりませんが、ある程度は機能しているようです。

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 に答える