1
$\begingroup$

enter image description here

Hi, I've proved parts a and parts b, but I'm confused on how to prove part c. I think it should really follow directly from parts a and parts b but I'm lost. In part c, are we assuming that $x_j$ is not a null variable or that $x_j$ is a null variable?

If $x \in P$ and $x_j$ is a null variable then there exists some $p \in R^m$ for which $p'A \geq 0, p'b=0$ and such that the jth component of $p^TA$ is positive. Then $A^Tp>0$ since $(A^Tp)=(p^TA)^{T}$ so we are done.

But what happens if $x \in P$ and $x_j$ is not a null variable? Then there exists some $y \in P$ for which $y_j >0$ then I don't what to do. I'm confused what to do.

I've set up the primal and dual pairs for parts a:

Primal:

max $0^T x$

$Ax=b$

$x \geq 0$

Dual:

min $p^Tb$

$p^T A \geq 0$

$\endgroup$
  • $\begingroup$ I don't see how you proved part a. You seem to use the implication "$(A^T p)_j > 0 \Rightarrow x_j = 0$". Is that based on complementary slackness? If yes, that only tells something about an optimal $x$, not about all $x \in P$, right? I think you need a slightly different primal/dual pair. $\endgroup$ – LinAlg Nov 12 at 19:06
  • $\begingroup$ For part $c$, there is no assumption on $x_j$ being a null variable. A different way of phrasing question $c$ is: Suppose $Ax =b, x\geq 0, A^Tp \geq 0, p^Tb=0$, show that $x_j > 0$ or $(A^Tp)_j > 0$. $\endgroup$ – LinAlg Nov 12 at 19:12

Your Answer

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

Browse other questions tagged or ask your own question.