I am considering the following question:

Suppose that two constraints in a system are cx $\leq$ 1 and dx $\leq$ 1, where c and d are linearly dependent. If cd $\geq$ 0 does this mean that one of c or d is redundant?

Intuitively, I would say the answer is yes, one of the constraints is redundant. Because cd $\geq$ 0, both c and d are pointing in the same direction (i.e. they are both positive or both negative), any constraint imposed by one will either make redundant or be made redundant by the other. I am having trouble fully forming this idea and proving it more formally - any tips?


Yes, one of them is redundant. We can assume that both c and d are not zero, because if one of them were 0 that inequality is clearly redundant.

If both c and d are not zero:

$$x \le \frac{1}{c} \qquad \text{and} \qquad x \le \frac{1}{d}$$

And clearly one of these inequalities is redundant because you only need to consider the one with the smallest bound and the other will be automatically fulfilled.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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