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$$
Find $y$ to minimize $\sum (x_i - y)^2$
1
$\begingroup$
optimization
-
1The average of $x_i$ is the best you can do. – 2012-03-07
-
0@Uwat What is $x_i$? What are the sum indices? – 2012-03-07
-
0@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 – 2012-03-07
-
0Thomas 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}.$ – 2012-03-07
3 Answers
3
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$.
-
0Thanks 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... – 2012-03-08
-
0@Uwat: If I recall correctly, it is the _median_ which minimizes $\sum |x_i - y|$, and need not be the same as the mean. – 2012-03-08
-
0I 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 – 2012-03-08
1
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.
0
Simply take the first-order condition of the problem if there are no restrictions on $y$. This is a simply concave problem.