Minimization of sum of squares

Question

I'm having trouble figuring out how to minimize the expression:

$$(k_1 + 2)^2 + (k_2 + 2)^2 + \cdots + (k_m + 2)^2$$

given that $k_1 + k_2 + \dots + k_m = 17$. Any help would be appreciated!

Answer 1

Show that if $k_1 \neq k_2$ you can decrease the sum by making both the average. Then argue that this means all the $k$s are equal.

Answer 2

Note that $\min \{ \sum_i (k_i+2)^2 | \sum_i k_i = 17 \}$ has the same solutions as $\min \{ \sum_i (k_i+2)^2 | \sum_i k_i = 17 , \sum_i (k_i+2)^2 \le 19^2\}$ and the latter has a compact feasible set so has a solution.

Lagrange gives $2 (k_i+2) + \lambda = 0$ hence all the $k_i$ are the same and so $k_i = {17 \over m}$.

Alternative: (Not really.)

Let $x_i=k_i+2$, then the problem is $\min\{ \sum_i x_i^2 | \sum_i x_i = 17-2m \}$, that is the nearest point to the origin in the plane $\sum_i x_i = 17-2m$ which is $x_i = {17 \over m} -2$, and so $k_i = { 17 \over m}$.

Another one: (A more complicated way of writing Ross' answer.)

Note that the problem is convex and furthermore, if $k$ satisfied the constraint so does $Pk$, where $P$ is a permutation matrix, and $f(k) = f(Pk)$, where $f$ is the cost. Since the problem is convex, we have $f({1 \over |\cal P|} \sum_{ P \in {\cal P}} Pk ) \le {1 \over |\cal P|} \sum_{ P \in {\cal P}} f(Pk) = f(k) $ and it is intuitively clear that ${1 \over |\cal P|} \sum_{ P \in {\cal P}} Pk = (\sum_i k_i) (1,1,...,1)^T$, so we can restrict the search to the set of vectors that all have the same component. The answer follows.

Answer 3

Hint By Cauchy-Schwarz

$$\left( k_1+2+k_2+2+...+k_m+2 \right)^2 \leq \left( (k_1 + 2)^2 + (k_2 + 2)^2 + ... + (k_m + 2)^2\right) \left(1+1+...+1 \right) $$

Equality occurs when $$\frac{k_1+2}{1}=\frac{k_2+2}{1}=...=\frac{k_m+2}{1}$$

Answer 4

The map $x \mapsto (x+2)^2$ has second derivative of 2 and hence is striclty convex.

$\mathbf k \succeq \frac{17}{m}\mathbf 1$ so with $f: \mathbf x \mapsto \big \Vert\mathbf x + 2\mathbf 1\big \Vert_2^2$ you have $f\big(\mathbf k\big) \geq f\big(\frac{17}{m}\mathbf 1\big)$ with equality iff $\mathbf k =\frac{17}{m}\mathbf 1$. An equivalent finish without using majorization is to observe the result follows by Jensen's Inequality by a nearly identical convexity argument.