# Best upper bound for the solution of a maximization problem

Let $$D \geq 2$$ and $$n \leq \displaystyle \frac{D}{2}.$$ Consider the following maximization problem:

$$\begin{cases} \displaystyle\arg \max_{x_1, \ldots, x_n} \sum_{i=1}^n x_i^2 \\ \text{s.t.}\\ \displaystyle \sum_{i=1}^n x_i = D \\ x_i \geq 2 ~\forall i \end{cases},$$

where $$x_i$$ are real numbers.

Suppose that $$x_1^*, \ldots, x_n^*$$ is a solution of the previous problem. Let

$$y^* = \max\{x_1^*, \ldots, x_n^*\}.$$

Of course, $$y^* \leq D.$$ Anyway, $$D$$ seems to be a "too large" upper bound. Is there a way to find a "lower" upper bound?

The objective is to maximise $$\Sigma x_i^2$$, and $$x_i \geq 2$$ with $$\Sigma x_i = D$$.

Since $$x_i\geq 2$$, let's start with the basic feasible solution $$x_i = 2$$. Now, the value of $$\Sigma x_i^2$$ would be $$2^2n=4n$$. This is not the optimal solution but just a basic feasible solution.

Now, to approach for optimal point, the $$x_i$$ values can only be increased but cannot be decreased because we have the constraints $$x_i \geq 2$$. Suppose we increase all the $$x_i$$ values with some $$\delta \;(>0)$$ such that the objective function $$\Sigma x_i^2$$ becomes maximum. $$\delta$$ cannot go to infinity because we have the constraint $$\Sigma x_i = D$$. So, if all the values of $$x_i$$ are increased by $$\delta$$ then we can have $$x_i = 2 + \delta$$, and the constraint would be $$n(2+\delta)=D$$, from which we can have $$\delta = \frac{D}{n}-2$$. And since all $$x_i$$ values have the same value, $$y^*$$ would be given by $$y^* = 2+\delta = 2+ \frac{D}{n} - 2 = \frac{D}{n}$$.

In the above step, we have increased all the $$x_i$$ values from $$2$$ to $$2+\delta$$. In other words, we have increased al the $$x_i$$ values by $$\delta$$. But if we want to have the upper limit of $$y^*$$, increasing one of the $$x_i$$ values by $$\delta^*$$ and keeping all the other $$x_i$$ values AT 2 could have one particular value of $$x_i$$ parameters to have the maximum value whilst the others have the minimum value. If we set $$x_1 = 2+\delta_2$$ and all the other $$x_i$$ values to be just $$2$$, then one of the $$x_i$$ values would have the maximum value whilst the others would have minimum values. And since $$y^*=\max{\{x_1, x_2, ..., x_n\}}$$, the upper bound of $$y^*$$ would be the $$x_i$$ value that has the maximum value and the others have the minimum value.

Let's say $$x_1$$ has the maximum value, i.e., $$x_i = 2+\delta_2$$, and $$x_2=x_3=...=x_n = 2$$.

Now, by putting these in the constraint $$\Sigma x_i = D$$, we can have

$$(x_1)+(x_2+x_3+...+x_n) = D$$ $$\Rightarrow (2+\delta_2)+(n-1)\times2 = D$$ $$\Rightarrow (2+\delta_2) = D-2(n-1) = D-2n+2$$

$$\Rightarrow \delta_2 = D-2n+2-2 = D-2n$$.

Any value of $$\delta_2$$ more than $$D-2n$$ would make at least one $$x_i$$ value less than 2, thereby violating at least one of the given constraints of the problem.

Therefore, a better upper bound of $$y^*$$ is $$D-2n+2$$.