5
$\begingroup$

I am trying to prove what is often titled the strong duality theorem. There is a hint in the book that I'm following, and I want to follow the method they have outlined for me. I will outline the problem:

Let A.1: Minimize $c^tX$ subject to $AX\ge b$, $X \ge 0$

Let A.2 (Dual): Maximize $Y^tb$ subject to $A^tY \le c$, $Y \ge 0$

Farkas' Lemma states: Given a matrix $D$ and a row vector $d$, either there exists a column vector $v$ such that $Dv \le 0$ and the scalar $dv$ is strictly positive, or there exists a non-negative row vector $w$ such that $wD = d$, but not both.

The strong duality theorem states: If a linear program has a finite optimal solution, then so does its dual, and the optimal values of the objective functions are equal.

Prove this using the following hint: If it is false, then there cannot be any solutions to

$$AX \ge b, \; A^tY \le c, \; X \ge 0,\; Y\ge 0, \; c^tX \le Y^tb.$$

My attempt at a solution picks up from the hint. If someone will help me complete the proof, I want it to follow my line of reasoning. I know there are many other proofs of this out there.

Let $X'$ be optimal for A.1, and let $c^tX' = \lambda$.

Assume for contradiction that the hypothesis is wrong:

$$\begin{bmatrix} A^t & -c\\ 0 & -1 \end{bmatrix} \begin{bmatrix} Y\\1\end{bmatrix} \le \begin{bmatrix} 0\\ 0 \end{bmatrix}, \quad \begin{bmatrix} b^t & -\lambda\end{bmatrix} \begin{bmatrix} Y\\1\end{bmatrix} \ge 0 \text{ is unsolvable.}$$

By Farkas' Lemma, we know the following system is solvable:

$$\begin{bmatrix} X & w_2\end{bmatrix} \begin{bmatrix} A^t & -c\\0 & -1\end{bmatrix} \ge \begin{bmatrix} b^t & -\lambda\end{bmatrix}, \text{ where $X,w_2 \ge 0$.}$$

Now, from the system above, we may write $XA^t \ge b^t$, and $Xc \le \lambda - w_2$.

If $w_2$ is greater than $0$, then we have found a contradiction with the assumption that $X'$ was optimal for A.1. However, one cannot reach that conclusion if $w_2$ is exactly $0$.

I feel like I can't be that far off from a correct complete proof as I've followed exactly the hint, and the use of Farkas' Lemma which was explained on the previous page. If someone could help me finish/correct the proof, I'd be greatly appreciative.

$\endgroup$
5
  • 3
    $\begingroup$ You can find several proofs of LP duality using Farkas' lemma on the internet by searching for "strong duality Farkas lemma". Perhaps you should check these before asking us. If you find the answer, you can answer your own question with the details. $\endgroup$ Jul 24, 2014 at 18:14
  • 2
    $\begingroup$ Your application of Farkas' lemma doesn't quite fit the lemma: you're replacing "strictly positive" with "non-negative" on the one hand, and an equality with an inequality on the other hand. Perhaps if you use the exact statement of the lemma you'll be able to see what's missing. $\endgroup$ Jul 24, 2014 at 18:15
  • $\begingroup$ @YuvalFilmus I've searched the internet, and while I've found many different proofs of this theorem, I haven't found one that is following the exact outline I'm working with here. – If >= is unsolvable, then > is unsolvable as well. If = is solvable, then >= is solvable as well. $\endgroup$
    – user7348
    Jul 24, 2014 at 18:30
  • 1
    $\begingroup$ All proofs using Farkas' lemma are essentially the same. Try using Farkas' lemma in a tighter way, which might help with the case $w_2 = 0$. $\endgroup$ Jul 24, 2014 at 18:30
  • $\begingroup$ @YuvalFilmus I simply disagree with the suggestion you're making. Are you saying that I'm a tiny tweak from having a correct proof? I've looked at modifying inequalities, but I don't see that it does anything. If you think you have a correction, then please type it up in an answer. I think that my work above is useless. I should edit my final comments that I'm near a solution. $\endgroup$
    – user7348
    Jul 24, 2014 at 18:33

2 Answers 2

1
$\begingroup$

The following is based on the book "Combinatorial Optimization" by Papadimitriou and Steiglitz (chapter 3)

On LP duality, they first state a theorem that when a LP has a feasible solution, the dual also has one and on optimality their costs are equal (Theorem 3.1 in the book, based on the simplex algorithm)

This follows from the fact that the dual cost is always dominated by the primal cost.

i.e let $x$ and $\pi$ the solutions to the primal and dual respectively, then (i.e $c'$ is transpose vector of $c$)

$$c'x \ge \pi'Ax \ge \pi'b$$

So if the primal has a feasible solution so does the dual and on optimality they (the costs) are equal.

Then the Farkas Lemma (theorem 3.5 in the book) is proved based on this theorem.

But one can reverse the proof of Farkas Lemma in the book and prove Th. 3.1 from Farkas Lemma (Th. 3.5)

A sketch:

Farkas' Lemma states that (as stated in book):

Given vectors $a_i \in R^n$, $i = 1,..m$ and another vector $c \in R^n$,

iff $y'a_i \ge 0, \forall i \implies y'c \ge 0$, then $c \in C(a_i)$ (i.e $c$ is in the cone generated by $a_i$)

Consider a LP:

$$\min{c'y}$$ $$a_i'y \ge 0, i =1..m$$ $$y \ne 0$$

The LP is feasible and bounded because $y = 0$ is a feasible point and $c'y \ge 0$ (by the lemma)

$c$ can be expressed as linear combination of the $a_i$'s using a vector $\pi$, where $\pi_i \ge 0$, i.e

$$c = \sum_1^m{\pi_i a_i}$$

Constructing the dual of the LP as:

$$A_j = col(a_{ij}, i=1..m) \in R^m$$ $$a_i = col(a_{ij}, j=1..n) \in R^n$$

gives the dual LP:

$$\max{0}$$ $$\pi'A_j = c_j, j = 1..n$$ $$\pi \ge 0$$

which has a feasible solution ($\pi$) and equal cost at optimality (strong duality theorem)

$\endgroup$
1
  • $\begingroup$ That's fine, but if you see my thread math.stackexchange.com/questions/878061/… One can simply take the system that I consider above, subtract a positive delta that's guaranteed to exist, and perform the same manipulations I performed above. At the end, you'll have a contradiction. Be sure to read the comments under my thread posting that I linked. These issues are discussed there. $\endgroup$
    – user7348
    Aug 5, 2014 at 17:31
-1
$\begingroup$

Instead of lambda use lambda - epsilon - one ends up with the desired contradiction. Hence for any epsilon >0 there exists a Y_eps s.t. b^T Y_eps > lambda - epsilon.Taking the maximum over all Y_epsilons, max (bT Y_eps) >= lambda. Hence they are equal. Is the maximum value is attained? That remains to be shown, but we can get as close as we want.

$\endgroup$
1
  • $\begingroup$ Welcome to Computer Science Stack Exchange. Please use LaTeX to write math. I cannot parse the syntax of your penultimate sentence: two occurrences of "is". $\endgroup$
    – babou
    Jul 14, 2015 at 23:00

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.