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