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?


1 Answer 1


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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .