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

[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 x₁,...,x_N):

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

2. A set of (usually n or more) absolute-value inequalities:
|Ʃb_mnx_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 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!

 

[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.