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)$.

  • $\begingroup$ 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? $\endgroup$ – user177196 Mar 5 '18 at 20:19
  • $\begingroup$ 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? $\endgroup$ – user177196 Mar 5 '18 at 20:31
  • $\begingroup$ 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}$ $\endgroup$ – user177196 Mar 5 '18 at 21:30
  • 1
    $\begingroup$ 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$. $\endgroup$ – LinAlg Mar 5 '18 at 21:32

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.