Minimizing Sum of Absolute Values

adoado

Hello all,

I am trying to solve a problem based on some computer programming task I am trying to solve, and I have encountered a situation I am having trouble continuing..

Given a function f(x)=|1-x| + |0.5-2x| ...

How can I find it's minimum efficiently? This sum may extend to 4 or 5 more absolute values. I can try using calculus, but I found the derivative was messy, and I was not sure how to find it's zeros.

P.S. LaTeX seemed to be stuffing up, it would never update in the preview box?

Any help greatly appreciated!

Cheers,
Adrian

Dickfore

You need to look at piecewise defined functions:

[tex]
|a x + b| = \left\{\begin{array}{l}
|a| \left| x + \frac{b}{a} \right|, a \neq 0 \\

|b|, a = 0
\end{array}\right.
[/tex]

and use:

[tex]
|x| = \left\{\begin{array}{l}
x, x \ge 0 \\
-x, x < 0
\end{array}\right.
[/tex]

If you have n linear terms, the number of segments increases linearly and is equal to [itex]n + 1[/itex].

adoado

Thanks Dickfore for your fast reply!

Sorry, I am not sure how this helps with minimizing the function, though?

dharapmihir

hey adrian
I tried your problem by graphical approach
The last absolute value in the series i.e., |0.5-2x| in the above example will be equal to zero at x=0.25. This is the value of x for which the value of whole function will be minimum.
This is valid for any number of terms. Just find the value of x for which the last absolute value is equal to zero
I hope this solves your problem
Mihir

chiro

I'm not sure if this method is feasible, but you could possibly expand the definition for each segment of the function (ie each absolute function) and create every permutation of the function (ie |x| = x, x > 0, -x for x <= 0) so if you had N absolute segments the number of permutations would be 2^N.

Then you have continuous functions in a given range. Then you will have to do some extra partitioning to figure out all of the functions that share the same range.

Once you have partitioned the functions into functions that have the same range, you can then use normal optimization techniques for each partition (partitions are those of the real line being that of the domain of x).

After you've done that you simply find the minimum of all of the results from your optimization routine for every partition.

You could program a computer to do that for a finite number of segments, and if the segments were pretty small, it shouldn't take too long.

dharapmihir

I still do not get why my method is not feasible.
Because for any number of segments of absolute values, the slope of the function is negative only for the values of x lesser then the smallest critical point. The slope of the function is positive for the other segments(i.e.,segments of values of x greater than the smallest critical point). So the minimum value of the function has to be at the smallest critical point

Dickfore

Because you have a sum of several linear functions defined on a segment, the result is a piecewise linear function. Depending on the sign of the slope, the linear functions attain their minima on the left (for negative slope) or right (for positive slope) side of the segment. Thus, the minima can only be on the boundary points on each segment, or possibly at infinity. You need to work out an algorithm for finding which point has that minimum.

chiro

After reflecting, my method is the generalized version, and a simpler method posted by other users might be a better alternative.

adoado

This logic seems to be correct, no? So simply finding the smallest critical point should be the minimum itself?

@chiro: Expanding each function piecewise means a lot of resultant functions, and a lot of extra mathematics.. there must be an easier way, as it will become infeasible once the number of absolute functions grows.. (although thanks for the input! )

Redbelly98

That was my thought as well.

[EDIT: The following is not true, please ignore it...]

I'm not 100% sure of this, but ... would the minimum be at the critical point for the expression with the steepest slope?

So for the OP's example, f(x)=|1-x| + |0.5-2x|, the expression with the slope of ±2 will determine the minimum point -- just solve 0.5-2x=0 to find it.

dharapmihir

The terms after these are like a series (like |0.25-4x|,|0.125-8x| and so on) right??

adoado

What's the reasoning? I minimized this by Wolframalpha:

y =|1-5x| + |0.5-2x|+ |36-6x|

And the result is 139/4 at x = 1/4. If that were true, the steepest slope would be -6x, giving a minimum at 6 instead?

adoado

@dharapmihir: No, they are completely arbitrary.

Redbelly98

My reasoning was in error. It's true if there are only two terms, but not in general.

AlephZero

Suppose you have [itex]f(x) = |f_1(x)| + |f_2(x)| + \dots + |f_n{x}| [/itex]

If all the [itex]f_i[/itex] are linear functions, then [itex]f(x)[/itex] is piecewise linear and its minimum will be at an [itex]x[/itex] value where one of the [itex]f_i(x) = 0[/itex].

To show this, draw a picture: the graph of each [itex]f_i[/itex] is two straight lines forming a V shape.

So, you can find the minimum by finding the [itex]n[/itex] values of [itex]x[/itex] at the "corners" of the graph, and checking the corresponding values of [itex]f(x)[/itex].

If some of the [itex]f_i[/itex] are not linear functions, you also need to check for minima the intervals between the "corners", either numerically or using a calculus based method. There may be any number of roots of each equation [itex]f_i(x) = 0[/itex] (including no roots, of course) so the number of "corners" of the graph is not necessarily [itex]n[/itex]. In the worst case, there could be an infinte number of "corners" in a finite range of x values - but don't worry about crossing that bridge till you come to it!

awkward

I got so frustrated that I almost quit using this site, until some kind person told me that there is a bug in the Latex processor which requires the user to click the Refresh button in his browser.

dharapmihir

If the terms are arbitrary then the method I suggested is not valid.
In that case you will have to find all the critical points and find the value of function at each critical point and then decide the minimum.
The minimum of function may not be at the smallest critical point.
But it will be at some critical point provided that all the terms in the absolute value are linear.
If they are not linear then you will have to write the function piecewise and check all the points where the derivative is zero(and also all the critical points)