How to find minimum of sum of mod functions?

Question

How to find minimum value of $$|x-1| + |x-2| + |x-31| + |x-24| + |x-5| + |x-6| + |x-17| + |x-8| + \\|x-9| + |x-10| + |x-11| + |x-12|$$ and also where it occurs ?

I know the procedure for find answer for small problems like the following

what is the minimum value of |x-2| + |x+3 | + |x-5| and where it occurs ?

Here it is easy to visualise and give answer or even possible mathematically using equations as

Let the point be at distance c from $x = -3$ so the sum of the distances from the $3$ points $x =2$ , $x=-3$ , $x=5$ are $5-c$ , $8-c$ and $c$ respectively ,so total distance is minimum when it is 8 as $x=-3$ and $x=5$ are the farthest and they are $8$ units away so the required point must lie within this region so

$$ 5-c + 8-c + c = 8 $$ $$ c = 5 $$ so the point where minimum value occurs is at $x =2$

to find the minimum value substitute it in equation to get value as 8.

But In this problem it is hard to do it this way as there are more points .

Is there any easy way to find the answer .

Thanks

Answer 1

Let's make it generic, you want to minimise

$$f(x) = \sum_{k = 1}^n \lvert x - p_k\rvert,$$

where, without loss of generality, $p_1 \leqslant p_2 \leqslant \ldots \leqslant p_n$.

How does the value of $f(x)$ change if you move $x$

• left of $p_1$,
• between $p_k$ and $p_{k+1}$,
• right of $p_n$?

A simple counting argument finds the location of the minimum.

Answer 2

As you pointed out, the expression gives the sum of the distances of $x$ from the various points.

Imagine that you are somewhere to the left of all the points, and start walking to the right. For every tiny step you take, say of length $s$, the sum of your distances to the points decreases by $12s$.

This is true until you reach the point $x=1$. Then for a while, if you take a tiny step $s$, your distance from $1$ increases by $s$, but your distance from each of the other $11$ points decreases by $s$, so the sum of the distances decreases by $11s-s=10s$.

This continues until you hit $x=2$. After that, for a while, every tiny step of length $s$ increases your distances from $1$ and $2$ by $s$ each, and decreases your distances from each of the others by $s$, for a total decrease of $8s$.

Keep walking. When you reach the next point in the list, which is $5$, each tiny step of length $s$ gives you a net decrease of $6s$. Continue. When you reach $6$ and take a small step, the sum decreases by $4s$. When you reach $8$ an move right, the decrease is $2s$.

Finally, when you reach $9$, and take a small step, the distance from each of the $6$ points to your left increases by $s$, but the distance from each point to your right decreases by $s$, so there is no change in the sum.

Finally, when you reach $10$ and continue walking to the right, the sum of the distances starts to increase.

So the minimum sum is reached at all points between $x=9$ and $x=10$. To find the minimum sum, evaluate at say $x=9$.

Remark: We used a lot of words in order to try to describe what was going on. But basically you move right until half the points are to your left and half are to your right. If we have instead points $a_1,a_2,\dots,a_n$, where $n$ is odd, the minimum is reached at the median of the points $a_i$. The answer is the same if $n$ is even, but there will be an interval of medians.