In weak duality theorem, we assume $x_i$ and $y_i$ are feasible. But how could we show a primal program is unbounded by this theorem?
Suppose we have a primal program: $\max \mathbf c^\top \mathbf x, \mathbf A\mathbf x \leq \mathbf b, \mathbf x \geq 0$ such that:
$\mathbf A$ has no rows which are all zero, $\mathbf c$ is not the zero vector, $c_j \geq 0$ for $j=1,\dots,n$ and $a_{ij} \leq 0$ for $i=1,\dots,m$ and $j=1,\dots,n$.
It seems obvious that this LP is always unbounded, but how to apply weak duality here?
Best Answer
Weak duality for maximization problems asserts that the if $\mathbf{p}$ is a feasible solution to the dual problem, and $\mathbf{x}$ is a feasible solution to the primal problem, then
$$\mathbf{p}^{T}\mathbf{b} \geq \mathbf{c}^{T}\mathbf{x}.$$
Unfortunately, the classic corollary in this case states that:
You want something like the converse of the first statement in the corollary. If you show that the dual is infeasible, then the primal must be unbounded or infeasible by weak duality, and then you just have to show that the primal is feasible.