Take the 2-minute tour ×

Given $$\sum_{i=1}^n x_i = 1,$$ what values of $x_i$ minimize the sum $$\sum_{i=1}^{n}x_i^2\ ?$$

share|improve this question
I 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$. –  Craig Sep 7 '11 at 17:06

3 Answers 3

up vote 7 down vote accepted

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).

share|improve this answer
+1. A side comment on your parenthetic remark: It's not always true in the presence of symmetry that the optimal solution has all variables equal. See, for instance, When does symmetry in an optimization problem imply that all variables are equal at optimality? –  Mike Spivey Sep 7 '11 at 17:25
Of course, but in this example the objective is convex, in fact strictly convex. So the minimum is unique, and therefore must be invariant under the symmetry. –  Robert Israel Sep 7 '11 at 18:14
@Robert Israel: Yes, as your comment on one of the answers in the linked question says! :) –  Mike Spivey Sep 7 '11 at 19:02

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)$.

share|improve this answer
The LHS had a small typo (there should be no $\sqrt{\cdot}$ there). I fixed it for you :) –  Srivatsan Sep 7 '11 at 19:26
Thanks for the fix. –  pharmine Sep 7 '11 at 19:43

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$.

share|improve this answer

Your Answer


