The following linear programming problem $x_n = \arg\min c_n'x \mbox{ subject to } Ax<b$ has a changing coefficient $c_n$. We have that $c_n\rightarrow c_*$. What happens to the solution $x_n$? Does it converge to $x_*$, the optimal solution with coefficient $x_*$?
4
-
$\begingroup$ We can assume that the $x_n$ is unique for all $c_n$. $\endgroup$– BascaCommented May 13, 2019 at 20:32
-
2$\begingroup$ It may jump around. Let the restrictions be $x,y\ge 0,x+y\le 1$. Now let $c_n$ be $(1,1+(-1)^n/n)$. However, if it does converge, it converges to an optimal solution for the limit problem. $\endgroup$– fedjaCommented May 13, 2019 at 20:38
-
$\begingroup$ I think the last sentence should be "...with coefficient $c_*$." $\endgroup$– LarrySnyder610Commented May 14, 2019 at 1:54
-
$\begingroup$ @LarrySnyder610 Yes, you are correct. $\endgroup$– BascaCommented May 14, 2019 at 14:58
Add a comment
|