2
$\begingroup$

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$?

  • 0
    Yes$i$is subscript, sorry i couldn't post it correctly2010-10-13

1 Answers 1

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.

  1. Suppose that $Ad \neq 0$. Then $A(x+\lambda d)=b+\lambda Ad \neq b$, violating the equality constraint.

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