I've been trying to prove the Strong Duality Theorem following these slides. In those slides, we start with proving Farkas' lemma, then a corollary followed by the proof of the Strong Duality Theorem. To prove Farkas' lemma, I first proved that $\{A(x)|x \in X_n\}$ where $X_j = \{x=(x_1,x_2 \dots x_j) \in \mathbb{R}^j | x_i \geq 0 \text{ for all } 1\leq i \leq j\}$ and $A \in M(m,n)$, is a closed, convex set. This was deceptively hard and has been discussed in these answers. Using this I managed to prove the following:
Let $b\in \mathbb{R}^m$. Exactly one of these two linear programs have a solution:
\begin{align}
Ax&=b\\
x &\in X_n \nonumber
\end{align}
\begin{align}
(A^Ty) &\in X_n\\
\langle b,y \rangle &< 0 \nonumber\\
y &\in \mathbb{R}^m
\end{align}
This is Farkas' lemma. I also managed to prove this "corollary". I put it in quotes because I could not use the Farkas' lemma directly to get the result. The corollary is as follows: Let $b\in \mathbb{R}^m$. Exactly one of these two linear programs have a solution:
\begin{align}
Ax+s&=b\\
x &\in X_n \nonumber\\
s &\in X_m \nonumber
\end{align}
\begin{align}
A^Ty &\in X_n \nonumber\\
\langle b,y \rangle &< 0 \\
y &\in X_m \nonumber
\end{align}
The final step of this puzzle, which directly proves the Strong Duality Theorem is what I am trying to solve. This is what I am trying to prove now: For any $\alpha \in \mathbb{R}$, $b\in \mathbb{R}^m$, and $c\in \mathbb{R}^n$, prove that exactly one of these two linear programs have a solution:
\begin{align}
Ax+s&=b\\
\langle c,x \rangle &\leq \alpha \nonumber\\
x &\in X_n \nonumber\\
s &\in X_m \nonumber
\end{align}
\begin{align}
\langle b,y \rangle + \alpha z&< 0 \\
A^Ty + cz&\in X_n \nonumber\\
y &\in X_m \nonumber\\
z &\in \mathbb{R}_+ \nonumber
\end{align}
Here are my questions:
- Is there a way to prove Farkas' corollary using Farkas' lemma?
- How do I prove the last step from Farkas' corollary?
Best Answer
The first system of the last alternative is $$ Ax+s = b, \ \langle c,x\rangle \le \alpha, \ x\ge 0, \ s \ge0. $$ Introducting a slack variable $t\ge 0$, this can be written as $$ \pmatrix{A& I & 0 \\ c^T&0 & 1} \pmatrix{ x \\ s \\ t} = \pmatrix {b \\ \alpha } $$ with $x\ge0,s\ge0,t\ge0$. By Farkas Lemma, either this system or the following one is solvable: $$ \pmatrix{A^T & c\\ I & 0 \\ 0 & 1} \pmatrix{y \\ z} \ge 0 $$ $$ b^Ty + \alpha z < 0, $$ which is the second alternative in the last system.