How to find out the global minimum of the following expression

What is the global minimum of the expression \begin{align} |x-1| &+ |x-2|+|x-5|+|x-6|+|x-8|+|x-9|+|x- 10| \\&+ |x-11|+|x-12|+|x-17|+|x-24|+|x-31|+ |x-32|? \end{align}

I've solved questions of this sort before but there were only 3 terms. I solved those by expanding all the terms in the modulus and drawing a graph. This question came in a paper which requires the student to solve it within 5 minutes. What's a better method?

Solution 1:

You can in principle write out the function in a lot of intervals. But it would probably take too long. However, I will use this fact, without doing it explicitly. We know that if we do write this function, it is going to be linear on each interval (sum of linear functions is a linear function), and it's going to be continuous (sum of continuous functions is a continuous function). We also know that on a line you get minimum at one end, the other, or both (constant line). So all you need to do is to calculate your function at $1,2,5,6,...$ and find the minimum.

Solution 2:

Unfortunately I needed some minutes to think about the problem before finding a solution that can be calculated very quickly:

Imagine the graph of the function $f_a(x)=|x-a|$. Having the graph in mind you see that the derivation $f'(x)=-1$ for $x<a$ and $f'(x)=1$ for $x>a$.

For the intervals: $(-\infty,1)$, $(1,2)$, $(2,5)$, ..., $(32,\infty)$ we can now easily calculate the derivative $f'(x)=f'_1(x)+f'_2(x)+f'_5(x)+...-f'_{32}(x)$:

In the range $(-\infty,1)$ it is $f'(x)=-1-1-1-...-1+1=-11$.
In the range $(1,2)$ it is $f'(x)=+1-1-1-...-1+1=-9$.
In the range $(2,5)$ it is $f'(x)=+1+1+1-...-1+1=-7$.
...

In every step we simply have to invert one sign so "-1" becomes "+1". This means the derivative is changing by 2 at the points x=1,2,5,...

We start by calculating the derivative for $x<1$; it is -11.

Now we simply go through the ranges:

<1: -11
1..2: -9
2..5: -7
5..6: -5
6..8: -3
8..9: -1
9..10: +1
10..11: +3
11..12: +5
12..17: +7
17..24: +9
24..31: +11
31..32: +13
>32: +11

At $x=32$ the derivation decreases by 2 because of the minus sign before $|x-32|$; you could of course adapt this method for sums of elements of the form $b|x-a|$.

We see that for $x<9$ the derivation is negative and for $x>9$ the derivation is positive. We also know that the function is continuous. (This is important because the derivation is not defined at x=1,2,5,...) This means that the function is strictly decreasing respectively increasing for $x<9$ and for $x>9$.

So we know that the global minimum must be at $x=9$.

Solution 3:

The answer (minimizer) in this case is $10$, the median of the sequence $$(1,2,5,6,8,9,10,11,12,17,24,31,32).$$

You can plug in $x=10$ in the function and you would find that the minimum value is $96$. In general, the solution to the following minimization problem

$$\min\{|x-a_1| + |x-a_2| + \cdots + |x-a_n|\}$$ is the median of $(a_1,\ldots,a_n)$. To see why, consider first when $n=2$, and without loss of generality assume $a_1<a_2$. Then $|x-a_1|+|x-a_2|$ is the distance between $x$ and $a_1$ plus the distance between $x$ and $a_2$. It is easy to see that only when $x$ is in the middle of $a_1$ and $a_2$ should the sum of distances be minimal, which equals $|a_2-a_1|$ in this case. In this case the minimizer is not unique. Any points in $[a_1,a_2]$ is a minimizer.

When $n=3$, the function is $|x-a_1|+|x-a_2|+|x-a_3|$, and we order the parameters again so that $a_1<a_2<a_3$. When $x$ coincides with $a_2$, i.e. $x=a_2$, the value becomes $|a_2-a_1|+|a_2-a_3|=|a_3-a_1|$, the distance between $a_3$ and $a_1$. But when $x\in[a_1,a_3], x\neq a_2$, the value of the function is $$|x-a_2|+|x-a_1|+|x-a_3| = |a_3-a_1| + |x-a_2|,$$ which is largar than $|a_3-a_1|$, the distance between $a_3$ and $a_1$. Similarly the value would become larger when $x$ is outside $[a_1,a_3]$. So in this case, the minimizer is unique and is equal to $a_2$, the median of $(a_1,a_2,a_3)$.

In general, when $n$ is odd, there exists a unique minimizer, which is equal to the (unique) median of the parameters $(a_1,\ldots,a_n)$. When $n$ is even, the function is minimal and constant over the range $[a_i,a_j]$, where $a_i$ and $a_j$ are the two middle values.

Solution 4:

TL;DR: Put the absolute values in ascending order, and look at the sum of the leading coefficients. One by one, change the signs in the sum from right to left. When the sum changes signs, you have passed a local extremum. When the sum equals zero, there is an extremum on an entire interval.

As an alternative to Andrei's excellent answer, or perhaps an extension, you could also look at the derivative. Clearly the function is continuous everywhere, and it is differentiable in all but finitely many points, call them $a_1,\ldots,a_n$ in ascending order. Then we want to minimize $$f(x)=\sum_{k=1}^nc_k|x-a_k|=\sum_{k=1}^n(-1)^{\delta_{x\leq a_k}}c_k(x-a_k),$$ where $\delta$ denotes the Kronecker delta, in this case defined as $$\delta_{x\leq a_k}:=\left\{\begin{array}{ll}1&\text{ if } x\leq a_k\\0&\text{ otherwise}\end{array}\right..$$ This has derivative (for all $x$ apart from the $a_k$) $$f'(x)=\sum_{k=1}^n(-1)^{\delta_{x\leq a_k}}c_k.$$ The expression has a local minimum at $x$ if either $f'(x)=0$, or if $x=a_k$ for some $k$ and $f'(y)<0$ for $a_{k-1}<y<a_k$ and $f'(y)>0$ for $a_k<y<a_{k+1}$.

This is all rather formal; in practice this means you put the $c_k$ in ascending order, so here $n=13$ and $c_1=\cdots=c_{12}=1$ and $c_{13}=-1$, and find all $m$ such that flipping the last $m$ signs in the sum $$c_1+c_2+c_3+c_4+c_5+c_6+c_7+c_8+c_9+c_{10}+c_{11}+c_{12}+c_{13}$$ makes the sum change signs compared to changing the last $m-1$ signs. Here a quick look gives $$c_1+c_2+c_3+c_4+c_5+c_6-c_7-c_8-c_9-c_{10}-c_{11}-c_{12}-c_{13}=1,$$ $$c_1+c_2+c_3+c_4+c_5-c_6-c_7-c_8-c_9-c_{10}-c_{11}-c_{12}-c_{13}=-1,$$ so $f$ has a local minimum at $a_6=9$, and it is not difficult to see that there is no other minimum.