Minimizing Sum of Absolute Values

adoado

What is the reasoning for this?

Redbelly98

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

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

I am not sure the reasoning to it, or exactly what you mean 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

Given [itex]f(x) = \sum_{i}|a_{i}x+b_i|[/itex], you can use a convex optimization solver as [itex]f(x)[/itex] 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. [itex]x_i = -\frac{b_i}{a_i}[/itex]. 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 [itex]|a_i|[/itex].
3. Sort the array according to knee point coordinates, in ascending order.
4. When [itex]x=-\infty[/itex], the slope of [itex]f(x)[/itex] is [itex]-\sum_{i}|a_i|[/itex].
5. Run through the array of structure to compute the new slope at each knee point. This can be done by adding the current [itex]|a_i|[/itex] in each array element to the current running slope of [itex]f(x)[/itex].
6. The minimum point of [itex]f(x)[/itex] is reached when the current running slope reaches 0. The associated solution [itex]x^{*}[/itex] 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 [itex]O(n\log{n})[/itex], due to the sorting procedure in step (3). It would be good if somebody can introduce an algorithm which runs in linear time .

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

Otherwise, the above algorithm can be adapted for the case of [itex]f(\vec{x})= \sum_{i}|\vec{a_{i}}^{T}\vec{x}+b_i|[/itex], by holding all but one variable in [itex]\vec{x}[/itex] 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 [itex]\vec{x}[/itex] to start the iteration is [itex]-A^{\dagger}\vec{b}[/itex], where the rows of [itex]A[/itex] are [itex]\vec{a_{i}}^{T}[/itex], and the entries of [itex]\vec{b}[/itex] are [itex]b_i[/itex].

An algorithm which jointly optimizes for all variables in [itex]\vec{x}[/itex] 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

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

awkward

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 [itex]1 - x - y \ge 0[/itex], then [itex]a = 1 - x - y[/itex] and [itex]b = 0[/itex]; otherwise [itex]a = 0[/itex] and [itex]b = - (1 - x - y)[/itex]. So [itex]a + b = |1 - x - y|[/itex] in all cases.
You might think that other solutions are possible-- for example, if [itex]1 - x - y = 2[/itex], then [itex]a = 3[/itex] and [itex]b = 1[/itex] 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 [itex]a[/itex] and [itex]b[/itex] will always be zero.

Aero51

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

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