1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ the idea is certainly correct $\endgroup$ – gt6989b Mar 29 '17 at 16:09
  • $\begingroup$ 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. $\endgroup$ – Omar Wali Mar 29 '17 at 16:11
2
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.