5
$\begingroup$

Say we have the equation $Ax>b$, where $A$ is an M-by-N matrix, $b$ is a known vector of length N, x is an unknown vector of length N, and the inequality sign means that each element of $Ax$ is greater than the corresponding element of $b$. Is there some linear-algebra-based method, such as e.g. some modification of LU decomposition or something similar, that would be amenable to programming on a computer and which would allow me to generically solve this system for $x$, given numerical values for $A$ and $b$? I will also accept any method of determining merely whether a solution exists, if not any solutions themselves.

EDIT: I should clarify that I'm mainly working with matrices with N and M both less than 10, so an exact method that works analogously to e.g. LU decomposition will probably be faster than an iterative method.

$\endgroup$
6
  • $\begingroup$ this is what linear programming all about !! $\endgroup$
    – alkabary
    Jun 3, 2015 at 1:40
  • $\begingroup$ Yeah, but I had trouble finding resources for solving this inequalities question numerically. Everyone seems to only want to talk about the $Ax=b$ case. $\endgroup$
    – Izzhov
    Jun 3, 2015 at 1:42
  • 2
    $\begingroup$ A relevant article: Avis and Kaluzny, "Solving inequalities and proving Farkas's lemma made easy". $\endgroup$
    – user21467
    Jun 3, 2015 at 2:07
  • $\begingroup$ Like alkabary said: Linear Programming en.wikipedia.org/wiki/Linear_programming That doesn't mean Linear Algreba. Also en.wikipedia.org/wiki/Simplex_algorithm for a numerical method. $\endgroup$
    – muaddib
    Jun 3, 2015 at 2:08
  • $\begingroup$ That's not what I'm looking for. That solves $Ax=b$ with each $x_i>0$. I'm looking for the solution of $Ax>b$, i.e. every element of $Ax$ is greater than every element of $b$. $\endgroup$
    – Izzhov
    Jun 3, 2015 at 2:12

1 Answer 1

3
$\begingroup$

LU decomposition is effectively doing book-keeping of Gaussian elimination. The analog of Gaussian elimination for solving a linear system of inequalities is Fourier-Motzkin elimination. This procedure is not useful in practice.

You are asking for $Ax>b$, but it might be easier to think about it in the following way:

  • Linear algebra is for $Ax=b$
  • Linear programming is for $Ax=b$, where $x\geq0$

Somehow adding that inequality gives you a leap in difficulty and expressiveness.

If you are looking to implement something yourself, you will almost surely have to learn about the Simplex Method. The Simplex Tableu gives an easy way to code a naive implementation.

To see how to convert your problem into the standard form $Ax=b$ with $x\geq 0$, see http://ocw.mit.edu/courses/sloan-school-of-management/15-053-optimization-methods-in-management-science-spring-2013/tutorials/MIT15_053S13_tut06.pdf

$\endgroup$
5
  • $\begingroup$ The second thing you wrote is not what I'm looking for. $Ax=b$ with $x>0$ is not the same thing as $Ax>b$. Reread my question. $\endgroup$
    – Izzhov
    Jun 3, 2015 at 2:14
  • $\begingroup$ I have already in my question repeated what you are asking for. Do you see that? I have not misread your question. These two equations are both forms of linear programming problem. You can convert from one form to another. Can you explain why you need the strict inequality in your application? $\endgroup$
    – Gus
    Jun 3, 2015 at 2:19
  • $\begingroup$ I fail to see how you can convert from $Ax > b$ to $Ax = b$ with $x \geq 0$. I need the strict inequality because in my application, $b$ is actually zero on the right hand side, so if the equation were $Ax \geq 0$, it would be trivially solved by $x=0$. I'm mainly just trying to see if any solution exists to my problem, I'm not as interested in finding the whole space of solutions or finding a minimum or maximum among them. $\endgroup$
    – Izzhov
    Jun 3, 2015 at 2:22
  • $\begingroup$ Also, in my original problem that I stated in the question. I don't want the constraint $x \geq 0$. $x$ may have negative entries in my problem. $\endgroup$
    – Izzhov
    Jun 3, 2015 at 2:25
  • 3
    $\begingroup$ Let me state it a different way. If you give me $A,b$ corresponding to $Ax\geq b$, I can give you a $C,d$ such that a solution of $y$ in $Cy=d, y\geq 0$ corresponds to a solution of $x$ in your original problem. If you want to avoid the trivial solution, then solve $Ax \geq \epsilon\mathbf{1}$ where $\mathbf{1}$ is an appropriately sized vector of $1$s and $\epsilon$ is some very small number greater than zero. $\endgroup$
    – Gus
    Jun 3, 2015 at 2:32

You must log in to answer this question.

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