  


Strong Duality: Without Simplex and without theorems of alternatives
Somdeb Lahiri (somdeb.lahiriyahoo.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 preempt 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 nonempty 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 ) Citation: Download: [PDF] Entry Submitted: 09/08/2015 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  