Math Help Forum - View Single Post

luobo · #19 August 7th, 2009, 05:45 PM

Problem: Known $-\infty<x_1<x_2<...<x_{n-1}<x_n<+\infty$ , minimize $f(x)=\sum_{i=1}^{n} |x-x_i|$ .

Two observations of $f(x)$ are:
(1) It is uni-modal (for odd $n$ , 1 minimum point) or almost so (for even $n$ , 2 minimum points of equal functional value).
(2) The minimum value can be reached at the nodes $x_i, 1\leq i\leq n$ .

With these observations, suppose minimum is reached at $x_k$ . Then
$f(x_k)=\sum_{i=1}^{n} |x_k-x_i|=\sum_{i=1}^{k-1} (x_k-x_i)+\sum_{i=k+1}^{n}(x_i-x_k)$ $=(2k-n-1)x_k+\sum_{i=k+1}^{n} x_i-\sum_{i=1}^{k-1} x_i$

Similarly,
$f(x_{k-1})=(2k-n-3)x_{k-1}+\sum_{i=k}^{n} x_i-\sum_{i=1}^{k-2} x_i$
$f(x_{k+1})=(2k-n+1)x_{k+1}+\sum_{i=k+2}^{n} x_i-\sum_{i=1}^{k} x_i$

$f(x_k)-f(x_{k-1})=(2k-n-2)(x_k-x_{k-1})\leq 0=>2k\leq n+2$

$f(x_{k+1})-f(x_k)=(2k-n)(x_{k+1}-x_k)\geq 0=>2k\geq n$

Therefore, $\frac{n}{2}\leq k \leq \frac{n}{2}+1$

For the present example, $n=16$ , so $k=8$ or 9.