Maxima/Minima of absolute function

Question

Given $a_i=\{a_1,\dots,a_n\}$ and function $$f(x)=\sum_{i=1}^n{|x-a_i|}^3$$ I need to find minimum value of $f(x)$. As far my understanding goes the derivative is given by: $$f'(x) = \sum_{i=1}^n\frac{3*{(x-a_i)}^3}{{|x-a_i|}^3}$$ After this I have no clue how to solve $f'(x)=0$. Any suggestions?

Answer 1

To get rid of the absolute values, one way is to compute the derivative separately on each interval $(a_1,a_2), \ldots, (a_{n-1},a_n)$. I'm assuming without loss of generality that $a_1<a_2<\cdots<a_n$. Within each of those intervals you know the sign of each term $x-a_i$, so you can replace each $|x-a_i|^3$ by either $(x-a_i)^3$ or $-(x-a_i)^3$.

The global minimum may be achieved at points with zero derivative within each of the intervals or at the interval endpoints $a_1, \ldots, a_n$. So you have to also check the function value at the latter points.

Answer 2

I have seen this problem on a programming competition and solved it as follows:

1. Sort $a_1\leq a_2 \leq ...\leq a_n$.

2. Consider your function on the following intervals: $(\infty, a_1], [a_1, a_2],...,[a_n,+\infty)$. On every such interval $f(x)$ is just a polynomial of degree at most $3$, because you can get rid of absolute values. E.g. on $[a_1,a_2]$ we have $|x-a_3|^3=(a_3-x)^3$.

3. For every interval minimize $f$ on it. This can be done by looking at the derivative etc.

Answer the minimum over all intervals.