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