10
$\begingroup$

It is well known how to solve a system of linear equations $A{\bf x} = {\bf b}$, but how do we solve a system of linear inequalities $A{\bf x} \leq {\bf b}$?

For the applications I have in mind the most important questions are: (1) determining whether there are any solutions, and if so (2) finding the dimension of the solution set.

If it makes things any easier, the case ${\bf b} = {\bf 0}$ is of particular interest -- how can we effectively compute the dimension of the polyhedral cone $A{\bf x} \leq {\bf 0}$?

This seems closely related to linear programming since we are asking to find the dimension of the feasible region. But just to be clear -- we don't really care about finding any particular solutions, or optimizing an objective function; we only want to know the dimension of the feasible region. I am hoping that this is easier than linear programming in general.

I am especially interested in practical algorithms, but if you know any related theory that would be welcome as well.

Improve this question
$\endgroup$
3
  • 12
    $\begingroup$ There's a standard reduction which shows your question (1), testing whether there is a solution to a set of linear inequalities, is just as hard as finding the optimum, i.e., as hard as linear programming. Your question (2) is equivalent to both of these questions, since you can answer it by repeatedly solving a linear programming problem. As for practical algorithms, there are tons of linear programming packages out there. The best ones are expensive, but there are some decent free ones, and many mathematical software packages like MATLAB, Maple, Mathematica, have reasonable ones. $\endgroup$
    – Peter Shor
    Commented Jul 17, 2010 at 19:22
  • 9
    $\begingroup$ Continuing my previous comment, if you want to see the reduction, question (1) is called the feasibility problem for linear programming, and you should be able to find the proof that it's equivalent to lienar programming by googling or looking in linear programming textbooks. $\endgroup$
    – Peter Shor
    Commented Jul 17, 2010 at 19:25
  • 2
    $\begingroup$ to go along with Peter Shor's answer, may I also suggest using Octave or Scilab, which are open-source software packages with the same capabilities as Matlab and Mathematica (and also able to run some of the same Matlab scripts and functions with minimal changes) $\endgroup$
    – sleepless in beantown
    Commented Oct 11, 2010 at 5:46

3 Answers 3

Reset to default
5
$\begingroup$

Look into Fourier-Motzkin:

http://en.wikipedia.org/wiki/Fourier%E2%80%93Motzkin_elimination

Improve this answer
$\endgroup$
4
$\begingroup$

These notes by Ted Ralphs, Lehigh University, give you an answer to question 2, computing the dimension.

Improve this answer
$\endgroup$
1
$\begingroup$

Question 1 can be answered by forming an artificial problem and applying simplex method (look for two-phase simplex method in google). Question 2: If what you mean by dimension of the solution set is the number of extreme points, then we know from linear programming theory that the number of extreme points will be ${n+m}\choose{m}$, where $n$ is the number of variables and $m$ the number of inequalties. Remember that all interior points in the polyhedron may be represented as convex combinations of the extreme points, so that knowledge of the extreme points is sufficient to characterize all the solution set.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .