Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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. –  Jyotirmoy Bhattacharya Oct 13 '10 at 2:24
    
I'm also a bit confused by this. Do you mean $i$ to be a subscript? If so, your question makes perfect sense. –  Mike Spivey Oct 13 '10 at 13:47
    
Yes i is subscript, sorry i couldn't post it correctly –  Mark Oct 13 '10 at 14:19
add comment

1 Answer

up vote 2 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.