Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a finite set of numbers $X$. I want to minimize the following expression by finding the appropriate value for y: $$\sum\limits_{i=1}^n (x_i - y)^2$$

share|improve this question
1  
The average of $x_i$ is the best you can do. –  Thomas Andrews Mar 7 '12 at 22:04
    
@Uwat What is $x_i$? What are the sum indices? –  Pedro Tamaroff Mar 7 '12 at 22:05
    
@PeterT.off x_i is an element of X, the sum goes from i=1 to i=n where n is the number of elements in X thanks to Brett and Arturo for fixing my format –  Uwat Mar 7 '12 at 22:10
    
Thomas has given you the correct answer. You sum can be rewritten as $\sum_{i=1}^{n} x_{i}^{2} -2y\sum_{i=1}^{n}x_i + ny^{2}.$ –  Geoff Robinson Mar 7 '12 at 22:12

3 Answers 3

up vote 3 down vote accepted

It is a quadratic in $y$:

$$ny^2 - 2Sy + P$$

which is minimized when $y = \frac{S}{n}$ (you can see that by completing the square).

Here $S = \sum x_i$ (and $P = \sum x_i^2$) and thus $y$ needs to be the mean of $x_i$.

share|improve this answer
    
Thanks for your answer. I find this very surprising that the mean of X minimizes both the sum of (xi - y)^2 and the sum of abs(xi-y)... I guess I shouldn't trust my intuition anymore... –  Uwat Mar 8 '12 at 3:19
    
@Uwat: If I recall correctly, it is the median which minimizes $\sum |x_i - y|$, and need not be the same as the mean. –  Aryabhata Mar 8 '12 at 3:24
    
I made up an example, and the median is indeed better than the mean for that case. I really need to check my assumptions ;) thanks again –  Uwat Mar 8 '12 at 3:33

Simply take the first-order condition of the problem if there are no restrictions on $y$. This is a simply concave problem.

share|improve this answer

This is one of those problems where you just turn the crank and out pops the answer. The basic optimization technique of "set the derivative equal to zero and solve" to find critical points works in its simplest form without issue here.

And as the others have mentioned, the special form of being quadratic allows you to apply the specialized techniques you've learned for dealing with quadratic equations.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.