Problem 50

**hkito** · May 9th 2009, 06:56 PM

The minimum is attained at the mean $\dfrac{\sum_{i=1}^{16} 2^i}{16}= \dfrac{2^{16}-1}{16}$

**CaptainBlack** · May 9th 2009, 11:33 PM

Originally Posted by hkito

The minimum is attained at the mean $\dfrac{\sum_{i=1}^{16} 2^i}{16}= \dfrac{2^{16}-1}{16}$

If you tell us why you think the minimum is attained there and what that minimum is we could explain where you went wrong.

CB

**Krahl** · July 28th 2009, 10:11 AM

This is how i did it...

let S= $|x-2|+|x-2^2|+...+|x-2^8|+|x-2^9|+....+|x-2^{15}|+|x-2^{16}|$

and S= $|x-2^{16}|+....+|x-2^9|+|x-2^8|+.......+|x-2|$

so whatever value minimises S would minimise

2S= $(|x-2|+|x-2^{16}|)+(|x-2^2|+|x-2^{15}|)$
$+......+(|x-2^8|+|x-2^9|)+<br /> (|x-2^9|+|x-2^8|)+......+(|x-2^{16}|+|x-2|)$

So if we look at all the values of x which minimises each term then the intersection of the values of x will minimise 2S and S.

looking at the graph of each term as chisigma did we see that all values between the minimum of each of the two terms are minimising values for both terms. since they are linear functions they intersect in the middle.

so the valuse minimising $(|x-2|+|x-2^{16}|)$ are $2 \leq x \leq 2^{16}$ and so on.

the intersection of $2 \leq x \leq 2^{16},2^4 \leq x \leq 2^{15},...,2^8 \leq x \leq 2^9,...,2 \leq x \leq 2^{16}$

is $2^8 \leq x \leq 2^9$ so these values would all minimise S.

**luobo** · August 7th 2009, 03: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.

Thread: Problem 50

LinkBack

Thread Tools

Display

Search Tags