[Date Index] [Thread Index] [Author Index]

Re: How to solve system of inequalities?

• To: mathgroup at christensen.cybernetics.net
• Subject: [mg1081] Re: How to solve system of inequalities?
• From: rubin at msu.edu (Paul A. Rubin)
• Date: Sun, 14 May 1995 19:31:25 -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).

[Insert sound of hand smacking forehead here.]  I was gratuitously 
complicated with my previous answer, which relied on the determination of 
an ephemeral epsilon.  While exchanging e-mail on this with Daniel 
Lichtblau at WRI, and stimulated by an obnoxiously repetitive test of our 
fire alarm, I figured out a better way to answer the question.  Let's 
assume that you write your system of inequalities as A . x < b.  
(Extension to mixed systems of strong and weak inequalities will be 
obvious.)  Solve the linear program ConstrainedMin[ A[[i]] . x, A . x <= b, 
x ] once for each i, getting solution vector u[[i]] (so u is a list of 
vectors) and objective value f[[i]].  If f[[i]] == b[[i]] for any i, your 
goose is cooked (the i-th strong inequality is inconsistent with all other 
relaxed inequalities).  Assume then that f[[i]] < b[[i]] for all i.  Let v 
= (Plus @@ u)/Length[ u ], the average of the solution vectors.  Since, for 
every i, A[[i]] . u[[j]] <= b[[i]] for all j and A[[i]] . u[[i]] < b[[i]], 
it follows that A[[i]] . v < b[[i]] for every i.  So v solves the original 
inequalities.

Incidentally, you don't really need to minimize every possible constraint. 
 If the i-th solution satisfies A[[j]] . u[[i]] < b[[j]] for some j > i, 
you can skip the j-th objective.

I think it's still more efficient to solve one linear program with 
artificial variables (as I suggested in my last post), so I might try my 
luck at guessing an epsilon first.  If I can't shake out the artificial 
variables with a plausible guess for epsilon, I might then resort to this 
sequence-of-linear-programs stuff to nail down the infeasibility of the 
system.

I think.  They're *still* setting off that fire alarm, and my cognitive 
circuits are starting to shut down.

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