Hi everybody,(adsbygoogle = window.adsbygoogle || []).push({});

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 x_{1},...,x_{N}):

1. One linear equality of the form:

Ʃa_{n}x_{n}= 0

2. A set of (usually n or more) absolute-value inequalities:

|Ʃb_{mn}x_{n}| > 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. |x_{n}|<x_{max}

(x_{max}is positive, of course)

All coefficients and variables (a_{n}, b_{mn}, x_{n}) 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 thelargestpossible 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!

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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?

**Physics Forums | Science Articles, Homework Help, Discussion**