Minimizing Sum of Absolute Values

[Ang Zhi Ping]

Would it be possible to find the minimum by squaring the function inside the absolute value signs then carrying out the necessary steps to find a minnima/maxima? I think this should work for any polynomial, not sure about other functions though.

The solution obtained using this method will not be the same as that in the original formulation, though it may possibly be close.

 

[awkward]

I recently encountered another problem, but it extends this topic. Instead of opening a new thread I guess this place is as good as any..

If one defines the function E=|1-x-y| + |4-2x-y| ... how can I find it's minimum now (x and y coordinates)? Can this be extended to N variables inside each absolute value? Each absolute value will be linear... I am not sure if the above answer can be generalized to suit this problem?

Any ideas?

Cheers,
Adrian

If you have access to a linear programming package, problems of this type can be solved by linear programming. In the above problem, we would reformulate the problem as follows:

minimize a + b + c + d
subject to
a - b = 1 - x - y
c - d = 4 - 2x - y
a, b, c, d >= 0

The trick is that if 1 - x - y \ge 0, then a = 1 - x - y and b = 0; otherwise a = 0 and b = - (1 - x - y). So a + b = |1 - x - y| in all cases.
You might think that other solutions are possible-- for example, if 1 - x - y = 2, then a = 3 and b = 1 seems to be an alternative solution that would mess things up. But this will never happen if you are using the Simplex Algorithm, because it is guaranteed to always find a solution at a vertex of the feasible polyhedron. At least one of a and b will always be zero.

 

[Aero51]

The solution obtained using this method will not be the same as that in the original formulation, though it may possibly be close.

Why? If you square the function and find the zeros, these points should correspond to where a derivative does not exist in the original function. Take a-x, for example, if you calculate the 0 point of (a-x)^2 you get a double root at x=a, consistent with the original formula. Squaring any higher order polynomial inside the absolute value function will still have roots at the location where the original function has no derivative. You can use this information to more quickly find the max/min of an absolute value function.

 

[Ang Zhi Ping]

Why? If you square the function and find the zeros, these points should correspond to where a derivative does not exist in the original function. Take a-x, for example, if you calculate the 0 point of (a-x)^2 you get a double root at x=a, consistent with the original formula. Squaring any higher order polynomial inside the absolute value function will still have roots at the location where the original function has no derivative. You can use this information to more quickly find the max/min of an absolute value function.

This method works if f(x) comprises of a single absolute term. If there are two or more terms, i.e. f(x,y) = |2x-y+3|+|x+3y+1| + |x-y+6|, the optimal solution which minimizes f is not the same as g(x,y) = (2x-y+3)^2+(x+3y+1)^2 +(x-y+6)^2, simply because there is no way to transform the second equation to the first.