# Optimality solutions of stochastic linear program

Given the random LP: $K(x,\epsilon) = min_{a=(a_1,a_2)}\ a_1(w) + a_2(w)$ such that

$$\ a_1(w) - a_2(w) = x-\epsilon$$ and $$a_1(w), a_2(w), x\geq 0,$$ where $\epsilon\sim U(0,1)$ and $w$ is the outcome of random variable $\epsilon$. Assume $a_1^{*}(w)$ and $a_2^{*}(w)$ are optimal solution given some $x$ and some outcome $w$.

(a) Express $a_1^{*}(w)$, $a_2^{*}(w)$ and $K(x,\epsilon)$ as a function of $x$ and $\epsilon$.

(b) Find $F_{Q}(\cdot)$, the cumulative distribution of $K(x,\epsilon)$.

(c) Use part (b) to find $x^{*} = \arg\min E[K(x,\epsilon)]$.

My attempt:

(a) The dual problem is: $max_{\pi\geq 1} \ \pi(x-\epsilon)$. By strong duality theorem, we have: $a_1^{*}(w) + a_2^{*}(w) = max_{\pi\geq 1} \pi(x-\epsilon)$. In addition, since $a_1^{*}(w)$ and $a_2^{*}(w)$ are optimal solutions to the primal problem, $a_1^{*}(w) - a_2^{*}(w) = x - \epsilon$.

Thus, solving the system of two linear equations above, we obtain $$a_1^{*}(w) = \frac{x-\epsilon + max_{\pi\geq 1} \pi(x-\epsilon)}{2}$$

and $$a_2^{*}(w) = \frac{-x+\epsilon + max_{\pi\geq 1} \pi(x-\epsilon)}{2}$$

Thus, $K(x,\epsilon) = max_{\pi\geq 1} \pi(x-\epsilon)$.

(b) By definition, $F_{K}(\cdot) = P(K(x,\epsilon)\leq x) = P(\pi(x-\epsilon)\leq x) = P(x-\frac{x}{\pi}\leq \epsilon)$ for all $\pi\geq 1$.

Since $\epsilon\sim U(0,1)$, we obtain $F_{K}(\cdot) = P(x-\frac{x}{\pi}\leq \epsilon) = 1 - x + \frac{x}{\pi}$.

(c) Note that $E[K(x,\epsilon)] = E_{\epsilon}[K(x,\epsilon)] = \int_{0}^{1} [1-(1-x-\frac{x}{\pi})]\ d\epsilon = x+\frac{x}{\pi}$.

Since $x\geq 0$, the minimum value of $x+\frac{x}{\pi}$ obviously occurs at $x=0$, so $\fbox{$x^{*} = 0$}$

My question: Could someone please help review my solutions above and let me know if there are any mistakes in it, especially parts (a) + (c)? Any inputs would really be appreciated.

The formula for $K(x,\epsilon)$ can be simplified: $K(x,\epsilon) = x-\epsilon$ if $x\leq\epsilon$, $\infty$ otherwise.
In part $b$, I do not see why $x$ in $K(x,\epsilon)$ and in $\leq x$ should be the same, but that could be due to the context. (I also do not see why you use $w$ instead of $\epsilon$.) Either way, $\max_\pi$ is missing in $b$. Including that gives $F_K(x) = P(x\leq\epsilon)$.
• thank you very much for your comment. You are right,but I skipped the $\max_{\pi}$ on purpose, because $\pi(x-\epsilon)\leq \max_{\pi}\pi(x-\epsilon)$. Otherwise, how could you compute $F_{K}(x)$? Also, how did you get $F_{K}(x) = P(x\leq \epsilon)$? The $x$ is the same because I thought that is the definition of cumulative distribution of $K(x,\epsilon)$, no? – user177196 Mar 5 '18 at 20:19
• Btw, from $K(x,\epsilon)=x-\epsilon$ if $x\leq \epsilon$, isn't it true that $F_K(z) = 1-x+z$ if $x\geq z$, and $=1$ otherwise? – user177196 Mar 5 '18 at 20:31
• So, after incorporating your suggestion on $K(x,\epsilon)$, I actually got a very complicated form for $F_{K}(z)$: $1$ if $x\leq \min(x, \epsilon)$, $1-x+z$ if $x\leq \epsilon, x\geq z, z\geq x-\epsilon$ and $0$ otherwise. Now, computing $E(K(x,\epsilon)) = \int_{x-\epsilon}^{x} [1-F_{K}(z)dz] = \frac{x\epsilon + \epsilon^2}{2}$ – user177196 Mar 5 '18 at 21:30
• It does not follow from the definition of cdf that $x$ is the same. For example, if we had $K(x,\epsilon)=2\epsilon-x$, the cdf would be nondecreasing :D You should probably use the definition of a cdf with $y$ instead of $x$. – LinAlg Mar 5 '18 at 21:32