I have the following problem and I'd like to know if it is formalizable as a LP program. (or, more generally, if it is solvable in polynomial time).
Let us fix some terminology first which will probably allow you to understand the problem better. For a given set $X=\{x_{1},\dots, x_{n}\}$
I use the term "probability distribution" on $X$ for $n$-tuples $ d=\langle c_{1},\dots, c_{n}\rangle\in[0,1]^n$ such that $\sum c_{i}=1$.
I use the term "function" $f:X\rightarrow[0,1]$ for arbitrary tuples $\langle v_{1},\dots, v_{n}\rangle\in[0,1]^n$
I use the term "expected value" of $f$ under $d$, written $E_{d}(f)$ for: $E_{d}(f)= (c_{1}\cdot v_{1})+ \dots + (c_{n}\cdot v_{n})$, with $c_{i}$ and $v_{i}$ as above.
The problem is the following:
PROBLEM: I have two fixed sets $A$ and $B$ of distributions on $X$ (i.e., a bunch of tuples which are parameters and not variables of the problem). I want to know if there exists a function $f:X\rightarrow [0,1]$ such that:
$\ \ \ \ \ \ \displaystyle \min_{d\in A}E_{d}(f) \neq \min_{e\in B}E_{e}(f) $
or, equivalently, such that
$\ \ \ \ \ \ \displaystyle \min_{d\in A}E_{d}(f) - \min_{e\in B}E_{e}(f) > 0$
The problem in formalizing this in LP is given by the presence of $\min$ functions in positive and negative position.
Any suggestion?
Thanks!
Let me assume, that your $A$ and $B$ are finite, i.e., $A = \{ a_i \}_{i=1}^n$ and $B = \{ b_j \}_{j=1}^m$.
Then, we have that $\min_{d\in A} E_d(f) = \min_{d\in A} d^\top f \ge \alpha$ is equivalent to $a_i^\top f \ge \alpha$ for all $i = 1,\ldots,n$. Similarly, $min_{e\in B} E_e(f) \le \beta$ is equivalent to $\max_{e\in B} -E_e(f) \ge -\beta$, which is in turn equivalent to $-b_j^\top f \ge - \beta$ for all $j$.
Finally, consider the LP \begin{align} \text{Maximize}\quad & \alpha - \beta \\ \text{w.r.t.}\quad & \alpha, \beta, f \\ \text{such that}\quad & a_i^\top f \ge \alpha \text{ for all }i = 1,\ldots,n\\ \text{and}\quad & -b_j^\top f \ge - \beta \text{ for all }j = 1,\ldots,m. \end{align} The ptimal value of this LP is the maximal value of $\min_{d\in A} E_d(f) - \min_{e \in B} E_e(f)$.