Showing that if the Primal Program is unbounded then the dual is necessarily infeasible

Question

On my linear programming midterm we were asked the following question. I received a 5/10 on this so I would like to know where I went wrong in my explanation.

$$ \text{max } c^{T}x \\ \text{subject to } Ax \leq b \\ x \geq 0 $$

a) Write down the dual linear program.
b) Show from first principles (that means without using results of any theorems proved in class, you may of course use your knowledge of the proofs, but you need to provide complete explanation) that if the primal program is unbounded then the dual is necessarily infeasible.

Answer to part a was easy: $$ \text{min } b^{T}y \\ \text{subject to } A^{T}y \geq c \\ y \geq 0 $$

This was my answer to part B:

We pick $$y = \bigl(\begin{smallmatrix} y_{i} \\ \vdots \\ y_{m} \end{smallmatrix} \bigr) $$ and define a dual program such that $$ y^{T}\bigl(\begin{smallmatrix} a_{i} \\ \vdots\\ a_{m} \end{smallmatrix} \bigr) \geq c_{j} \\ j = 1, \dots, n $$

By definition these inequalities place an upper bound on our primal. That is all solutions $ S_{D} $ to dual give objective value greater than any primal solution. Therefore for an unbounded primal $ S_{D} $ is empty, which is the definition of infeasible.

Answer 1

You should watch out for the words "by definition". Unless you are literally using something you said while defining the thing you're talking about, you're probably sweeping something under the rug.

In your case, you defined the dual LP to have inequalities $A^T y \ge c$ (or, equivalently, $y^T A \ge c^T$), so you can say "by definition, a feasible solution satisfies the inequality $y^T A_j \ge c_j$ for all $j$, where $A_j$ is the $j$-th row of $A$" but not much else.

In particular, you failed to explain why "these inequalities place an upper bound on our primal". There's actual math to be done here: you can show that if $x$ is primal feasible and $y$ is dual feasible, then \begin{align} Ax \le b \text{ and }y \ge 0 &\implies y^TAx \le y^Tb \\ y^TA \ge c^T\text{ and }x \ge 0 &\implies y^TAx \ge c^Tx \end{align} and therefore $y^Tb \ge c^Tx$. This is not a "by definition" argument.

(And the words "these inequalities place an upper bound on our primal" themselves are not specific enough. Clearly they do nothing of the sort: the primal variables don't even occur in the inequalities. The existence of a dual solution places an upper bound on the value of any primal solution, by the argument above.)