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

1. Apr 5, 2012

### Assaf

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. Apr 7, 2012

### ajkoer

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.