1
$\begingroup$

I have really no idea where to go in this problem. This is from Bertsimas Introduction to Linear Optimization, Exercise 4.26. My teacher would like us to create a primal and dual LP to solve the following:

Let A be a given matrix. Show that exactly one of the following alternatives must hold.

(a) There exists some $x \neq 0$ such that $Ax = 0, x ≥ 0$.

(b) There exists some p such that $p'A > 0$.

$\endgroup$
0
$\begingroup$

My teacher released the answers, hopefully this helps someone else:

Primal : $Max\ c'x\ subject\ to\\ Ax = 0\\ x \ge 0$

Dual: $Min\ 0'p\ subject\ to\\ A'p \ge c$

Assuming $c > 0$

From now on youl have to excuse me if I write A'p vs p'A. Just know that they mean the same thing.

(a) If some x* satisfies $Ax\* =0$ then we can say that the primal is feasible and unbounded, since any positive multiple of c'x* will still satisfies $Ax = 0$ and increase the objective function. From weak duality, we know that since the primal is unbounded but feasible, the dual must be infeasible. This shows that no p can satisfy $A'p \ge c > 0$ or $A'p > 0$. Thus, if (a) is true (b) cannot be true.

(b) We can see the dual problem is feasible, since p has no restrictions and a solution to the constraints is simply $p = A^{-1} c$. Knowing the problem is feasible, we can see the optimal solution is simply $0$. We can also see that the primal is feasible, since $x = 0$ is a feasible solution. From strong duality (and i think weak duality) we can say that since both problems are feasible, their optimal solutions must be equal. The duals optimal solution is 0 so the primal must also be optimal at 0. Since c is strictly positive and x is non-negative, we conclude that the only x that satisfies this is $x = 0$, proving that is (b) is true (a) cannot be true.

$\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.