Clarifying commentary about the function: $f(x)=\displaystyle \sum_{i=1}^n |x-a_i|$ in Spivak's Calculus Problem 4b Chapter 11 Chapter 11 Problem 4b of Spivak's Calculus asks the user to find the minimum value of the following function for $a_1 \lt a_2 \lt \cdots \lt a_n$:

$f(x)=\displaystyle \sum_{i=1}^n |x-a_i|$

Beneath the initial question, Spivak adds the commentary:

This is a problem where calculus won't help at all: on the intervals between the $a_i$'s the function $f$ is linear, so that the minimum [point] clearly occurs at one of the $a_i$, and those are precisely the points where $f$ is not differentiable.

In the absence of graphing software, Spivak's claim did not make immediate sense to me. In this post, I aim to detail why Spivak's statement (with some minor modifications) is correct.

Firstly, we will establish equations for three relevant types of intervals useful to this problem:

*

*$(-\infty, a_1]$


*$[a_n, \infty)$


*$[a_i,a_{i+1}] \text{ for some } 1 \leq i \lt n$
For $x \in (-\infty, a_1]$, we see that for any $i$ in our list, $x-a_i \leq 0$ because $x \leq a_1 \lt \cdots \lt a_n$. This means that for any $i$ in our list: $|x-a_i| = -(x-a_i)$. Therefore, we can write:
\begin{align}
f_{(-\infty, a_1]}(x)&=(-1)\left(nx-\displaystyle \sum^n_{i=1}a_i\right) \\
&=-nx+\sum^n_{i=1}a_i \quad (\dagger)
\end{align}
Similarly, for $x \in [a_n, \infty)$, $x-a_i \geq 0$ because $ a_1 \lt \cdots \lt a_n \leq x$. This means that $|x-a_i|=x-a_i$. Thus, we can write:
\begin{align}
f_{[a_n,\infty)}(x)&=nx-\displaystyle \sum^n_{i=1}a_i \quad (\dagger \dagger)\\
\end{align}
For the third type of interval, consider the following argument:
Let $x \in [a_i,a_{i+1}]$ for some $1 \leq i \lt n$. Then $x \geq a_i$, which means that for any $k$ satisfying $1 \leq k \lt i$, we have: $a_1 \lt \cdots \lt a_k \lt \cdots \lt a_i\leq x$. Similarly, we also know that $x \leq a_{i+1}$. For any $\ell$ satisfying $i+1 \lt \ell \leq n$, we must then have $x \leq a_{i+1} \lt \cdots \lt a_{\ell} \cdots \lt a_n$. Consequently, we can write:
\begin{align}
f_{[a_i,a_{i+1}]}(x)&=(x-a_1)+ \cdots +(x-a_i)+(-1)(x-a_{i+1})+\cdots +(-1)(x-a_n)
\end{align}
In this expression, there are $i$ positive terms and there are $n-i$ negative terms. Therefore, we can simplify this to:
\begin{align}
f_{[a_i,a_{i+1}]}(x)&=ix-(n-i)x-\displaystyle \sum_{d=1}^i a_d + \sum_{d=i+1}^n a_d\\
&=(2i-n)x-\displaystyle \sum_{d=1}^i a_d + \sum_{d=i+1}^n a_d
\end{align}
Importantly, we see that each of the 3 equations derived is linear; the summations are simply constants. i.e. each equation is of the form $mx+b$.

Next, we will comment that at $x=a_i$ for any $1 \leq i \leq n$, $f$ is non-differentiable. To demonstrate this we need to show that for the given $a_i$, the following is true:

$\displaystyle \lim_{h \to 0^-}\frac{f(a_i+h)-f(a_i)}{h} \neq \lim_{h \to 0^+}\frac{f(a_i+h)-f(a_i)}{h}$

The proof structure has slight variations for $i=1$, $1 \lt i \lt n$, and $i=n$ (due to $f$ having a different mapping rule depending on which interval we are on). Each case is straightforward to prove, so we will accept the claim as true without proof .

Next, we will show that the global minimum point of $f$ must take place on the interval $[a_1,a_n]$.
Firstly, $f$ is definable every where on $\mathbb R$. Note that $f$ is a sum of individual absolute value functions. Absolute value functions are continuous. The sum of continuous functions is continuous. Therefore $f$ is continuous in all of $\mathbb R$.
Next, referencing $(\dagger)$, we see that for any $x \in (-\infty, a_1)$, $f'(x)=-n \lt 0$. This implies that $f$ is strictly decreasing on the interval $(-\infty, a_1]$. Similarly, referencing $(\dagger \dagger)$, for any $x \in (a_n, \infty)$, $f'(x)=n \gt 0$. This implies that $f$ is strictly increasing on the interval $[a_n, \infty)$.
Given the above information, consider the interval $(-\infty,a_1]$. Because $f$ is strictly decreasing on this interval, we can conclude that $a_1$ must be a minimum point for $(-\infty,a_1]$. Similarly, because $f$ is strictly increasing on the interval $[a_n, \infty)$, it must be the case that $a_n$ is the minimum point for this interval. Finally, consider the closed interval $[a_1,a_n]$. Because $f$ is continuous on this section, there exists a minimum point $m$ such that for any $x$ in $[a_1,a_n]$, $f(m) \leq f(x)$. We can therefore conclude that the global minimum point for $f$ must be found within $[a_1,a_n]$.

We will now show why the minimum point of $f$ coincides with an $a_i$. Additionally, we will demonstrate that there can actually be two consecutive $a_i$'s that the minimum coincides with (in addition to infinitely many points between those two different, consecutive $a_i$'s.)
Recall that the global minimum of $f$ must occur on the closed interval $[a_1,a_n]$. In the case of $n=1$, this closed interval is a singleton, and $a_1$ must therefore be the global minimum point.
In the event that $n \gt 1$, we use the following argument:
If $n \gt 1$, we see that the interval $[a_1,a_n]$ contains two types of points: finitely many $a_i$'s (where $f$ is non-differentiable) and all of the points between each $a_i$ (where $f$ is differentiable).
For the points between, consider the open intervals $(a_i,a_{i+1})$ for any $i$ satisfying $1 \leq i \lt n$. The equations for $f$ in this interval is: $$(2i-n)x-\displaystyle \sum_{d=1}^i a_d + \sum_{d=i+1}^n a_d$$
Taking the derivative of $f$ along one such interval yields:
$$f'(x)=2i-n \text { where } i \text{ and } n \text{ are constants}$$
In order for a point in a given $(a_i,a_{i+1})$ to be a minimum point, the derivative of $f$ must be $0$ at that point. To locate this critical point, we would want to see if $2i-n=0$.
There are two cases: 1) $n$ is odd 2) $n$ is even.
Importantly, if $n$ is an odd number, this can never happen for any $i$ because $2i$ is even and an even number minus an odd number will never equal $0$. For an odd $n$, we can therefore conclude that the minimum point does not occur at any of the points on any of the open intervals described by $(a_i,a_{i+1})$.
However, if $n$ is even, then there exists an $i'$ in our index that could certainly satisfy this. Consider $i'=\frac{n}{2}$. This amounts to saying that for an even $n$, the derivative of $f$ at every $x$ in $(a_{i'},a_{a'+1})=0$. This implies that $f$ is constant across this interval. At the the moment, we simply recognize that the minimum point may be every point in $(a_{i'},a_{i'+1})$ - note, just because $f'(x)=0$ does not mean that $x$ is a minimum/maximum point.
Continuing with Case 1 ($n$ is odd), we need to determine which of the finitely many $a_i$ is the minimum point. We will make use of a theorem that we implicitly invoked previously:

If for any $x \in (a,b)$, $f'(x) \lt 0$, and $f$ is continuous on $[a,b]$, then $f$ is strictly decreasing on $[a,b]$. Similarly, if for any $x \in (a,b)$, $f'(x) \gt 0$, and $f$ is continuous on $[a,b]$, then $f$ is strictly increasing on $[a,b]$. Finally, if for any $x \in (a,b)$, $f'(x) = 0$ and $f$ is continuous on $[a,b]$, then $f$ is a constant on $[a,b]$. These are all proven using the Mean Value Theorem.

Recall that the derivative for a given interval $(a_i,a_{i+1})$ is $2i-n$. It is easy to see that if we create a new function of the form $g(i)=2i-n$, we are, in fact, describing a line with positive slope. What this means is that as we move to the right from $[a_1,a_2]$, to $[a_2,a_3]$, ...to $[a_{n-2},a_{n-1}]$ to $[a_{n-1}, a_{n}]$, we will have consecutive negative slopes associated with each interval until abruptly switching to consecutive positive slopes with each interval. This means that there is some $a_{i^*}$ such that from $[a_1,a_{i^*}]$, $f$ is strictly decreasing and from $[a_{i^*},a_n]$, $f$ is strictly increasing.
To determine which $a_{i}$ exhibits this property, consider $\frac{n-1}{2}$ and $\frac{n+1}{2}$. For an odd $n$, this is as close to $0$ as we can get from the negative and positive sides (note that for an odd $n$, $i=\frac{n}{2}$ is not possible because $i$ must be a natural number). When $i=\frac{n-1}{2}$, we see that $2i-n=-1$.This corresponds to the slope for the interval $(a_{\frac{n-1}{2}},a_{\frac{n+1}{2}})$
When $i=\frac{n+1}{2}$, we see that $2i-n=1$. This corresponds to the slope for the interval $(a_{\frac{n+1}{2}},a_{\frac{n+3}{2}})$.
We can therefore state that on the interval $[a_1,a_{\frac{n+1}{2}}]$, $f$ is strictly decreasing, and on the interval $[a_{\frac{n+1}{2}},a_n]$, $f$ is strictly increasing. We can then conclude that for odd $n$, the global minimum point of $f$ occurs at $a_{\frac{n+1}{2}}$ which is the median of all such $a_i$.
Jumping back to Case 2, we can use a very similar argument. However, for this argument, note that because $n$ is even, the values that $2i-n$ can take on are slightly different: consider the numbers $\frac{n}{2}-1$, $\frac{n}{2}$, and $\frac{n}{2}+1$. If $i=\frac{n}{2}-1$, then $2i-n=-2$. This corresponds to the interval $(a_{\frac{n}{2}-1},a_{\frac{n}{2}})$.
As previously stated, if $i=\frac{n}{2}$, then $2i-n=0$. This corresponds to the interval $(a_{\frac{n}{2}},a_{\frac{n}{2}+1})$. Remember, $f$ is constant across this interval.
And if $i=\frac{n}{2}+1$, then $2i-n=2$. This correspond to the interval $(a_{\frac{n}{2}+1},a_{\frac{n}{2}+2})$.
Together, we can assert that $f$ is strictly decreasing on $[a_1,a_{\frac{n}{2}}]$, $f$ remains constant on $[a_{\frac{n}{2}},a_{\frac{n}{2}+1}]$, and $f$ is strictly increasing on $[a_{\frac{n}{2}+1},a_n]$. Collectively, this means that for an even $n$, the global minimum point of $f$ takes place at any point in $[a_{\frac{n}{2}},a_{\frac{n}{2}+1}]$
 A: You are making it a bit too hard. Even if you don't have to graph it, you should think of $x$ as sliding over the real line, and regard the absolute values as distances. This geometric idea really makes things more intuitive.
Given $a_1<a_2<\cdots<a_n$, obviously a global minimum will be achieved in $[a_1, a_n]$, because if $x$ approaches toward $a_1$ from the left, then all the distances $d(x, a_i) = |x-a_i|$ are decreasing. Similarly, the minimum cannot be achieved on the right of $a_n$.
Now assume $a_i<x<a_{i+1}$, and let $x$ gets slightly bigger, it becomes say $x+\delta$ and we still have $x+\delta<a_{i+1}$. Then the distances of $x$ to the points on the left of $x$ have all increased by $\delta$, and similarly the distances of $x$ to the points to the right of it have all decreased by $\delta$, therefore $f(x+\delta)-f(x) = i \cdot \delta - (n-i) \cdot \delta$. Thus $\frac{f(x+\delta) - f(x)}{\delta} = i - (n-i) = 2i-n$ is a constant even before taking $\delta\rightarrow 0$, hence $f'(x)=2i-n$ is a constant and $f(x)$ is linear over $(a_i, a_{i+1})$, and by continuity, $f(x)$ is also linear over $[a_i, a_{i+1}]$.
Note that as long as $2i - n \le 0\Leftrightarrow i\le n/2$, $f(x)$ is decreasing and $f(x)$ is increasing for $2i-n\ge 0\Leftrightarrow i\ge n/2$.
Therefore, if $n$ is even, a minimum is achieved at $x = a_{n/2}$ (and because $f'(x)=0$ when $i=2/n$, $f(x)$ is contant over $[a_{n/2}, a_{n/2+1}]$, hence $f(x)$ is minimized for any $x\in [a_{n/2}, a_{n/2+1}]$), and when $n$ is odd, a minimum is achieved at $x=a_{(n+1)/2}$.
Obviously, this has something to do with median. The trick is to consider the sum of distances of pairs: $d(x, a_1) + d(x, a_n)$, $d(x, a_2) + d(x, a_{n-1})$, $\cdots$. If $x$ is between $a_i$ and $a_j$, then $d(x, a_i) + d (x, a_j)$ is minimized, therefore we would like $x$ to lie between as many pairs as possible, and it should sit between the innermost pair.
A: $f(x)$ (in black) is a sum of copies of $g(x) = |x|$ (in gray) shifted around such that the "corner" of $g$ is at each of the $a_i$'s.
$f$ isn't differentiable at those points, but you can use a "fake calculus" approach to finding the minimum by considering the slope of $f$ at each point.
Note that each $g$ contributes $x$ to the slope of $f$ to the right of its $a_i$ and $-x$ to the left of its $a_i$. If you start out with all $a_i$'s on your right, the slope is $-nx$, and is incremented by $2x$ for each $a_i$ that you cross going in the positive direction. Therefore you want to have an equal number of $a_i$'s to the left and to the right in order to be at a minimum.
Hence $$f(x) = \sum_{i=1}^n |x - a_i|$$ is minimized by the median of the $a_i$'s.

