11
$\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$
5
  • 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, 2013 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, 2013 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, 2017 at 18:36
  • 1
    $\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$ Jan 8, 2019 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$ Jan 8, 2019 at 13:20

1 Answer 1

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$
2
  • $\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, 2013 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, 2013 at 9:33

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.