2
$\begingroup$

In my research I have to find two discrete probability distributions by solving two separate linear programs. The domain of optimization is the probability space of $m^n$ atomic events, where $n$ is the number of random variables and each random variable can take $m$ discrete values.

The only difference in the two linear programs are the coefficients of the linear objective and the coefficients of the linear inequalities, for example the first linear program is $$\max a_{1}^Tp_1$$$$\text{such that }U_1p_1\geq0$$ $$\sum p_1=1$$$$p_1 \geq0$$

and the second program is $$\max a_{2}^Tp_2$$$$\text{such that }U_2p_2\geq0$$ $$\sum p_2=1$$$$p_2 \geq0$$ where $p_1,$ $p_2$ are probability vectors of each size $m^n$ and $U_1$, $U_2$ are real matrices.

Each element in the coefficients $a_1$, $U_1$ are decreasing with a parameter $d$ on the other hand each element in the coefficients $a_2$, $U_2$ are increasing with that same parameter $d$.

I want to say that there is some value $d$ such that the $a_1^Tp_1^* \leq a_2^Tp_2^*$ where $p_1^*$,$p_2^*$ are the optimal arguments of the two linear programs.

I want to know how I can make such a claim and what assumptions I need, if any. Appreciate any form of advice. Thank you all.

$\endgroup$
  • 1
    $\begingroup$ I think that what you need to prove is that the convex hull of the first program is contained in the convex hull of the second program. Your claim would then follow, since all extreme vertices of the first simplex (I assume your programs are bounded) would be "inside" the second simplex. $\endgroup$ – baudolino Sep 1 '13 at 3:00
  • $\begingroup$ @baudolino Thank you very much. I understood your point. But it occurs to me that even if the two convex hulls are completely non overlapping still there can be two probability distributions such that the my claim holds. Therefore contrainment of convex hull of first program in the second is sufficient but doesn't seem a necessary condition. How can we look for such more general conditions ? $\endgroup$ – triomphe Sep 1 '13 at 3:51
  • 1
    $\begingroup$ I think the problem now is too vague. You should know more about assumptions that you can make. Maybe it would help if you state how $a_1, a_2, U_1, U_2$ depend on $d$. Otherwise, I can come up with something like $\max a_1 \le \min a_2$ for some $d$. $\endgroup$ – Tunococ Sep 1 '13 at 4:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.