If $x$ is an element in a standard convex linear optimization set constrained by $Ax = b, x \geq 0$, then how can I prove $d$ is a feasible direction only if $Ad=0$ and $di \geq 0$ for every $i$ where $xi=0$?
Prove feasible direction
2
$\begingroup$
linear-programming
-
0Do you also have the condition $i \geq 0$? Otherwise the second condition does not make much sense since by taking $-i$ I would have $di \leq 0$ while still having $xi=0$ and then the condition could be met only if $di=0$ for all $xi=0$. But then why write the condition as an inequality in the first place. – 2010-10-13
-
0I'm also a bit confused by this. Do you mean $i$ to be a *subscript*? If so, your question makes perfect sense. – 2010-10-13
-
0Yes i is subscript, sorry i couldn't post it correctly – 2010-10-13
1 Answers
3
[EDITED after OP's clarification that $i$ is a subscript.]
If I get the idea of feasible direction right then it means that $x+\lambda d$ should be in the constraint set for some $\lambda>0$.
Suppose that $Ad \neq 0$. Then $A(x+\lambda d)=b+\lambda Ad \neq b$, violating the equality constraint.
Suppose that there is an $i$ such that $x_i=0$ but $d_i<0$. Then $x_i+\lambda d_i<0$ for all $\lambda>0$ and hence the non-negativity constraint would be violated.