Maximize $\sum\limits_{k =1}^n x_k (1 - x_k)^2$

Question

Given problem for maximizing \begin{align} &\sum_{k =1}^n x_k (1 - x_k)^2\rightarrow \max\\ &\sum_{k =1}^n x_k = 1,\\ &x_k \ge 0, \; \forall k \in 1:n. \end{align}

My attempt: first of all i tried AM-GM, or we can just say, that $x_k (1 - x_k)^2 \le x_kx_k^2 =x_k^3$, but now we got just sum of cubes. Can we say, that $\sum\limits_{k =1}^n x_k^3 \le \sum\limits_{k =1}^n x_k,$ because $x_i \le 1$ and get our maximum - 1? It looks very easy, but i suppose i'm wrong

Answer 1

For $x_1=x_2=...=x_n=\frac{1}{n}$ we get a value $\frac{(n-1)^2}{n^2}.$

We'll prove that it's a maximal value.

Indeed, \begin{align} \frac{(n-1)^2}{n^2}-\sum_{k=1}^nx_k(1-x_k)^2&=\sum_{k=1}^n\left(\frac{(n-1)^2}{n^3}-x_k(1-x_k)^2\right)\\ &=\frac{1}{n^3}\sum_{k=1}^n(1-nx_k)(n^2x_k^2-n(2n-1)x_k+(n-1)^2) \end{align} \begin{align} &=\frac{1}{n^3}\sum_{k=1}^n\left((1-nx_k)(n^2x_k^2-n(2n-1)x_k+(n-1)^2)-(1-nx_k)(n^2-4n+3)\right)\\ &=\frac{1}{n^3}\sum_{k=1}^n(1-nx_k)^2(2n-2-nx_k)\geq0\text{ for any } n\geq2. \end{align} For $n=1$ we have $x_1=1$ and $$x_1(1-x_1)^2=0=\frac{(n-1)^2}{n^2},$$ which says that $\frac{(n-1)^2}{n^2}$ is the answer.

Answer 2

We can use the method of Lagrange multiplers.

You are trying to maximize $$f = \sum_{k =1}^n x_k (1 - x_k)^2$$

subject to $$\sum_{k =1}^n x_k = 1$$

You have that $$f_{x_k} = \lambda g_{x_k} \to 3x_k^2 - 4x_k + 1 = \lambda$$ is valid for all $x_k$. We can solve for $x_k$ to get that $$x_k = \frac{2 \pm \sqrt{1+3\lambda}}{3}$$

Since $x_k$ must be positive, we have that $$x_k = \frac{2 + \sqrt{1+3\lambda}}{3}$$

This means that all $x_k$ are the same. Specifically, according to the constraint, $$x_k = \frac{1}{n}$$

Using this, I get that the max is $$\sum_{k=1}^n \frac{1}{n}\left(1-\frac{1}{n}\right)^2 = \left(1-\frac{1}{n}\right)^2$$

Answer 3

We start with $n+1$ variables, $x_1,x_2,.....,x_n,x_{n+1}$.

Now, $x_{n+1}=1-(x_1+....+x_n)$.

So, write the sum $$f(X)=\sum_{k=0}^{n+1} x_k(1-x_k)^2$$ as follows.

$$f(X)=\sum_{k=1}^{n} x_k(1-x_k)^2 +(\sum_{k=0}^{n} x_k)^2-(\sum_{k=0}^{n} x_k)^3$$.

$f(X)$ is extremum when $\vec{\nabla}f =0$.

From this we get $n$ non-linear equation of variables $x_k$ written below.

$$3{x_k}^2-4x_k+1=3(\sum_{k=0}^{n} x_k)^3-2(\sum_{k=0}^{n} x_k)^2$$

So, the right hand side is same for all $x_k, k=1,2,....,n$. Say this $c$. It's easy to see $\frac{1}{3} \leq c\leq 1$

$$3(\sum_{k=0}^{n} x_k)^3-2(\sum_{k=0}^{n} x_k)^2=c$$....(1)

So, the equations are $3{x_k}^2-4x_k+1-c=0$ which give the solutions like $x_k=\frac{2±\sqrt{1+3c}}{3}$.

Now from (1),

$S_n=\sum_{k=1}^{n} x_k=\frac{2n}{3}+m(\frac{\sqrt{1+3c}}{3})$,...(2) for some $-n \leq m \leq n$, such that $n-m$ is even.

As, $0 \leq S_n \leq 1$ we get

$2n+m\sqrt{1+3c} \leq 3$. ....(3)

As $c<1, \sqrt{1+3c}<2$, $m$ must be either $-n$ or $-(n-1)$ to satisfy (3). But, $n-(-(n-1)=2n-1$ isn't even. So, $m=-n$.

That means all $x_k=\frac{2-\sqrt{1+3c}}{3}$ , equal.

This means $f(X)$ would be maximum if $x_1=x_2=....=x_n$. But there is an additional information hidden in. That is the last $x_{n+1}$ also have to be equal with them.

$f(x_1,x_2,...,x_n)=f(x_2,x_3,...,x_{n+1})$

as the function is symmetric. So, if we had replaced $x_1$ instead of $x_{n+1}$ that still would require $x_k$ to be equal for $k=2,3,....,n+1$.

So, $x_1=x_2=x_3=.....=x_{n+1} \rightarrow x_k=\frac{1}{n+1}$

Hence, the summation $$\sum_{k=1}^{n+1} x_k(1-x_k)^2$$ along with the constraint has maximum value when $x_k=\frac{1}{n+1}$ and the maximum value is $(1-\frac{1}{n+1})^2$.