1
$\begingroup$

Suppose I have a linear program of the form $\max c^Tx$ such that $Ax \leq b$. I am curious as to the continuity of the solutions to such a linear program under perturbations of the entries of $A$.

Are there any results of the form "If $\delta > 0$ is small enough, then the solution $x^*$ to $\max c^Tx$ such that $Ax \leq b$ will be within $\epsilon$ of the solution $x^*_{\delta}$ to $\max c^Tx$ such that $(A+B\delta)x \leq b$? In this case any nonzero $B$ matrix would be sufficient for what I am looking for.

If not, are there any counterexamples where no matter how small $\delta$ is, the solution $x^*_{\delta}$ stays at least a fixed distance from $x^*$?

Improve this question
$\endgroup$
1
  • 4
    $\begingroup$ What do mean here by "the solution"? The set of all maximizers may be empty, and it may be infinite. $\endgroup$ Commented Dec 23, 2024 at 18:18

1 Answer 1

Reset to default
2
$\begingroup$

When the optimal solution is non-unique, you typically have discontinuity under perturbation. For a simple example, consider

maximize $x_1 + x_2$ subject to $x_1 + a x_2 \le 1$, $x_1, x_2 \ge 0$.

For $0 < a < 1$, the optimal solution is $x_1 = 0$, $x_2 = 1/a$. For $a > 1$, the optimal solution is $x_1 = 1$, $x_2 = 0$. For $a = 1$, the optimal solutions are $x_1 = t$, $x_2 = 1-t$ for $0 \le t \le 1$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ But assuming the solution is nondegenerate we can avoid this case though right? $\endgroup$ Commented Dec 24, 2024 at 22:35
  • 1
    $\begingroup$ @AnotherPerson Yes. If the solution is nondegenerate, then for $\delta$ sufficiently small the optimal basis will be unchanged. For such $\delta$, the optimal solution is a continuous function of $\delta$. $\endgroup$ Commented Dec 30, 2024 at 5:59

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.