5
$\begingroup$

Consider an arbitrary linear program:

$$\max \vec c \cdot \vec x$$

subject to:

$$\textbf{A}\cdot \vec x = 0, \quad \vec a \le \vec x \le \vec b$$

Assume that this program is feasible and bounded. Now suppose I perturb the bounds by small amounts:

$$\vec a' = \vec a + \delta \vec p, \quad \vec b' = \vec b + \delta \vec q$$

where $\vec p,\vec q$ are unit vectors and $\delta > 0$. Assume that the modified problem remains feasible and bounded.

Prove or disprove: For arbitrary $\epsilon > 0$, there exists a $\delta > 0$ such that there exist optimal solutions $\vec x, \vec x'$ to the original and perturbed linear programs (respectively) satisfying $|\vec x - \vec x'| < \epsilon$.

Extra: Is there a way to define uniform continuity in this context, such that Linear Programming is, or isn't, uniformly continuous?

$\endgroup$
6
$\begingroup$

The answer is no. Consider the probem $$x+y\to\max,$$ $$x\geq 0,\; y\geq 0,$$ $$x+y\leq 1.$$ It has infinitely many solutions. One of them is $(0,1)$. Now change the last inequality to $$x+(1+\epsilon)y=1.$$ The new problem has a unique solution $(1,0)$ which is not close to the solution of the first one.

One can also construct a counterexample with unique solution of the original problem:

Consider this $x\to\max$, under the restrictions $x\geq 0,\; y\geq 0$, $1\leq x+y\leq 1.$ The unique solution is $(1,0)$. Now you can perturb a little the last restriction, and you obtain a unique solution $(0,1)$.

$\endgroup$
  • 1
    $\begingroup$ I misstated the question, sorry. Your answer made me see the issue. Can you please look at the updated question? $\endgroup$ – becko Jan 30 '17 at 20:42
  • $\begingroup$ @becko: My second example disproves the new conjecture. $\endgroup$ – Alexandre Eremenko Jan 31 '17 at 7:57
  • $\begingroup$ The correct conditions that ensure continuity are stated in the answer of Robert Israel. $\endgroup$ – Alexandre Eremenko Jan 31 '17 at 7:59
  • $\begingroup$ I don't understand the second example. How exactly do you perturb the last restriction? $\endgroup$ – becko Jan 31 '17 at 13:28
  • 1
    $\begingroup$ Replace the last restriction by $1\leq y+(1-\epsilon)x$ and $x+y\leq 1$. Together with $x\geq 0$, $y\geq 0$ the only feasible point is $(0,1)$. $\endgroup$ – Alexandre Eremenko Jan 31 '17 at 19:52
4
$\begingroup$

You can get this kind of continuity if the optimal solution is nondegenerate in the following sense. Let the coefficient matrix be $m \times n$, and suppose there is a subset $B$ of $[1,\ldots,n]$ with cardinality $m$ (the "basic variables") such that the submatrix $A_B$ for columns in $B$ is invertible, and in your optimal solution the $x_j$ for $j \notin B$ are each equal to either $a_j$ or $b_j$, and the $x_j$ for $j \in B$ are strictly between $a_j$ and $b_j$.

$\endgroup$

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.