Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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.
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$$
You can prove this by induction. Start with this lemma. For $a, b, c \geq 0$ we have:
$$a^2 + (a + b + c)^2 \geq (a + b)^2 + (a + c)^2$$
The proof just involves expanding out all terms and noticing that there is an extra $bc$ term on the LHS.
Let $m = \frac{k}{n}$. Let $S = \sum_{i = 1}^n x_i^2$. Let $M = nm^2$. We want to show that $S \geq M$.
Then we can proceed by induction on the number of terms $x_i$ which are not equal to $m$. In the base case, all terms are equal to $m$, and so $S = M$, and we're done.
In the inductive case, then WLOG assume that the terms $x_i$ are ordered in increasing order. And so $x_n > m$ and therefore $x_1 < m$. Let $a = x_n - m$ and let $b = m - x_1$. Then:
$$x_n = x_1 + a + b$$
Now let $x_1' = x_1 + a$ and let $x_n' = x_1 + b = m$. Then by our lemma, $x_1^2 + x_n^2 \geq x_1'^2 + x_n'^2$. So letting $S' = x_1'^2 + \sum_{i = 2}^{n - 1} x_i^2 + x_n'^2$ we have that $S \geq S'$. Also, clearly replacing $x_1$ and $x_n$ with $x_1'$ and $x_n'$ respectively preserves the total sum $k$. And since $x_n' = m$, then the number of terms that are not equal to $m$ has decreased after we make the replacement. So we can apply the inductive hypothesis yielding $S' \geq M$. Putting it all together:
$$S \geq S' \geq M$$
And that completes the proof.
