# Light weight proof of strong duality in linear programming

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?"

• See for instance arxiv.org/abs/1407.1240. Maybe Cees Roos also has published about it. Commented Mar 24, 2022 at 9:50
• For teaching purposes, sometimes a good example is more effective than a proof, especially if there is nothing "light-weight" out there. See for example science4all.org/article/duality-in-linear-programming, with a nice geometric explanation. Commented Mar 24, 2022 at 10:02
• @ErlingMOSEK that is a pretty nice paper. Thanks for the reference!
– Sune
Commented Mar 24, 2022 at 10:16
• For one of the simplest algorithmic proofs of strong duality (according to the authors), see also Criss-Cross Methods: A Fresh View on Pivot Algorithms by Fukuda and Terlaky. Commented Dec 15, 2022 at 13:08