Re: How to solve system of inequalities?

*To*: mathgroup at christensen.cybernetics.net*Subject*: [mg1065] Re: How to solve system of inequalities?*From*: rubin at msu.edu (Paul A. Rubin)*Date*: Fri, 12 May 1995 16:10:54 -0400*Organization*: Michigan State University

In article <3oker8$jh7 at news0.cybernetics.net>, jeff at econ.berkeley.edu wrote: ->Hi. I have a system of linear inequlities specified symbolically. ->I want to test whether they are consistent. (i.e. whether the ->solution region is non-empty). I don't see how to do this and ->it is not covered in Wolfram's book. -> ->For example, I can surely type -> -> In[1] 1<0 -> ->and get back the expected -> -> Out[1] False -> ->But if I enter -> -> In[2] y<x && x<y -> ->I get back the unhelpful -> -> Out[2] y < x && x < y -> ->Apparently Mathematica cannot deduce that this is impossible. ->Is there any way to get Mathematica to tell me when a series of ->inequalities is logically consistent? The workaround I tried ->was to use ConstrainedMin which returns an error when the ->Constraint inequalities have empty solution region. The problem ->is that I need to enforce the inequalities to be strict and ->Constrained seems to be willing to assume weak inequalites when ->necessary. For example -> -> In[3] ConstrainedMin[x,{x<y,y<x},{x,y}] -> ->returns -> -> Out[3] {0, {x->0, y->0}} -> ->which is not what I wanted. -> ->There has got to be a simple way to do this, right? I think you're on the right track in using ConstrainedMin, although you need to be careful: ConstrainedMin assumes that all variables are restricted to being nonnegative. If that's not true in your problem, you can work around it in one of two ways: write every variable x as a difference x1-x2 of two new nonnegative variables; or add a single new nonnegative variable z, and replace every existing variable x with the difference x -> x1-z, where x1 is a new nonnegative variable. The former approach doubles the number of variables, the latter adds just one to the variable count, and they are equally valid. Now to the question of strict inequalities. I don't think you'll get a definitive answer, but you can try the following: Step 1: If necessary, change variables so that all variables are nonnegative, and (for convenience) move terms around so that all variables appear on the left side of each constraint, the right side containing only a number. Step 2: Add/subtract a new nonnegative "artificial" variable to each inequality, so that if the original inequality is violated, the artificial variable soaks up the violation. Thus blah blah blah <= number becomes blah blah blah - u <= number (same for strict <) and blah blah blah >= number becomes blah blah blah + v >= number (same for strict >), where u and v are the new artificial variables. You add one artificial variable per inequality. Step 3: Convert strict inequalities to weak inequalities by perturbing the right hand side by a "small" amount (but not so small that the perturbation is below the accuracy threshold of the number). Thus blah blah blah < number becomes blah blah blah <= number*(1-epsilon) and blah blah blah > number becomes blah blah blah >= number*(1+epsilon) where epsilon is a small positive number. If the right hand side is zero, subtract or add epsilon, rather than multiplying as above. Make sure you don't pick epsilon too small; you'll know it's too small if number*(1-epsilon) >= number or number*(1+epsilon) <= number evaluates to True. Step 4: Apply ConstrainedMin, using the sum of all artificial variables as the objective function, the modified inequalities as constraints, and the Join of the original variable list and the list of artificials as the variables. If you get a zero objective value, the modified inequalities are consistent, which implies the original ones are. If you get a nonzero objective value, the modified inequalities are inconsistent, which means that EITHER the original inequalities are inconsistent OR the original inequalities are (barely) consistent and you chose epsilon too large. (Sorry, it's not foolproof, but I doubt a foolproof method exists.) Good luck. Paul ************************************************************************** * Paul A. Rubin Phone: (517) 432-3509 * * Department of Management Fax: (517) 432-1111 * * Eli Broad Graduate School of Management Net: RUBIN at MSU.EDU * * Michigan State University * * East Lansing, MI 48824-1122 (USA) * ************************************************************************** Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. J. W. v. GOETHE