# How to show a primal program is unbounded by using weak duality?

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?

-

## 1 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:

• If the optimal cost of the primal problem is unbounded, then the dual is infeasible.
• If the optimal cost of the dual problem is unbounded, then the primal is infeasible.

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.

-