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