Optimization Online


Strong Duality: Without Simplex and without theorems of alternatives

Somdeb Lahiri (somdeb.lahiri***at***yahoo.co.in)

Abstract: The simplex method has its own problems related to degenerate basic feasible solutions. While such solutions are infrequent, from a theoretical standpoint a proof of the strong duality theorem that uses the simplex method is not complete until it has taken a few extra steps. Further, for economists the duality theorem is extremely important whereas the simplex method is not necessarily so. If we add to it the fact, that the simplex method has faster substitutes for computational purpose, an alternative proof of the strong duality theorem which does not use the simplex method would be very welcome. The alternative is to use the Farkasís lemma or a theorem of alternative than can be derived from it. Such proofs while extremely elegant pre-empt deriving Farkasís lemma itself from the strong duality theorem of LP. We provide an alternative proof of the strong duality theorem whose main step is a proposition which says that every canonical linear programming minimization problem whose image under its objective function of the set of feasible solutions is non-empty and bounded below has an optimal solution. We also use this proposition to obtain an independent proof of the Farkaís lemma.

Keywords: linear programming, strong duality, Farkas's lemma

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )


Download: [PDF]

Entry Submitted: 09/08/2015
Entry Accepted: 09/08/2015
Entry Last Modified: 12/03/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society