Maximize $\sum{a_i^2}$ given $\sum{a_i}=237$

Question

I recently got stuck with the following problem:

Consider 18 integer numbers in segment $[10; 20]$. Find the maximum possible value of $$ \sum_{i=1}^{18} {a_i^2} $$ given that $$\sum_{i=1}^{18} {a_i}=237$$

I don't really know how to approach this problem. The thing is, solving it like constraint optimization problem I got the solution $a_1=a_2=...=a_n=\frac{237}{18} \approx13.2$

But we need to solve it in integers. And just taking numbers around $13.2$ doesn't make sense to me. Any ideas?

Answer 1

The idea is to suppose all of the $a_i$ are fixed except for two of them, and see what happens if you add $1$ to one and subtract $1$ from the other. So say for instance $a_1 = x$, $a_2 = y$, and all the other $a_i$ are fixed. Then adding $1$ to $x$ and subtracting $1$ from $y$ gives the same sum, but what happens to the sum of squares? $$(x+1)^2 + (y-1)^2 - (x^2 + y^2)$$ is the amount by which the sum of squares increases or decreases. But this is $$2x + 1 - 2y + 1 = 2(x-y+1).$$ So if $x \ge y$, this means the sum of squares will increase if we add $1$ to $x$ and subtract $1$ from $y$. Repeated application of this logic means that the sum of squares is actually maximized when $x$ is as large as possible and $y$ is as small as possible. Then we repeat this logic for the other terms in the sum; it follows that the maximum is attained when we can make as many of the $a_i$ as large as possible. Since the $a_i$ are restricted to $[10; 20]$ we want the largest $m$ such that $20 m + 10(18 - m) \le 237$, or $m = 5$. This means $5$ of the $a_i$ are equal to $20$, $12$ of them are $10$, and the last one makes up the remainder, which has value $17$, and the sum of squares is $3489$.

---

A slightly different way to look at the second part of the solution is to note that since each of the $a_i$ must be at least $10$, we can create an auxiliary sequence $b_1, b_2, \ldots, b_{18}$ with $b_i = a_i - 10$, hence $b_i \in [0; 10]$ and the constraint on them is $$\sum_{i=1}^{18} b_i = 57.$$ Then the same reasoning as before gives five $b_i$ equal to $10$, and one $b_i$ equals $7$.

Answer 2

This looks like a job for Cauchy's inequality. By Cauchy, we have that $(a_1^2+a_2^2+a_3^2...+a_{17}^2+a_{18}^2)(1+1+1 ... + 1 +1) \ge (a_1(1) + a_2(1) +a_3(1)...a_{17}(1) + a_{18}(1))^2$.

Note that there are $18$ ones in $(1+1+1 ... + 1 +1)$ to pair up with $18$ $a$s.

So, this inequality simplifies as $18(a_1^2+a_2^2+a_3^2...+a_{17}^2+a_{18}^2) \ge (a_1 + a_2 +a_3...a_{17} + a_{18})^2$. We know that the sum on the left is $237$, thus we have $18(a_1^2+a_2^2+a_3^2...+a_{17}^2+a_{18}^2) \ge (237)^2$. Simplifying, we get $(a_1^2+a_2^2+a_3^2...+a_{17}^2+a_{18}^2) \ge 3120.5$. By Cauchy's inequality condition, we must have all $a$ be equal, so we get $18a_1^2 \ge 3120.5$, or $a_1 \le -13.6666$ or $a_1\ge 13.16666...$. However, that means that making all of the terms $13/-13$ actually gets you to the MINIMUM. However, since Cauchy's inequality has no upper bound, that means that the maximum of the squares is INFINITE. This is because you can take ridiculously small negative integers, and ridiculously big integers, and still have a sum of $237$. However, the sum of their squares will be HUGE.

Example, the sum of $-1000,-2000,-3000,-4000,-5000,-6000,-7000,-8000,-9000,-10000,-11000,-12000,-13000,-14000,-15000,-16000,-17000, 153237$

is $237$, but the sum of the squares of this set is $2.5266578169×10^{10}$.

Answer 3

An optimal solution cannot have $10 < a_i \leq a_j < 20$ for some $i$, $j$ because that contradicts optimality (you could increment $a_j$ and decrement $a_i$ and get a higher objective value). Therefore, there can be at most one element that is not $10$ or $20$.

There is therefore an optimal solution for which $a_1, \ldots, a_m$ take the value $10$, $a_{m+1},\ldots,a_{17}$ take the value $20$, and $a_{18} \in [10,20] \cap \mathbb{Z}$. From the equality constraint it follows that $a_{18} = 237 - 10m - 20(17-m) = 10m-103$. The only $m$ for which $10m-103 \in [10,20]$ is $m=12$, so the problem is solved.

If you had multiple $m$, you should evaluate the objective value ($100m + 400(17-m) + a_{18}^2 = 100m^2 - 2360m + 17409$) and pick the one for which the objective is the highest.

---

Other method This problem is also easy to solve with an integer programming solver after you formulate it appropriately. Let $x_{10}$ denote the number of times you pick $10$, etc, then the problem is:

\begin{align} \max_{x} \quad & \sum_{i=10}^{20} i^2 x_i \\ \text{s.t.} \quad & \sum_{i=10}^{20} i x_i = 237 \\ & \sum_{i=10}^{20} x_i = 18 \\ & x_i \in \mathbb{Z}_+ \end{align}

I have added the GAMS model below, which you can solve on the NEOS server. The optimal solution is $$a = (10,10,10,10,10,10,10,10,10,10,10,10,17,20,20,20,20,20)$$

with an objective value of 3489.

Set
   i 'idx'    / r10*r20 /;

Parameter
   a(i) / r10 10, r11 11, r12 12, r13 13, r14 14, r15 15, r16 16, r17 17, r18 18, r19 19, r20 20 /;

Integer   Variable x(i);
Variable z;

Equation objective, budget, eighteen_numbers;
objective.. z =e= sum(i, a(i)*a(i)*x(i));
budget.. sum(i, a(i)*x(i)) =e= 237;
eighteen_numbers.. sum(i, x(i)) =e= 18;

Model knapsack / all /;
solve knapsack max z using mip;