Optimization Online


An elementary proof of linear programming optimality conditions without using Farkas' lemma

Anders Forsgren(andersf***at***kth.se)
Margaret H. Wright(mhw***at***cs.nyu.edu)

Abstract: Although it is easy to prove the sufficient conditions for optimality of a linear program, the necessary conditions pose a pedagogical challenge. A widespread practice in deriving the necessary conditions is to invoke Farkas' lemma, but proofs of Farkas' lemma typically involve "nonlinear" topics such as separating hyperplanes between disjoint convex sets, or else more advanced LP-related material such as duality and anti-cycling strategies in the simplex method. An alternative approach taken previously by several authors is to avoid Farkas' lemma through a direct proof of the necessary conditions. In that spirit, this paper presents what we believe to be an "elementary" proof of the necessary conditions that does not rely on Farkas' lemma and is independent of the simplex method, relying only on linear algebra and a perturbation technique published in 1952 by Charnes. No claim is made that the results are new, but we hope that the proofs may be useful for those who teach linear programming.

Keywords: linear programming, optimality conditions, Farkas' lemma

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

Citation: arXiv:1407.1240 [math.OC], July 2014

Download: [PDF]

Entry Submitted: 07/08/2014
Entry Accepted: 07/08/2014
Entry Last Modified: 07/08/2014

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