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.

The question I'd like to ask is as in the title: How to determine whether a system of linear inequalities has a POSITIVE solution or not?

Is there any poly-time algorithm to do this? Or the best algorithms known are no less complex than algorithms for solving set of linear inequalities?

Thanks for any help,

Regards Michal

share|improve this question
    
Question posted at mathoverflow and was closed. Don't remember the link. –  user38268 Jan 15 '12 at 18:05
    
Note that search for positive solutions can be written as another general linear inequality because $x_i>0$ is just a linear inequality, so you can add it to your system and you still have a system of linear equalities. –  Thomas Andrews Jan 15 '12 at 18:43
    
@Benjamin: Two versions at MO were posted: This one and this one. They were both closed there. But, they're clearly on-topic here. –  cardinal Jan 15 '12 at 20:38

1 Answer 1

Your problem is known as Linear Programming (if you change positive to non-negative). Usually linear programming is thought of as an optimization problem, but in fact the optimization problem is equivalent to feasibility, which is exactly what you're asking: whether a system of inequalities has any solution.

If you really want to ask whether there's a positive solution, then what you can do is take your system of inequalities $Ax \geq b$ and add the constraint $x_i \geq m$, maximizing over $m$. If the maximum is $m > 0$, then there is a strictly positive solution, otherwise there isn't.

share|improve this answer

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.