Problem 50 - Page 2

hkito · #16 $Old$ May 9th, 2009, 08:56 PM

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

CaptainBlack · #17 $Old$ May 10th, 2009, 01:33 AM

Quote:

Originally Posted by hkito $View Post$

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 · #18 $Old$ July 28th, 2009, 12:11 PM

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|)+(|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 · #19 $Old$ 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.