Find the minimum value of $f(x)=\sum_{i=1}^n |x-a_i|$. Let $a_1 \lt a_2 \lt \dots \lt a_n$.
Find the minimum value of $f(x)=\sum_{i=1}^n |x-a_i|$.
My guess is the minimum occurs at the middle point. However, I don't know how to show this since I can't use calculus here. What kinds of idea should I use? I would greatly appreciate any help.
 A: Okay how is this answer?
Let $x$ be in any interval $[a_{j-1},a_j]$. Now let $y$ be in $[a_j,a_{j+1}]$, and $|x-a_j|=|y-a_j|$. Then $|y-a_i|=|x-a_i|+|y-x|$ if $i\le j-1$, and $|y-a_i|=|x-a_i|-|y-x|$ if $i\ge j-1$. 
Hence, $f(y)=f(x)+|y-x|\{(j-1)+(n-j)\}=f(x)+|y-x|\{(2j-1)-n\}$. 
Now it is clear that as $x$ moves to the middle $a_i$, $f$ decrease, then increases as it moves further away.  
A: Suppose $a_1<a_2<\dots<a_n$. Then on each interval $\;(a_k,a_{k+1})$,
$$ f(x)=\sum_{i=1}^k(a_i-x)+\sum_{i=k+1}^n(x-a_i)=(n-2k)x+\sum_{i=1}^ka_i-\sum_{i=k+1}^n a_i $$
Thus, $f(x)$ is decreasing on $\;(a_k,a_{k+1})$  as long as $n-2k>0$, i.e. $k<\dfrac n2$, increasing as soon as $k>\dfrac n2$. 
We see there are two cases:


*

*If $n$ is odd; $n=2p+1$, there is a unique minimum, attained at the middle point  $a_{p+1}$, and its value is:
$$f(a_{n+1})= -a_1-\dots-a_n+a_{n+2}+\dots+a_{2p+1}.$$

*If $n$ is even: $n=2p$, the function attains its minimum on the middle interval $\;[a_p,a_{p+1}]$ and its value is:
$$-a_1-\dots-a_p+a_{p+1}+\dots+a_{2p}.$$

A: Your intuition is good, the answer is the median of $(a_i)_{1\leq i\leq n}$.
Let $f_1(x)=\sum_{i=2}^{n-1}\vert x-a_i\vert$. Then you have, for all $x$:
$$f(x)=\vert x-a_1\vert + f_1(x)+\vert x - a_n\vert$$
Considering this equation, you can show that $f_1$ et $f$ have the same minimum, noticing that:


*

*the minimum is not outside $[a_1,a_n]$

*$\forall x\in\lbrack a_1,a_n\rbrack$, $f(x)=f_1(x)+(a_n-a_1)$


Repeating this, you can "forget" extremal points at each step. At the end you only have one or two points left. Then you just have to consider the two cases: $n$ even and $n$ odd.
A: 
My guess is the minimum occurs at the middle point

The middle (median) interval.  There are two median points if $n$ is even and $f$ is constant and minimum on the interval between them.  If $n$ is odd the interval reduces to a point.
This was the starting point of Median Regression.  Wikipedia attributes the idea to Boskovic in the 1700's, which would make it one of the first examples of regression methods.
