3

I'm working on the following exercise:

Let $c \in \mathbb{R}^n$ and $A \in \mathbb{R}^{m*n}$. For an any arbitrary $b \in \mathbb{R}^m$ we consider the following problem $(P_b)$:

$$min_{x \in \mathbb{R}^n} c^Tx$$

$$\text{such that } Ax = b, x \ge 0$$

Let further be $B$ a base of $A$. We set $x(B,b)$ as the unique solution to the linear equation system: $Ax = b, x_i = 0 \ (\forall i \not \in B )$. We know that the mapping $b \mapsto x(B,b)$ is continuous.

Let now be $\overline{b} \in \mathbb{R}^m$. We make the following assumptions:

  1. The problem $(P_{\overline{b}})$ has a unique solution $\overline{x}$ and there is a unique base $\overline{B}$ such that $\overline{x} = x(\overline{B},\overline{b})$. For all $i \in \overline{B}$ holds $\overline{x}_i > 0$.
  2. There is a number $\epsilon_0 > 0$ such that for all $b \in \mathbb{R}^m$ with $\| b - \overline{b} \| \le \epsilon_0$ the problem $(P_b)$ has a solution.

Show that there is a $\epsilon >0$ such that for all $b \in \mathbb{R}^m$ with $\| x - \overline{x} \| \le \epsilon$ the point $x(\overline{B},b)$ is a solution to $(P_b)$.

My idea would be to use, the continuity of the mapping $b \mapsto x(B,b)$ with point 2) to show from $\| b - \overline{b} \| \le \epsilon_0$ that $\| x - \overline{x} \| \le \epsilon$ but I don't know how to choose $\epsilon$ so that I can say that $\| x - \overline{x} \|$ is indeed smaller or equal to $\epsilon$. I also don't get why the solution has to have the form $x(\overline{B},b)$. Could you give me a hint ?

3nondatur
  • 4,178
  • When you refer to solutions, are you referring to optimal solutions? I am going to assume so. This is a nice question. – Wes Jun 11 '18 at 23:24
  • Also, I think you should have been asked to show that there is $\varepsilon > 0$ s.t. for all $b \in \mathbb{R}^m$ with $||b - \overline{b}|| < \varepsilon$ the point $x(\overline{B}, b)$ is a solution of $(P_b)$. The current statement does not make sense. – Wes Jun 12 '18 at 00:18

1 Answers1

1

Assume for clarity that $x(B, b)$ denotes the optimal solution to $(P_b)$. I also think that you should have been asked to show This problem can be interpreted as asking you to show an important fact about sensitivity analysis in the absence of degeneracy: that the current basis remains optimal so long as feasibility is maintained.

Condition (1) implies that $x(\overline{B}, \overline{b})$ is non-degenerate, as well as unique. This is sufficient to prove condition (2), as well as the result you desire.

Consider the optimal simplex tableau corresponding to $\overline{x} = x(\overline{B}, \overline{b})$. Let $\overline{x}_{\overline{B}}$ denote the basic part of $\overline{x}$. Note that the only part of the tableau containing $\overline{b}$ is the right-hand side, where $\overline{B}^{-1} \overline{b}$ appears. Notice that $\overline{x}_{\overline{B}} = \overline{B}^{-1} \overline{b} > 0$, by the non-negativity of condition (1), and $\overline{B}^{-1}$ is a linear operator. Linear operators are continuous, so there is a $\delta > 0$ such that $\overline{B}^{-1} b > 0$ for all $|| b - \overline{b} || < \delta$. This means that replacing $\overline{B}^{-1} \overline{b}$ with $\overline{B}^{-1} b$ in the aforementioned optimal tableau yields an optimal tableau for $(P_b)$, since feasibility is maintained, the reduced costs remain unchanged, and multiplying the new optimal tableau through by $\overline{B}$ gives an initial tableau for $(P_b)$. This simultaneously proves condition (2) and the result.

Wes
  • 670