In: Advanced Math
Prove that if the primal minimisation problem is unbounded then the dual maximisation
problem is infeasible.
Suppose this is not the case, so that the dual maximization problem
is feasible, but the primal minimization problem
is unbounded.
Fix a feasible solution to the dual problem.
Then
, so that for
all
we have
Since the primal problem is unbounded, for every there
is
such that
and
. But
then, from
we get
However, recall that is a fixed vector, and
is a
fixed feasible solution to the dual. Therefore,
is a real
constant. Thus, the above shows that for every
we have
, a
constant; this is absurd.
Therefore, the dual problem must be infeasible.