6
$\begingroup$

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

$\endgroup$
4
  • 3
    $\begingroup$ See for instance arxiv.org/abs/1407.1240. Maybe Cees Roos also has published about it. $\endgroup$ Commented Mar 24, 2022 at 9:50
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kuifje
    Commented Mar 24, 2022 at 10:02
  • $\begingroup$ @ErlingMOSEK that is a pretty nice paper. Thanks for the reference! $\endgroup$
    – Sune
    Commented Mar 24, 2022 at 10:16
  • $\begingroup$ 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. $\endgroup$ Commented Dec 15, 2022 at 13:08

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

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

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