Proof of Strong Duality via Simplex Method

Question

I am study the book Introduction to Linear Optimization by Bertsimas and Tsitsiklis. The proof of strong duality (Theorem 4.4)

Theorem 4.4 (Strong duality) If a linear programming problem has an optimal solution, so does its dual, and the respective optimal costs are equal.

uses the fact that the simplex method has finite termination using the lexicographic pivoting rule, takes an optimal BFS $x$, and constructs a dual feasible solution $p'=c_B'B^{-1}$ that has the same cost as the primal optimal solution.

I wonder why the simplex method is used in this proof. Why not just use the fact that a standard form LP which has an optimal solution must have an optimal BFS? Is it because the reduced costs are not guaranteed to be nonnegative?

Answer 1

The issue of nonnegative reduced cost is likely the reason, yes.

It does not take too much work to show (without the simplex method) that if a linear program has an optimal solution, then it has an optimal basic feasible solution. This is still a nontrivial proof, and using the simplex method to prove strong duality sidesteps it.

However, once we have the optimal basic feasible solution, there are two challenges with the reduced costs:

1. To prove the dual feasibility of $c'_B B^{-1}$, we need them to be nonnegative, and the clearest argument I can see for that is "well, if one of them is negative, do a pivot step of the simplex method to improve the objective value". We can rephrase that without talking about pivoting - something like "the corresponding nonbasic variable can be increased slightly with a compensating slight decrease in all the basic variables by such-and-such formula, getting a better feasible solution". But at some point, you're avoiding the obvious.
2. We can't even guarantee for certain that if a basic feasible solution is optimal, then it has nonnegative reduced costs. When the optimal basis is degenerate, there might be other bases that the optimal solution can be written in, where some reduced costs have the wrong sign. (The argument in 1 does not apply, since in such a case any attempt to increase the nonbasic variable immediately drops a basic variable into the negatives.) Handling this requires something to deal with degeneracy, at which point you might as well be reinventing the simplex method.

---

This is not to say that strong duality cannot be proven without the simplex method. The usual alternate route is to use Farkas's lemma: if a system of linear inequalities has no solution, then some linear combination of those inequalities (with nonnegative coefficients, so that the inequalities are preserved) yields a contradiction.

To prove Farkas's lemma, we can use Fourier-Motzkin elimination to try to solve the system of linear inequalities: this is a much slower algorithm than the simplex method, but it is also easier to handle theoretically.