15
$\begingroup$

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?

$\endgroup$
1
9
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ The right answer. Congratulations! Although I don't know if your method works when the number of terms is even, say $f(x) = |x-1|+ |x-2|$ or $f(x) = |x-11|+|x-12|+|x-17|+|x-24|$ (the minimum or maximum is an interval). $\endgroup$
    – David
    Nov 25 '18 at 22:20
  • $\begingroup$ @David Why should it be a problem if a whole interval represents the minimum or maximum? In the example of $|x-1|+|x-2|$ we would have $f'(x)=0$ in the whole interval 1...2. $\endgroup$ Nov 26 '18 at 6:28
  • $\begingroup$ This answers the previous version of my typo question but the method is absolutely wonderful. Thanks! $\endgroup$
    – user619072
    Nov 27 '18 at 17:36
15
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ I like how this answer asks us to imagine the graph of the function. I find this "imagine" technique useful, while still being intuitive. Similar examples includes "imagine the multiplication table of this finite group" (the group could be huge) or "imagine the truth table for this proposition" (the formula could be long). $\endgroup$
    – Alex Vong
    Nov 25 '18 at 22:02
5
$\begingroup$

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.

$\endgroup$
10
  • 1
    $\begingroup$ That doesn't seem to be correct. Wolfram says the minimum is 51 at x=9. See here $\endgroup$ Nov 25 '18 at 20:50
  • 3
    $\begingroup$ I see now that the confusion comes from the $−|x−32|$ in the problem statement @MartinRosenau. Note the minus sign. Fei Li solved it for a + sign. $\endgroup$ Nov 25 '18 at 21:18
  • 1
    $\begingroup$ I plot the graph using wxmaxima and get the same result as @IlikeSerena. Note the minus sign at the end. $\endgroup$
    – Alex Vong
    Nov 25 '18 at 21:48
  • 1
    $\begingroup$ Maybe the OP @CaptainQuestion made a typo. We need his or her classification, but I think the purpose of this question is exactly what I have demonstrated. $\endgroup$
    – Fei Li
    Nov 25 '18 at 22:00
  • 1
    $\begingroup$ @AlexVong So I hoped, but the next sentence "which equals $|a_2-a_1|$ in this case." excludes this interpretation. $\endgroup$
    – Servaes
    Nov 25 '18 at 22:39
1
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy