patternMinor
Mistake in a proof of termination phase of Simplex algorithm in CLRS?
Viewed 0 times
phaseclrsmistakealgorithmsimplexterminationproof
Problem
There is a pseudo-code for Simplex algorithm in CLRS:
The proof consists from three-part loop invariant:
Proof We use the following three-part loop invariant:
At the start of each iteration of the while loop of lines 3–12,
The initialisation and maintenance phases are clear for me.
But, the termination case seems(not sure) wrong to me:
So, my question is:
It is unclear for me that $\bar{x_i} = \infty $ if $i = e$. But, if we look at the pseudo-code, it is obvious that such thing happens only if $x_e \leq 0$. What am I missing ?
The proof consists from three-part loop invariant:
Proof We use the following three-part loop invariant:
At the start of each iteration of the while loop of lines 3–12,
- the slack form is equivalent to the slack form returned by the call of INITIALIZE-SIMPLEX,
- foreach $i \in B$, we have $b_i$ >= 0, and
- the basic solution associated with the slack form is feasible.
The initialisation and maintenance phases are clear for me.
But, the termination case seems(not sure) wrong to me:
So, my question is:
It is unclear for me that $\bar{x_i} = \infty $ if $i = e$. But, if we look at the pseudo-code, it is obvious that such thing happens only if $x_e \leq 0$. What am I missing ?
Solution
Because of line 9, $\Delta_l$ is going to be $\infty$ if and only if all the $\Delta_i$ with $i \in B$ are $\infty$. This can happen only when all the $a_{ie}$ with $i \in B$ are $ \le 0$. Hence, by construction the solution $\bar{x}$ satisfies $\bar{x}_i \ge 0$ for all $i$. Therefore it is both feasible and it has unbounded objective value.
If you are confused by the $\infty$, as Marcus Ritt mentioned in a comment you can replace the $\infty$ in the definition of $\bar{x}$ with a very large value $M$ and consider what happens as $M$ tends to $\infty$.
If you are confused by the $\infty$, as Marcus Ritt mentioned in a comment you can replace the $\infty$ in the definition of $\bar{x}$ with a very large value $M$ and consider what happens as $M$ tends to $\infty$.
Context
StackExchange Computer Science Q#110991, answer score: 3
Revisions (0)
No revisions yet.