# Homework Help: Minimum of Ʃ$^{n}_{i=1}$$\left|x_{i}-z\right|$

1. Nov 30, 2012

### no_alone

1. The problem statement, all variables and given/known data
Hello,
I have a question what is
What is the minimum of Ʃ$^{n}_{i=1}$$\left|x_{i}-z\right|$
x$_{i}$ are constants

2. Relevant equations
Not Much

3. The attempt at a solution
I split the sum to 3 sums
Ʃ$^{}_{x_{i}>z}$$(x_{i}-z)$ + Ʃ$^{}_{x_{i}<z}$$(-x_{i}+z)$+Ʃ$^{}_{x_{i}=z}$$(x_{i}-z)$
then I split the sums again:
Ʃ$^{}_{x_{i}>z}$$(x_{i})$+Ʃ$^{}_{x_{i}>z}$$(-z)$ + Ʃ$^{}_{x_{i}<z}$$(-x_{i})$ + Ʃ$^{}_{x_{i}<z}$$(z)$+Ʃ$^{}_{x_{i}=z}$$(x_{i}-z)$
This is Equall to
Ʃ$^{}_{x_{i}>z}$$(x_{i})$-$n^{}_{x_{i}>z}$$*z$ + Ʃ$^{}_{x_{i}<z}$$(-x_{i})$ + $n^{}_{x_{i}<z}$$*z$+Ʃ$^{}_{x_{i}=z}$$x_{i}-z$-$n^{}_{x_{i}=z}$$z$

Then I derivative by z and =0 to find maximum
I get:
-$n^{}_{x_{i}>z}$+ $n^{}_{x_{i}<z}$-$n^{}_{x_{i}=z}$=0

If x_{i}≠z for every i then
-$n^{}_{x_{i}>z}$+ $n^{}_{x_{i}<z}$=0

$n^{}_{x_{i}<z}$=$n^{}_{x_{i}>z}$

If there is i that x_{i}=z
$n^{}_{x_{i}<z}$ = $n^{}_{x_{i}>z}$+$n^{}_{x_{i}=z}$

What we get is that the minimus is when z is the median of x_{i}

But I have a problem, when I try for example to derivate:
$n^{}_{x_{i}<z}$$*z$
n is dependent on z soo... I cannot do it! I dont know how to derivate it...

Thank's for the help

2. Nov 30, 2012

### MathematicalPhysicist

This is a nonnegative function, so you want to find for which value of z it gets the minimal value.

As always we have the arithmetic-geometrical means inequality:

$$\sum_{i=1}^{n}\frac{|z-x_i|}{n} \geq \prod_{i=1}^{n} (|z-x_i|)^{\frac{1}{n}}$$

So the minimum value of this function is achieved when the above LHS equals the RHS, and this happens when:

$$|z-x_i|=|z-x_j|$$ for all $$i\neq j$$.

3. Nov 30, 2012

### Ray Vickson

Setting the derivative to zero is a mistake: the function $f(z) =\sum_i |z - x_i|$ is piecewise differentiable only, and may not have a derivative at all at the minimizing point. For example, draw the graph of $f(z) = |z-1|+|z-2|+|z-3|.$

You are correct that the minimum is at the median, but there is an easier way to get this: imagine that the x_i are sorted in increasing order, so $x_1 < x_2 < \cdots < x_n$; I'll let you worry about the modifications needed in the argument if some of the x_i are equal. So, to the left of x_1 the slope of the graph of f(z) is -n, because
$$f(z) = \sum_{i=1}^n x_i - nz$$ when z < x_1 . As z increases through x_1 the slope increases by 2, to become -n+2. Every time z passes through the next x_i the slope increases by 2.

4. Nov 30, 2012

### Michael Redei

If you're looking for a minimum of the form $\sum|x|$, you can look at the function $\sum x^2$ instead, since |x| and x² are extreme at the same places.

If you do that for this case, you'll be led to the arithmetic mean of the xi and not their median.

5. Nov 30, 2012

### Ray Vickson

In this problem the minimum is at the median, not at the mean. The two forms |x-z| and (x-z)^2 give different things when there is more than one such term.