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 $n$ positive values. Their sum is $k$. $$ x_1 + x_2 + \cdots + x_n = k $$ The sum of their squares is defined as: $$ x_1^2 + x_2^2 + \cdots + x_n^2 $$

I think that the sum of squares is minimum when $x_1 = x_2 = \cdots = x_n$. But I can't figure out how to prove it. Can anybody help me on this? Thanks.

share|improve this question
    
The standard method for problems of this overall shape is Lagrange multipliers, though that may be overkill in this simple case. –  Henning Makholm Sep 24 '11 at 14:37

7 Answers 7

HINT: By Cauchy-Schwarz we know

$$\left(\sum x_i y_i\right)^2 \leq \left(\sum x_i^2\right) \left(\sum y_i^2\right)$$

Take $y_i = 1$ for all $i$ to get a lower bound on $\sum x_i^2$. Then show that $x_i = \frac{k}{n}$ achieves this bound.

share|improve this answer
    
Thijs, your answer also works. Thanks. –  Jingguo Yao Sep 24 '11 at 15:10
3  
(+1) Nice and simple. –  cardinal Sep 24 '11 at 16:58

You can use Lagrange multipliers.

We want to minimize $\sum_{i=1}^{n} x_{i}^{2}$ subject to the constraint $\sum_{i=1}^{n} x_{i} = k$.

Set $J= \sum x_{i}^{2} + \lambda\sum_{i=1}^{n} x_{i}$. Then $\frac{\partial J}{\partial x_i}=0$ implies that $x_{i} = -\lambda/2$. Substituting this back into the constraint give $\lambda = -2k/n$. Thus $x_{i} = k/n$, as you thought.

share|improve this answer
    
Quinn, Thanks for your help. –  Jingguo Yao Sep 24 '11 at 14:46

Let $c = k/n$. Then, for all $(x_1,\ldots,x_n)$ such that $\sum_i x_i = k$, $$ \newcommand{\s}{\sum_{i=1}^n} \s x_i^2 = \s (c + x_i - c)^2 = c^2 n + \s (x_i - c)^2 \>, $$ since $2 \s c(x_i-c) = 0$. The right-hand side is obviously minimized by taking $x_i = c$ for all $i$ and so the result follows.

share|improve this answer

I think this reeks of AM-QM inequality. The $x_i$ have a fixed arithmatic mean of $\frac{k}{n}$, while the quadratic mean: $$ \sqrt{\frac{x_1^2 + \cdots + x_n^2}{n}} $$ is bounded below by that same number, which means that the sum of squares is bounded below by $\frac{k^2}{n}$, attained exactly when the $x_i$ are all equal.

share|improve this answer
3  
+1. For those (like me) who hadn't heard the term "quadratic mean" before; it is also known as the root mean square. –  Mike Spivey Sep 24 '11 at 20:12
    
In fact, I think this is my favorite of the answers. Since $x^2_{rms}$ is $n$ times the sum of squares, and $\bar{x}$ is fixed, it's clear from the relationship $x^2_{rms} = \bar{x}^2 + \sigma_x^2$ that $x^2_{rms}$ is minimized when $\sigma_x^2 = 0$; i.e., all variables are equal. –  Mike Spivey Sep 24 '11 at 20:27
    
Mike. Your explanation is nice. –  Jingguo Yao Sep 28 '11 at 15:39

If you haven't had Lagrange multipliers yet, here is the idea behind them.

If $\{x_i\}_{i=1}^n$ is a critical point, then for every vector $\{u_i\}_{i=1}^n$ so that $$ \frac{\mathrm{d}}{\mathrm{d}t}\sum_{i=1}^n(x_i+tu_i)=0\tag{1} $$ at $t=0$, we also have $$ \frac{\mathrm{d}}{\mathrm{d}t}\sum_{i=1}^n(x_i+tu_i)^2=0\tag{2} $$ at $t=0$.

Evaluating $(1)$ and $(2)$, this says that for every $\{u_i\}_{i=1}^n$ so that $$ \sum_{i=1}^nu_i=0\tag{3} $$ we also have $$ \sum_{i=1}^nx_iu_i=0\tag{4} $$ This means that $x$ is perpendicular to the space of all vectors that are perpendicular to $v$ where $v_i=1$. This means that $x$ is in the subspace spanned by $v$. Thus, the $x_i$ are all the same, and therefore, $x_i=k/n$.

share|improve this answer

More generally, if the objective function is strictly convex (objective is quadratic, check), the feasible region is convex (constraint is linear, check), and the problem is symmetric (i.e., the variables can be interchanged without changing the problem, check), then the global minimum has all the variables equal to each other. (See for, example Boyd and Vandenberghe, Convex Optimization, Exercise 4.4.). That immediately gives $x_i = \frac{k}{n}$ as well.

share|improve this answer

@Quinn Culver

Quinn Culver's answer is not enough.

It's not enough to say that $x_i=k/n$ is the local optima. Based on the Second Order Sufficiency Conditions, we need to prove $y^T\nabla_{xx}J y>0$ for all $y\ne0$ with $\nabla h(x)^Ty=0$. After some computation, we find $\nabla_{xx}J=2I$, where $I$ is the identity matrix and the vector $y$ satisfies $\nabla h(x)^Ty=0$ is $y^T1=0, \ y\ne 0$. In the end, we find $y^T\nabla_{xx}J y=2y^Ty >0$. Therefore, we prove that $x_i=k/n$ is the local optima. Furthermore, because $x_i=k/n$ is the unique solution, therefore, it is the global optima.

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.