## Minimizing Sum of Absolute Values

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,

 PhysOrg.com science news on PhysOrg.com >> 'Whodunnit' of Irish potato famine solved>> The mammoth's lament: Study shows how cosmic impact sparked devastating climate change>> Curiosity Mars rover drills second rock target
 You need to look at piecewise defined functions: $$|a x + b| = \left\{\begin{array}{l} |a| \left| x + \frac{b}{a} \right|, a \neq 0 \\ |b|, a = 0 \end{array}\right.$$ and use: $$|x| = \left\{\begin{array}{l} x, x \ge 0 \\ -x, x < 0 \end{array}\right.$$ If you have n linear terms, the number of segments increases linearly and is equal to $n + 1$.
 Thanks Dickfore for your fast reply! Sorry, I am not sure how this helps with minimizing the function, though?

## Minimizing Sum of Absolute Values

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

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

 Quote by adoado Thanks Dickfore for your fast reply! Sorry, I am not sure how this helps with minimizing the function, though?
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.

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

 Quote by 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
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! )

Mentor
Blog Entries: 10
 Quote by adoado This logic seems to be correct, no? So simply finding the smallest critical point should be the minimum itself?
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.

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

 Quote by Redbelly98 That was my thought as well. I'm not 100% sure of this, but ... would the minimum be at the critical point for the expression with the steepest slope?
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?

 @dharapmihir: No, they are completely arbitrary.

Mentor
Blog Entries: 10
 Quote by 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?
My reasoning was in error. It's true if there are only two terms, but not in general.

 Recognitions: Science Advisor Suppose you have $f(x) = |f_1(x)| + |f_2(x)| + \dots + |f_n{x}|$ If all the $f_i$ are linear functions, then $f(x)$ is piecewise linear and its minimum will be at an $x$ value where one of the $f_i(x) = 0$. To show this, draw a picture: the graph of each $f_i$ is two straight lines forming a V shape. So, you can find the minimum by finding the $n$ values of $x$ at the "corners" of the graph, and checking the corresponding values of $f(x)$. If some of the $f_i$ 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 $f_i(x) = 0$ (including no roots, of course) so the number of "corners" of the graph is not necessarily $n$. 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!

 Quote by adoado Hello all, [snip] P.S. LaTeX seemed to be stuffing up, it would never update in the preview box? Any help greatly appreciated! Cheers, Adrian
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.

 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)