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

```

• Prev by Date: Re: Random[BinomialDistribution[..]] wrong ?
• Next by Date: Normal Probability Plots
• Previous by thread: Re: How to solve system of inequalities?
• Next by thread: Re: How to solve system of inequalities?