Minimizing Sum of Absolute Values

  • Thread starter adoado
  • Start date
  • #1
72
0

Main Question or Discussion Point

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
 

Answers and Replies

  • #2
2,967
5
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].
 
  • #3
72
0
Thanks Dickfore for your fast reply!

Sorry, I am not sure how this helps with minimizing the function, though?
 
  • #4
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
 
  • #5
chiro
Science Advisor
4,790
131
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.
 
  • #6
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
 
  • #7
2,967
5
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.
 
  • #8
chiro
Science Advisor
4,790
131
After reflecting, my method is the generalized version, and a simpler method posted by other users might be a better alternative.
 
  • #9
72
0
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! :smile:)
 
  • #10
Redbelly98
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
12,100
129
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.
 
Last edited:
  • #11
The terms after these are like a series (like |0.25-4x|,|0.125-8x| and so on) right??
 
  • #12
72
0
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?
 
  • #13
72
0
@dharapmihir: No, they are completely arbitrary.
 
  • #14
Redbelly98
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
12,100
129
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. :blushing:
 
  • #15
AlephZero
Science Advisor
Homework Helper
6,994
291
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!
 
  • #16
329
0
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.
 
  • #17
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)
 
Last edited:
  • #18
72
0
...But it will be at some critical point provided that all the terms in the absolute value are linear.
What is the reasoning for this?
 
  • #19
Redbelly98
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
12,100
129
What is the reasoning for this?
Between each adjacent pair of critical points, the function is linear. Therefore, no minima or maxima will lie between the critical points -- unless the slope happens to be zero, which is possible.
 
  • #20
@Redbelly98 : Exactly what I want to say
 
  • #21
Redbelly98
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
12,100
129
No problem.

Here's a representative graph. (Ignore the zj-1, etc. This comes from a google image search and I took the best graph I could find):

F5.small.gif

In general, the minimum could be at any one of the critical points. In some special cases, there could be a horizontal line for part of the function -- but even then evaluating the function only at the critical points will yield the minimum value.
 
  • #22
72
0
Awesome, thanks everybody for your help! That answers the question!
 
  • #23
72
0
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 [tex]E=|1-x-y| + |4-2x-y| ...[/tex] 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? :confused:

Cheers,
Adrian
 
  • #24
Redbelly98
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
12,100
129
If there are just two terms for E, then find x and y so that both terms are zero.

If there are more than two terms for E, I will have to think about it some more.
 
  • #25
Redbelly98
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
12,100
129
Okay, I've got it.

You need to consider all possible pairs of expressions, and find (x,y) where both terms in the pair equal zero.

Then evaluate E at all such points, and take the minimum.

So if E has three terms, there are 3 ways to pair up the terms.
If E has four terms, there are 6 ways to pair them up.
Etc.

If that's not clear, let me know.
 

Related Threads on Minimizing Sum of Absolute Values

  • Last Post
Replies
2
Views
8K
  • Last Post
Replies
6
Views
5K
  • Last Post
Replies
8
Views
8K
  • Last Post
Replies
2
Views
5K
  • Last Post
Replies
4
Views
19K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
10
Views
2K
Replies
1
Views
4K
  • Last Post
Replies
3
Views
4K
  • Last Post
Replies
3
Views
12K
Top