3
$\begingroup$

enter image description here


Let $P=\{x\in\mathbb{R}^n|Ax=b,x\geq0\}$ be a nonempty polyhedron, and let $m$ be the dimension of the vector $b$. We call $x_j$ a null variable if $x_j=0$ whenever $x\in P$. (b) prove that if $x_j$ is a null variable, then there exists some $p\in\mathbb{R}^m$ for which $p'A\geq 0', p'b=0$, and such that the $j$th component of $p'A$ is positive AND (c) if $x_j$ is not a null variable, then by definition, there exists some $y\in P$ for which $y_j>0$. Use the results in parts (a) and (b) to prove that there exist $x\in P$ and $p\in\mathbb{R}^m$ such that $p'A\geq0', p'b=0, x+A'p>0$

I did prove part (a) which was fairly easy to compute simply by multiplying $p'$ on the both sides of $Ax=b$. However I am struggling solving both (b) and (c). I am assuming $p\in\mathbb{R}^m$ is a dual variable and since $x_j$ is a null variable, $j$th constraint of dual can be removed. I also think that $j$th component of $p'A$ is positive because otherwise $x\notin P$, i.e. $Ax\neq b$. But I don't clearly see it. I am completely lost on part (c) as well. Any help would be very appreciated.

$\endgroup$
  • $\begingroup$ Are you familiar with Farkas's lemma? $\endgroup$ – Misha Lavrov Nov 12 at 1:56
  • $\begingroup$ @MishaLavrov Just a bit. I've learned the definition and some applications of farkas's lemma. $\endgroup$ – jackDanielle Nov 12 at 2:02
  • $\begingroup$ This problem seems like another one of those applications. $\endgroup$ – Misha Lavrov Nov 12 at 2:12
0
$\begingroup$

For (a) and (b), the proof is similar to that of Farka's lemma. Hint: Consider the dual of the LP $$\max \, \left\{e_j'x : x \in P\right\}.$$

For (c), we can classify the indices into two groups, i.e. ones with null variables and the others without. For each $j$ such that $x_j$ is a null variable, we can find a $p^j$ such that the conditions are met. Now let $p$ be the sum of these $p^j$s. We have that $$ p'A\ge 0', \quad p'b=0, \\ \quad (A'p)_j > 0, \; \forall j: x_j \, \text{is a null variable}. $$

Finally, for each $i$ such that $x_i$ is not a null variable, there exists $y^i \in P$ such that $y^i_i > 0$. Let y be the average of these $y^i$s. We have that $$ y \in P \; \text{and} \; y_i > 0, \; \forall i: x_i \, \text{is not a null variable,} $$

and that $y + A'p > 0$.

$y$ and $p$ are as desired.

Note: If there are no null variables, we can simply set $p=0$. If all variables are null, any feasible $y$ will suffice.

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