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:

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

 

[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]

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.

 

[chiro]

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

 

[adoado]

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

 

[Redbelly98]

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.

 

[dharapmihir]

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

 

[adoado]

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?

 

[adoado]

@dharapmihir: No, they are completely arbitrary.

 

[Redbelly98]

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.

 

[AlephZero]

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 infinite number of "corners" in a finite range of x values - but don't worry about crossing that bridge till you come to it!

 

[awkward]

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.

 

[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)

 

[adoado]

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

 

[Redbelly98]

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.

 

[dharapmihir]

@Redbelly98 : Exactly what I want to say

 

[Redbelly98]

No problem.

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

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.

 

[adoado]

Awesome, thanks everybody for your help! That answers the question!

 

[adoado]

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

 

[Redbelly98]

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.

 

[Redbelly98]

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.

 

[adoado]

If that's not clear, let me know.

I am not sure the reasoning to it, or exactly what you mean :tongue2: Able to elaborate on the reasoning of this?

Cheers!
Adrian

 

[Redbelly98]

Okay.

First, consider just one absolute value expression,

z=|ax + by + c|.​

The line defined by ax+by+c = 0 divides the xy plane into two regions. In one region, the absolute value argument is positive and

z = ax+by+c​

On the other side of the line ax+by+c=0, the absolute value argument is negative and

z = -ax-by-c.​

So the graph of z is of two tilted half-planes that meet along the line ax+by+c=0. Hopefully you can visualize that.

Next consider several absolute value expressions,

z = |a₁x + b₁y + c₁| + |a₂x + b₂y + c₂| + ...​

Setting each absolute value argument a_ix + b_iy + c_i=0, we get several intersecting lines in the xy plane, dividing the xy plane into distinct regions as shown in this figure:

Within each region, the graph of z(x,y) is of a tilted plane. Each region is described by a different plane, and adjacent planes intersect along one of the lines. The entire graph resembles a polyhedral surface, and the minimum of the function must occur at one of the vertices of the "polyhedron", namely at an intersection of a pair of lines.

So you have to find the intersection of each pair of lines, and evaluate z(x,y) at all such intersection points.

 

[adoado]

Awesome, thanks a lot Redbelly! Really appreciate that! :)

 

[Ang Zhi Ping]

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

Given $f(x) = \sum_{i}|a_{i}x+b_i|$, you can use a convex optimization solver as $f(x)$ is a convex function.

Without plodding through a convex solver manual, one can efficiently find the minimum point using the below method:

1. Compute all knee point coordinates of each absolute term, i.e. $x_i = -\frac{b_i}{a_i}$. The knee point is where the sharp vertex is if each absolute term is plotted on its own.
2. Create an array of structures (if you are using either C or MATLAB to program), where each entry is associated with each absolute term, containing the knee point coordinate and the absolute slope $|a_i|$.
3. Sort the array according to knee point coordinates, in ascending order.
4. When $x=-\infty$, the slope of $f(x)$ is $-\sum_{i}|a_i|$.
5. Run through the array of structure to compute the new slope at each knee point. This can be done by adding the current $|a_i|$ in each array element to the current running slope of $f(x)$.
6. The minimum point of $f(x)$ is reached when the current running slope reaches 0. The associated solution $x^{*}$ is given by the knee point coordinate of the entry in the array where the algorithm terminates.

The above algorithm has an overall runtime complexity of $O(n\log{n})$, due to the sorting procedure in step (3). It would be good if somebody can introduce an algorithm which runs in linear time .

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

Once again the objective is convex hence a convex solver can be applied.

Otherwise, the above algorithm can be adapted for the case of $f(\vec{x})= \sum_{i}|\vec{a_{i}}^{T}\vec{x}+b_i|$, by holding all but one variable in $\vec{x}$ as constant. The algorithm has to be applied repeatedly to every variable in a round robin fashion. Convergence is guaranteed, but I cannot put a bound on the number of iterations required. A good initial value for $\vec{x}$ to start the iteration is $-A^{\dagger}\vec{b}$, where the rows of $A$ are $\vec{a_{i}}^{T}$, and the entries of $\vec{b}$ are $b_i$.

An algorithm which jointly optimizes for all variables in $\vec{x}$ is welcomed.

 

[Aero51]

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.

 

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