2
$\begingroup$

I want to maximize $$\sum_{i,j \in [n], i \ne j} x_i \times x_j$$ where $\forall i ~~$ $0\le x_i \le 1$ and $x_1 + x_2 + x_3 + \ldots +x_n = 1$

I want to prove that the sum will be maximized when $\forall i ~~$ $x_i = \frac{1}{n}$. I don't know whether this statement is true or not.

Note:- It would be more helpful if you can prove that using shifting of weights from one $x_i$ and $x_j$. Even the proof is not following that method it is fine.

$\endgroup$
2
$\begingroup$

Your summation is $x_1(\sum_{j\ne1}x_j)+x_2(\sum_{j\ne2}x_j)+...+x_n(\sum_{j\ne n}x_j)$ which is $x_1(1-x_1)+...+x_n(1-x_n)=(x_1+...+x_n)-(x_1^2+...+x^2_n)=1-(x_1^2+...+x^2_n)$. To maximize this, we need to minimize $\sum_{i\in[n]}x_i^2$.

We know $\sum_{i=1}^nx_i^2\ge \frac{(\sum_{i=1}^nx_i)^2}n=1/n$.

And indeed this minimum is observed when $ x_1=x_2=...=x_n=1/n$. The maximum value is $1-1/n$.

$\endgroup$
1
$\begingroup$

If you take the derivative wrt $x_i$ you get, for each $i$

$$ \sum_{j=1}^n x_j-x_i-\lambda=0\implies x_i=1-\lambda$$

where $\lambda$ is the Lagrange multiplier. This means that all the $x_i$ need to take the same value. Adding the $n$ FOC's results in

$$ 1=n(1-\lambda)\implies \lambda=\frac{n-1}{n},$$

and, therefore, $$ x_i=\frac{1}{n}$$

$\endgroup$

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.