Minimise absolute values of weighted sum of numbers

Question

Part of my problem is to minimise the absolute value of the weighted sum of certain numbers. I have to find the weights.

Let's say I have a set of numbers A, a1, a2, a3 and a4, such that(a1, a2 > 0), (a3, a4 < 0)

Minimum weight is, say, 0.1 (10%), maximum is 0.4 (40%). I am looking for weights w in such a way that the weighted sum is zero; if zero is not possible, then the closest possible to zero. A simple linear model can be used to achieve this:

Minimise E

E >= SUM w * a
E >= -(SUM w * a)
SUM w = 1
w >= 0.1 for all w
w <= 0.4 for all w

A simple linear program is enough to find the solution very fast. However, I would very much like to find a polynomial algorithm or formula for this problem. Any ideas? Is this problem well known?

Thanks!

Answer 1

Minimizing (resp. maximizing) SUM w * a is easy; set all weights to the minimum and then from the least a to the greatest (resp. greatest to least) increase the weight respecting the local maximum until the global maximum is achieved.

If the [min, max] interval contains 0, then an optimal solution can be realized as a convex combination of these two solutions. Otherwise, take the solution closer to 0.

Answer 2

The ellipsoid algorithm was the first worst-case polynomial-time algorithm for linear programming.

However, I suspect you want to solve your problem fast, that is why you are interested in a polynomial-time algorithm.

In that case, you will be better off with the simplex method. Even though the simplex is exponential in the worst case, it seems to be the best choice for most practical applications. Not surprisingly, it is implemented in all the good quality solvers that I know of.