Proof of Strong Duality Via <PERSON>
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$
<PERSON> 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. 563
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 <PERSON>, 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 <PERSON> which was explained on the previous page. If someone could help me finish\correct the proof, I'd be greatly appreciative. 768