Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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 – GBa Oct 13 '10 at 14:19
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|cite|improve this answer

Your Answer


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.