Proof of Strong Duality Via Farkas Lemma

Question

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.

Answer 1

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)

Answer 2

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.