[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
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?**
| |