# How to prove the sum of squares is minimum?

Given $n$ nonnegative 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.

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.

• Thijs, your answer also works. Thanks. – Jingguo Yao Sep 24 '11 at 15:10
• This also can be used to prove: If $\sum_{i=1}^{n}x_i=k\text{ }(x_i \le 0), \sum_{i=1}^{n}y_i=l \text{ }(y_i \le 0)$, $\sum_{i=1}^{n}x_i\cdot y_i$ minimizes when $x_1 = x_2 = ... = x_n$ and $y_1 = y_2 = ... = y_n$. – Jingguo Yao Aug 28 '16 at 5:49

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.

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.

• +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

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.

• Quinn, Thanks for your help. – Jingguo Yao Sep 24 '11 at 14:46

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

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.

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

For the sake of completion, here's a hint to complete squares:

$$\sum \left(x_i-\frac{k}n\right)^2\ge0 \iff \sum x_i^2\ge\frac{k^2}n$$