1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Travis Willse Oct 17 '14 at 13:10
  • $\begingroup$ Unfortunately i need exactly such sum. May be there is some general way to obtain at least one (even not unique) solution? $\endgroup$ – Igor Oct 17 '14 at 13:15
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.