1

Good day.

I have no idea how to solve the following question and will be grateful for any help. Suppose we are given $~n~$ real numbers $~y_1,...,y_n~$. Is there any simple way to minimize function $~f(y) = \sum_{k=1}^{n}|y_k-y|$ ?

Thanks in advance.

Igor
  • 2,153
  • 16
  • 19
  • In general there is no single minimizer $y$. For example, if $n = 2$ and $y_2 > y_1$, then $f(y) = y_2 - y_1$ (the global minimum) for all $y \in (y_1, y_2)$. You could take this as a motivation for considering the sum of squares of differences $(y_k - y)^2$. – Travis Willse Oct 17 '14 at 13:10
  • Unfortunately i need exactly such sum. May be there is some general way to obtain at least one (even not unique) solution? – Igor Oct 17 '14 at 13:15

2 Answers2

1

For simplicity, I will consider that $y_1<\cdots< y_n$. You can derive the function piecewise.

In each piece, the derivative is constant. At the left of $y_1$, it is $-n$. Between $y_1$ and $y_2$, it is $-n+2$, ... Between $y_{n-1}$ and $y_n$ it is $n-2$, and at the right of $y_n$ is $n$.

Then, you have two possibilities:

  1. If $n$ is even, the minimum is achieved in the segment $[y_{n/2},y_{1+(n/2)}]$, because in this segment, the derivative is $0$.
  2. If $n$ is odd, the minimum is achieved at a single point, namely $y_{(n+1)/2}$. Because at the left of this point the derivative is negative, and positive at the right (where it exists, of course).

As you can see, this minimum has a strong link with the median of the points $y_1,\ldots,y_n$.

ajotatxe
  • 65,084
1

Without loss of generality, suppose that $y_1\leq y_2\leq\cdots\leq y_n$. $$\sum_{k=1}^n|y_k-y|=\frac{1}{2}[\sum_{k=1}^n|y_{n+1-k}-y|+\sum_{k=1}^n|y-y_k|]\geq\frac{1}{2}\sum_{k=1}^n|y_{n+1-k}-y_k|$$ Equality holds only when $y\in[y_k,y_{n+1-k}]$ or $[y_{n+1-k},y_k]$ for arbitrary $k$.

If $n$ is even, the minimize attains when $y\in[y_{\frac{n}{2}},y_{\frac{n+1}{2}}]$.

If $n$ is odd, the minimize attains when $y=y_{\frac{n+1}{2}}$.

Alfred Chern
  • 2,658