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 the matrix D and the 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 it's 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,\, and\,c^tX\, \le\, Y^tb $.
My attempt at a solution picking 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}$, $\begin{bmatrix} b^t & -\lambda\end{bmatrix}$ * $\begin{bmatrix} Y\\1\end{bmatrix} \ge\, 0$ 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}$ Where X, $w_2$ are $\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 is $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.
Best Answer
I will give the proof with revised notation. Consider the same primal and dual, to prove strong duality (given weak duality holds), it's equivalent to prove the system below is feasible. $$\{Ax\geq b;A^T y\leq c;c^Tx-b^Ty\leq 0;x\geq0;y\geq0\}$$ Suppose not, we have the alternative system is feasible, which implies system $$\{A^T\lambda-cw_2\leq0;-A\mu+bw_2\leq0;b^T\lambda-c^T\mu>0;\lambda\geq0;\mu\geq0;w_2\geq0\}$$ If $w_2>0$, we have $$0\geq [\mu^T(A^T\lambda-cw_2)+\lambda^T(-A\mu+bw_2)]=w_2(b^T\lambda-c^T\mu)>0$$ Which leads to contradiction.
if $w_2=0$, we have the system $$\{A^T\lambda\leq 0; -A\mu\leq0; b^T\lambda-c^T\mu>0;\lambda\geq0;\mu\geq0\}$$ is feasible, which then implies the alternative system $$\{Ax\geq b; x\geq0; A^Ty\leq c; y\geq0\}$$ is not feasible, which contradict to the assumption that LP has a finite optimal solution, hence feasible. To be more rigorous, suppose $\{A^Ty\leq c;y\geq0\}$ is not feasible. (As we know primal is feasible). We have, the alternative system is feasible. $$\exists x'\in\{Ax'\geq0;x'\geq0;c^Tx'<0\}$$ Notice primal is feasible, consider a feasible solution $x$ to primal, we have take $\alpha>0$, $A(x+\alpha x')\geq b$, $(x+\alpha x')\geq0$, and we can arbitrarily push $\alpha$ to infinity, which contradict to that primal optimal solution is finite.