Finding the Minimum Value of a Summation with a Constant Term

[Dethrone]

Given $a_1,...,a_n$, find the minimum value of $\sum_{i}^{n}(x-a_i)^2$

No idea how to do it. I was thinking maybe when $x-a_i=0$, but I think $x$ is constant so it won't work...unless the series $a_n$ is constant too...Tiny hint please :D?

 

[MarkFL]

Okay, a tiny hint:

Begin by expanding the summand and exploiting the linearity of the summation operator.

 

[Dethrone]

Umm...(Wondering)

Expanding the summand:
$$\sum_{i}^{n}(x-a_i)^2=(x-a_1)^2+(x-a_2)^2+(x-a_3)^2+...+(x-a_n)^2$$

Not sure how to exploit it...just a guess:
$$=nx^2-2x(a_1+a_2+...+a_n)+(a_1^2+a_2^2+...+a_n^2)$$

 

[MarkFL]

You are moving in the right direction, although you have an error (that you have since fixed). But, what I meant is to write:

\(\displaystyle f(x)=\sum_{i=1}^{n}\left[\left(x-a_1\right)^2\right]\)

Now, expand the summand:

\(\displaystyle f(x)=\sum_{i=1}^{n}\left[x^2-2a_ix+a_i^2\right]\)

Exploit the linearity of the summation operator:

\(\displaystyle f(x)=\sum_{i=1}^{n}\left[x^2\right]+\sum_{i=1}^{n}\left[-2a_ix\right]+\sum_{i=1}^{n}\left[a_i^2\right]\)

Factor out those factors not dependent on the index of summation, to get a quadratic in $x$:

\(\displaystyle f(x)=x^2\sum_{i=1}^{n}\left[1\right]-2\sum_{i=1}^{n}\left[a_i\right]x+\sum_{i=1}^{n}\left[a_i^2\right]\)

\(\displaystyle f(x)=nx^2-2\sum_{i=1}^{n}\left[a_i\right]x+\sum_{i=1}^{n}\left[a_i^2\right]\)

Now, minimize...

Note: every summand is enclosed by square brackets, but they do not display properly for some reason. :D

 

[Dethrone]

Oh! I was going to write something similar to that, but I thought it was being a bit fancy for something that could be potentially wrong. (Dull)

$$\displaystyle f(x)=nx^2-2\sum_{i=1}^{n}\left[a_i\right]x+\sum_{i=1}^{n}\left[a_i^2\right]$$
$$f'(x)=2nx-2\sum_{i=1}^{n}\left[a_i\right]$$
Setting equal to zero:
$$x=\frac{\sum_{i=1}^{n}\left[a_i\right]}{n}$$

Is that right?

 

[MarkFL]

Yes, that is your critical value. How do you know this is at the minimum without using calculus?

 

[Dethrone]

I like that question! :D

Can I simply say that because there is only one critical number and the function tends to infinity as you approach its boundaries, then the extrenum must be a minimum? The function being a positive quadratic should be just enough, actually.

 

[magneto1]

The function you are minimizing is of the form $f(x) = nx^2 - 2Ax + B$. Since $n > 0$, if we find $x$ that min $f(x)$, it will also min $x^2 - \frac{2A}n x + \frac Bn$. We can then just complete the square:

$x^2 - \frac{2A}n x + \frac{A^2}{n^2} - \frac{A^2}{n^2} + \frac Bn = \left( x - \frac An \right)^2 - \frac{A^2}{n^2} + \frac Bn$.

With $A,B,n$ fixed, the smallest value can be attain when that square is $0$,
or $x = \frac{A}n$. In the case of this problem, it is $\frac 1n \sum_i a_i$, which we note is the average of the $a_i$'s.

 

[MarkFL]

...The function being a positive quadratic should be just enough, actually.

That's what I was hinting at, you have an upward opening parabola, so the critical value must be at the minimum.

Now, the question asks you to find the minimal value, so what do you get?

 

[Dethrone]

Hi Mark! (Wave)

So plugging $x$ in, we get:

$$\sum_{i=1}^{n}\left(\frac{\sum_{i=1}^{n}\left[a_i\right]}{n}-a_i\right)^2$$

Not sure if it is wise to simplify further. Looking back at magneto's method of completing the square, I see $- \frac{A^2}{n^2} + \frac Bn$, which also should be the minimum value.
$$- \frac{A^2}{n^2} + \frac Bn=-\frac{\left(\sum_{i=1}^{n}[a_i]\right)^2}{n^2}+\frac{\sum_{i=1}^{n}[a_i^2]}{n}$$

Are these statements equivalent?