Stochastic programming: Is the linear program over the vertices the same as over the simplex?

60 Views Asked by At

Suppose we have a random variable $W$ with probability distribution,

$\Pr(W = w) = p_w \in [0,1], \quad w \in I = \{1, \ldots n\}$

Consider the maximization problem:

$$\max\limits_{w \in I} \mathbb{E}[f(w)] $$

Then we have,

$\max\limits_{w \in I} \sum\limits_{w \in I} f(w)\Pr(W = w) = \max\limits_{w \in I} \sum\limits_{w \in I} f(w)p_w = \max\limits_{w \in I} f^Tp $

where $f = (f_w)_{w \in I}$, and $p = (p_w)_{w \in I}$

Question: Is this problem equivalent to:

$$\max\limits_{p \in \Delta} f^Tp $$

where $p = (p_w)_{w \in I}$ and $\Delta = \left\{p \in \mathbb{R}^n| \sum\limits_{w \in I} p_w = 1, p_w \geq 0\right\}$

1

There are 1 best solutions below

0
On BEST ANSWER

It depends what you mean by equivalent. $$ \max_{w \in I} \mathbb{E}[f(w)] \qquad (1)$$ $$ \max_{p \in \Delta} f^T p \qquad (2)$$

If (1) has a unique solution $w^* = \arg \max_{i \in N} f_i$, then the two problems are equivalent. $w^*$ is optimal for (1) if and only if $p_{w^*} = 1$ is optimal for (2). The two problems will always have the same optimal objective value. Hope this helps.