I'm trying to understand the solution to this question in Bertsimas 4.29: Question: Let $a_1,....a_m$ be some vectors in $R^n$ with $m>n+1$. Suppose that the system of inequalities, $a_i'x \geq b_i,i=1,....m$ does not have any solutions. Show that we can choose $n+1$ of these inequalities, so that the resulting system of inequalities has no solutions.

The solution given is: enter image description here Questions:


  1. Why is the polyhedron, $P$ considered with the transposes $A^Tp=0, b^Tp=1$ as opposed to $p^TA=0^T$

  2. Why does theorem 4.7 imply that if $x$ is a solution to the subsystem we must have $0^T x=0 \leq -1$? I also don't get how this is implied by $\hat{p}^T A=0^T, \hat{p}^T b=1, p \geq 0$. Theorem 4.7 is given as:

enter image description here

Where does the $-1$ come from in the inequality $0 \leq -1$ is my main question. Thank you.


Notice that $p^TA = 0^T \iff A^Tp=0$, these two conditions are equivalent, so it doesn't matter if we consider its transpose or not.

To use theorem $4.7$,

Notice that $\hat{p}^T(-A)=0^T$, here in theorem $4.7$, $c=0$. We also have $p\ge 0$, and $\hat{p}^T(-b) =-1 \le -1$, here $d=-1$. That is part $(b)$ of condition $4.7$ holds, then we conclude that result for part $(a)$ holds

If $\hat{x}$ is a solution to the subsystem, then $(-A)x\le (-b)$, hence we have $c'x=0 \le d = -1$ which is a contradiction.


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.