I've just read the the Duality Theorem of Linear Programming. Here is the proof from my book (and my questions after it):
Duality Theorem of Linear Programming: If the primal or dual linear program has a finite optimal solution, so does the other, and the corresponding values of the objective functions are equal. If either problem has an unbounded objective, the other problem has no feasible solution.
Proof. We note first that the second statement is an immediate consequence Weak Duality Lemma. For if the primal is unbounded and $\boldsymbol \lambda$ is feasible for the dual, we must have $\boldsymbol \lambda^T \textbf{b} \leq -M$ for arbitrarily large $M$, which is clearly impossible.
Second we note that although the primal and dual are not in symmetric form it is sufficient, in proving the first statement, to assume that the primal has a finite optimal solution and then show that the dual has a solution with the same value. This follows because either problem can be converted to standard form and because the roles of primal and dual reversible.
Suppose the primal linear program has a finite optimal solution with value $z_0$. In the space $E^{m+1}$ define the convex set
$C=\{ (r, \textbf{w}): r=tz_0-\textbf{c}^T\textbf{x}, \textbf{w}=t\textbf{b}-\textbf{Ax}, \textbf{x}\geq \textbf{0}, t \geq 0 \}$.
It is easily verified that $C$ is in fact a closed convex cone. We show that the point $(1,\textbf{0})$ is not in $C$. If $\textbf{w}=t_0\textbf{b}-\textbf{A}\textbf{x}_0 = \textbf{0}$ with $t_0 > 0, \textbf{x}_0\geq \textbf{0},$ then $\textbf{x}=\textbf{x}_0/t_0$ is
feasible for the primal linear program and hence $r/t_0=z_0-\textbf{c}^T\textbf{x}\leq\textbf{0};$ which means $r\leq0.$ If $\textbf{w}=-\textbf{A}\textbf{x}_0=\textbf{0}$ with $\textbf{x}_0 \geq \textbf{0}$ and $\textbf{c}^T\textbf{x}_0 = -1$, and if $\textbf{x}$ is any feasible solution to primal, then $\textbf{x}+\alpha\textbf{x}_0$ is feasible for any $\alpha\geq0$ and gives arbitrarily small objective values as $\alpha$ is increased. This contradicts our assumption on the existence of a finite optimum and thus we conclude that no such $\textbf{x}_0$ exists. Hence $(1,\textbf{0})\not\in C$.
Now since $C$ is a closed convex set, there is by Theorem $1$ (Separating and supporting hyperplanes) a hyperplane separating $(1, \textbf{0})$ and $C$. Thus there is a nonzero vector $[s, \boldsymbol \lambda] \in E^{m+1}$ and a constant $c$ such that
$$ s < c = \inf \{ sr + \boldsymbol \lambda^T\textbf{w}: (r, \textbf{w}) \in C \}.$$
Now since $C$ is a cone, it follows that $c\geq0$. For if there were a $(r,\textbf{w}) \in C$ such that $sr+\boldsymbol \lambda^T\textbf{w} < 0$, then $\alpha(r,\textbf{w})$ for large $\alpha$ would violate the hyperplane inequality. On the other hand, since $(0,\textbf{0})\in C$ we must have $c\leq0$. Thus $c=0$. As a consequence $s<0$, and without loss of generality we may assume $s=-1$.
We have to this point established the existence of $\boldsymbol \lambda \in E^m$ such that
$$-r+\boldsymbol \lambda ^T\textbf{w} \geq0$$
for all $(r,\textbf{w})\in C$. Equivalently, using the definition of $C$,
$$(\textbf{c}-\boldsymbol \lambda^T \textbf{A})\textbf{x}-tz_0 +t\boldsymbol \lambda^T\textbf{b}\geq0$$
for all $\textbf{x}\geq\textbf{0}, t\geq0$. Setting $t=0$ yields $\boldsymbol \lambda^T\textbf{A}\leq\textbf{c}^T$, which says $\boldsymbol \lambda$ is feasible for the dual. Setting $\textbf{x=0}$ and $t=1$ yields $\boldsymbol \lambda^T\textbf{b} \geq z_0$, which in view of the Weak Duality Lemma and its corollary shows that $\boldsymbol \lambda$ is optimal for the dual. $\blacksquare$
I have two questions:
The sentence: "Now since $C$ is a cone, it follows that $c\geq0$." I didn't understand this point. It was unclear for me, can someone explain it in other words or show why is it so?
Does this proof overall hold only if $C$ is a closed convex cone as was assumed in the proof?
Thank you for any help! =)
Please let me know if something is unclear in the proof (I might have done typos) or if you need more info from my book.
P.S.
here you can see the Duality Theorem of Linear Programming from my book: https://i.stack.imgur.com/U9SFY.jpg
and here you can see the Theorem 1 used in the proof: https://i.stack.imgur.com/BO9JE.jpg
The convex cone C is closed, therefore it can be strictly separated from the point $(1,\mathbf{0})$. If $C$ wasn't closed you couldn't do that strictly. Therefore, there exists $(s, \mathbf{\lambda})$ and $\epsilon >0$ such that for every $(r,\mathbf{w}) \in C$, the following holds (I noted $\langle, \rangle$ the inner product) : $$ \langle (1, \mathbf{0}), (s, \mathbf{\lambda}) \rangle < \langle (r, \mathbf{w}), (s, \mathbf{\lambda}) \rangle -\epsilon $$
Now suppose there exists $(r,\mathbf{w}) \in C$ such that $\langle (r, \mathbf{w}), (s, \mathbf{\lambda}) \rangle <0$. Then, $C$ being a cone, for every $\alpha >0$ you have $\alpha(r, \mathbf{w}) \in C$, where this is a scalar product. Getting $\alpha \to \infty$, you have $\alpha (r, \mathbf{w}), (s, \lambda) \rangle\to -\infty$. Therefore, you'll be able to find a very large $\alpha$ such that : $$\langle \alpha (r, \mathbf{w}), (s, \lambda) \rangle = \alpha \langle (r, \mathbf{w}), (s, \lambda) \rangle < \langle (1, \mathbf{0}), (s, \lambda) \rangle = s$$ because the latter is a fixed real number. THis inequality would be contradictory with the separating inequality exposed earlier.
This argument is frequently used in convex analysis and is linked with the basic properties of cones. To be sure you understand, you could just compare it with the classical following statement : let $L$ be a linear functional of a real vector space $E$. If $L$ is bounded from below (i.e. if there exists $a \in \mathbb{R}$ such that for every $v\in V, L(v) > a$), then $L(v) = 0$ for every $v\in V$. In your problem, the argument is the same, except that your linear functional $(s, \lambda)$ is bounded from below only over a cone, not over the whole vector space. This is why you can only derive $L(v) \geq 0$.