10
$\begingroup$

Consider the linear programs

\begin{array}{|ccc|} \hline Primal: & A\vec{x} \leq \vec{b} \hspace{.5cm} & \max \vec{c}^T\vec{x} \\ \hline \end{array} \begin{array}{|ccc|} \hline Dual: & \vec{c} \leq \vec{y}^TA \hspace{.5cm} & \min \vec{y}^T\vec{b} \\ \hline \end{array}

The weak duality theorem states that if $\vec{x}$ and $\vec{y}$ satisfy the constraints then $\vec{c}^T\vec{x} \leq \vec{y}^T\vec{b}$. It has a short and slick proof using linear algebra: $\vec{c}^T\vec{x} \leq \vec{y}^T A \vec{x} \leq \vec{y}^T\vec{b}$.

The strong duality theorem states that if the $\vec{x}$ is an optimal solution for the primal then there is $\vec{y}$ which is a solution for the dual and $\vec{c}^T\vec{x} = \vec{y}^T\vec{b}$.

Is there a similarly short and slick proof for the strong duality theorem?

$\endgroup$
  • 1
    $\begingroup$ Chapter 4 of the MIT online course web.mit.edu/15.053/www by Bradley, Hax, and Magnanti gives a reasonably short proof along these lines. Is this what you're looking for? $\endgroup$ – cody Nov 19 '13 at 17:40
  • $\begingroup$ @cody, well, it seems essentially the same as the one in CLRS. It can be fine if you can express it in a slick linear algebra way (i.e. no sums). $\endgroup$ – Kaveh Nov 19 '13 at 21:28
  • $\begingroup$ It seems that what I wanted is probably not possible. The Farkas uses the closedness of space which means there is probably no pure linear algebra proof. $\endgroup$ – Kaveh Oct 21 '17 at 18:36
  • $\begingroup$ Trying to find something not-too-cumbersome myself, to show my students (so they don't have to just take strong duality on faith), and most of what I've come across is more in the too-cumbersome category. Just found an argument in notes from a class of Dan Spielman's, which is quite short and seemingly simple. Not sure if it's hiding some complexity, or if there's something missing? (Haven't examined it thoroughly enough to tell, yet.) cs.yale.edu/homes/spielman/BAP/lect12.pdf $\endgroup$ – Magnus Lie Hetland Jan 8 at 13:10
  • $\begingroup$ Ah, I guess a central point is the geometric interpretation in the previous lecture, which takes us back to the Simplex family of proofs: cs.yale.edu/homes/spielman/BAP/lect11/lect11.pdf $\endgroup$ – Magnus Lie Hetland Jan 8 at 13:20
3
$\begingroup$

Probably not. Here is a conceptual argument based on

Farkas Lemma: Exactly one of the following alternatives has a solution:

  1. $Ax \le b$ and $x \ge 0$
  2. $y^TA\ge 0$ and $y^Tb < 0$

Now let $\delta$ be the optimal objective value of the primal. Let $\epsilon > 0$ be arbitrary. Let $A'$ to be $A$ with an additional $-c^T$ as the last row. Let $b'$ to be $b$ with an additional $-\delta - \epsilon$ as the last value.

The system $A'x'\le b'$ has no solution. By Farkas, there is a $y' = (y,\alpha)$ such that:

$y^TA\ge \alpha c$ and $y^Tb < \alpha (\delta + \epsilon)$.

Note that if $\epsilon = 0$ we are in the other alternative of Farkas. Therefore $\alpha > 0$.

Scale $y'$ so that $\alpha = 1$. $y$ is dual feasible. The weak duality implies $\delta \le y^Tb < \delta + \epsilon$.

$\endgroup$
  • $\begingroup$ I think this is the proof in Jeff Erickson's lecture notes. I am looking for something which avoids the epsilon stuff (like pure linear algebra). $\endgroup$ – Kaveh Nov 20 '13 at 0:48
  • 2
    $\begingroup$ What JeffE has is a little different, and it explains the geometry more. Anyway, you aren't going to find what you want, in the sense that the feasible region is a polyhedron, not a linear space, so something will eventually need to make use of that. (Here, it is hiding in Farkas. Gärtner and Matoušek's book is a really good reference for this stuff. I am pretty sure this proof is there.) $\endgroup$ – Louis Nov 20 '13 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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