Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to solve a system of linear inequalities with absolute magnitudes?

  1. Apr 5, 2012 #1
    Hi everybody,

    I'd love to pick your brains about a problem in (seemingly?) linear algebra I've run into, trying to find the most efficient algorithm for solving a set of linear inequalities involving absolute magnitudes.

    During my research I've run into a problem that involves solving a set of linear (usually
    over-specified) system of equalities and inequalities. This set always assumes the following forms (let's call the unknowns x1,...,xN):

    1. One linear equality of the form:
    Ʃanxn = 0

    2. A set of (usually n or more) absolute-value inequalities:
    |Ʃbmnxn| > d, m=1,2,3..., M (usually M≥N)

    where d is some number that I set. Furthermore, the variables need to obey the constraint:

    3. |xn|<xmax
    (xmax is positive, of course)

    All coefficients and variables (an, bmn, xn) are real, although not necessarily positive.

    My questions are two.

    1. What is the most efficient way of solving such a system? Being fairly a novice in these matters, I've (naively?) implemented a mixed integer linear program (see, e.g., here), minimizing a constant function and subject to linear constraints, which runs fine and returns correct values: I can always substitute the answers into my system and see that they satisfy it, which they do. However, it's a non-polynomial solution and I was wondering if there is a more efficient way of doing so. It looks like a problem in computational geometry to me, since I'm trying to find a point on a hyperplane (defined by #1) "outside" a non-convex non-connected polyhedron defined by the inequalities (#2), but I've never taken any course in the subject and can't really tell.

    2. A somewhat harder question, which I don't know how to answer: is there an efficient (polynomial) algorithm for determining what is the largest possible value of d for which there exists a solution to the above problem? I could run some sort of binary search on d, but that seems like overkill to me.

    Any hints, references, ideas and general thoughts would be greatly appreciated. Thank you!
  2. jcsd
  3. Apr 7, 2012 #2
    In the case where d is always positive, convert |Ʃbmnxn| > d, (m=1,2,3..., M) into linear equalities by adding a positive dummy variable Em which is subject to Em>0.

    My recollection is that this is now in a standard form subject to positivity constraints. The theorem and associated geometric interpretation used to prove the solution routine may be of aid.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook