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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.