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.

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
1  
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
add comment

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
2  
+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
1  
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
add comment

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
add comment

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
add comment

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.