Given $\sum_{i=1}^n x_i = 1,$ what values of $x_i$ minimize the sum $\sum_{i=1}^{n}x_i^2\ ?$
How do you find the optimal value for this function?
-
1I assume you mean the following: Given $\sum_{i=1}^n x_i = 1$, minimize $\sum_{i=1}^n x_i^2$. I further assume you want $x_i$ real. It's not too difficult to show that the latter sum is minimized by $x_i = 1/n$ for all $i$, in which case the sum is $1/n$. – 2011-09-07
3 Answers
You can use the method of Lagrange multipliers; but the problem is much more simple here.
You have an equation that defines a plane, and you want the vector on the plane that is closest to $\mathbf{0}$. The normal vector to the plane is $(1,1,\ldots,1)$, so you want to find the vector $(x_1,\ldots,x_n)$ in the plane such that $(x_1,\ldots,x_n)+t(1,1,\ldots,1) = (0,0,\ldots,0)$ for some $t$.
Hence we must have $x_1=\cdots=x_n$, and to lie on the plane you must have $nx_1=1$, so the answer is the vector $(\frac{1}{n},\frac{1}{n},\ldots,\frac{1}{n})$.
(This can also be seen by symmetry, since whatever the answer is, it should be invariant under swapping variables, since they all play symmetric roles).
-
0@Robert Israel: Yes, as your comment on one of the answers in the linked question says! :) – 2011-09-07
One way is to apply the Cauchy-Schwarz inequality to two $n$-dimensional vectors $\mathit{\boldsymbol a}=(x_1,x_2,\ldots,x_n)$ and $\mathit{\boldsymbol b}=(1,1,\ldots,1)$.
From $|\mathit{\boldsymbol a}\cdot\mathit{\boldsymbol b}|\le |\mathit{\boldsymbol a}||\mathit{\boldsymbol b}|$ it follows that $|x_1+x_2+\cdots+x_n|\le \sqrt{x_1^2+x_2^2+\cdots+x_n^2}\sqrt{1+1+\cdots+1}.$
Since the left hand side equals $|1|=1$, $\frac{1}{n}\le x_1^2+x_2^2+\cdots+x_n^2.$
The two sides are equal if and only if $\mathit{\boldsymbol a}$ and $\mathit{\boldsymbol b}$ are parallel, that is, $x_1=x_2=\cdots=x_n(=1/n)$.
-
0The LHS had a small typo (there should be no $\sqrt{\cdot}$ there). I fixed it for you :) – 2011-09-07
Let $S=\sum\limits_i x_i^2$. Define $z_i=x_i-h$ for $h=1/n$. One looks for the vector $(z_i)$ such that $\sum\limits_i z_i=0$ which minimizes $ S=\sum_i(z_i+h)^2=\sum_iz_i^2+2h\sum_iz_i+h^2\sum_i1=\sum_iz_i^2+2h\cdot0+h^2\cdot n=\sum_iz_i^2+h. $ Since $z_i^2\ge0$ for every $i$, the last expression of $S$ shows simultaneously that $S\ge h$ for every $(x_i)$ and that $S$ is minimal when $z_i=0$ for every $i$, that is, when $x_i=1/n$ for every $i$.