Course:MATH110/Archive/2010-2011/003/Notes/Optimization/Problem 9

Question

Say that you want to measure something, say the length of a table. Denote by $X$ the exact length of the table. Say now that you do a certain number of measures of the length of the table and get values

$x_{1},x_{2},x_{3},\ldots x_{N-1},x_{N}$

where $N$ is the number of measures you took. Now using all these measures, you want to construct an approximated value $x$ which should give you a solid idea of how much the real measure $X$ is. How to do so efficiently?

One very good idea would be to say that you want your value $x$ to be the one that has the smallest sum of the square of the differences to all your measures. What does that mean, it means you want to compute

$(x-x_{1})^{2}+(x-x_{2})^{2}+\ldots +(x-x_{N})^{2}$

and you'll say that your best guess for $X$ is the value $x$ that makes the above as small as possible. Why that? Well it makes sense to look at all the differences $x-x_{i}$ but since some might be positive and some negative, it makes sense to square them just to get them all positive and then to sum all that. Any number that makes the sum of the square differences small can be thought as being fairly in the middle and hence a really good guess for what all these measures are trying to get at.

Now the question is of course: great, how do I find that $x$ guy if I'm given all these measures $x_{1},\ldots x_{N}$?

Solution $\quad$

Before reading the solution, you should really try the problem for yourself. By should I mean that if you don't you will not gain any understanding, whatever you might believe, this is 100% guaranteed. So do yourself a favour, try the problem and look at the solution once you've gave it an authentic try. Solution $\quad$ Well, let's just use optimization! So we assume that we are given the values $x_{1},x_{2},\ldots x_{N}$ and we're looking for the value $x$ that will minimize the sum of the square of the differences, in other words, we're looking for the minimum value of the function: $f(x)=(x-x_{1})^{2}+(x-x_{2})^{2}+\ldots +(x-x_{N})^{2}$ To do this, we'll start by finding its critical points. So we need first to compute its derivative. $f'(x)=2(x-x_{1})+2(x-x_{2})+\ldots +2(x-x_{N})$ Then solve it for zero. $2(x-x_{1})+2(x-x_{2})+\ldots +2(x-x_{N})=0\quad \iff \quad 2Nx=2x_{1}+2x_{2}+\ldots +2x_{N}$ and so $x={\frac {x_{1}+x_{2}+\ldots +x_{N}}{N}}$ Which is the only critical point and clearly a minimum since the second derivative of the function is $f''(x)=2N>0$ which is always positive and hence concave up. Looking more closely at our answer, we actually see that $x={\frac {x_{1}+x_{2}+\ldots +x_{N}}{N}}$ is the average of the values $x_{1},x_{2},\ldots x_{N}$. So we've actually proved that the average of all the measures yields the value that minimizes the sum of the square of the difference of all the measures; a result that should have felt quite intuitive but for which we have a deeper understanding now.