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

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.

• the idea is certainly correct – gt6989b Mar 29 '17 at 16:09
• right, I didn't think I was too far off with my idea. but my track record with math as an undergrad is that my proofs usually don't have the required rigor and I'd like to fix that. – Omar Wali Mar 29 '17 at 16:11

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.