For teaching purposes, I believe it can be good to use very light-weight proofs of deep results, as it often answers the question "why is it true" better than other types of proofs. By "light-weight proofs" I mean proofs that rely as little as possible on other deep results as possible.

Regarding proofs of strong duality in linear programming, I have seen many proofs. To name a few

  1. Strong duality as consequence of weak duality + simplex algorithm produces optimal solutions (Introduction to linear optimization, Bertsimas & Tsitsiklis)
  2. Strong duality as a consequence of weak duality + a projection argument (Large scale linear and integer optimization, Kipp Martin)
  3. Strong duality as a consequence of weak duality + Farkas' lemma (Theory of linear and integer programming, Schrijver)
  4. Strong duality as a corollary of strong duality of Lagrangian duality (Noonlinear programming, Bazaraa, Sheral, Shetty)

It can be debated how light-weight these proofs are, as most of them rely on some rather significant results. Thus, my question is

"What good light-weight proofs of strong duality in linear programming do you know?"


1 Answer 1


Strong duality for LPs (and also convex programs) is a corollary of von Neumann's minimax theorem.

This is not what you asked for, since it is again appealing to a deep mathematical result. But I find that presenting duality first from the perspective of swapping min and max and second from the perspective of primal and dual problems makes the idea less magical and therefore more accessible to students. "What are the conditions under which we can swap min and max?" is a question everyone can get their head around.

This may be the same as your number 4.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.