Linear Programming: Find all optimal vertices
<p>I was wondering if there is a nice way (preferably using JuMP) to get all optimal solutions of a linear program (in case there are multiple optimal solutions).</p>

<p>An example </p>

<p>minimize the statistical distance (Kolmogorov distance) between two probabilities distributions.</p>

<pre><code>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 -&gt; Q[2],Q[3] = 0
</code></pre>

<p>Note we can phrase the optimization as a linear program, the objective becomes</p>

<pre><code>min S &gt;= sum_i S[i]
S[i] &gt;= P[i]-Q[i]
S[i] &gt;= Q[i]-P[i]
</code></pre>

<p>There is no unique solution to this problem, instead the subspace of optimal solution is spanned by</p>

<pre><code>Q1 = [0.75,0,0,0.25]
Q2 = [0.25,0,0,0.75]
</code></pre>

<p>Both have the minimal distance of 0.5,
any convex combination of the these two solution is optimal.</p>

<p>I was wondering if there is a nice way to find all these optimal extreme points (points that span the optimal subspace)?</p>

<p>Why am I interested in this; the points that gives the maximal <a href="https://en.wikipedia.org/wiki/Bhattacharyya_distance#Bhattacharyya_coefficient/%22Bhattacharyya%20Coefficient%22" rel="nofollow">Bhattacharyya coefficient</a> (concave function), lies somewhere in the middle of the optimal subspace of the statical distance.</p>

<p>So far I`ve tried to find optimal P,Q pairs (refering to example I gave) by making the algorithm favor miniziming the distance between P[i],Q[i], by adding a weight of 1.001 to this term in the sum. It seems to work to some extend, although I can hardly know for sure.</p>