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
    Do 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
  • 0
    I'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
  • 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.