Minimizing $\sum\limits_{i=1}^n (x_i^3 - x_i^2)$ subject to $\sum\limits_{i=1}^n x_i = S$

For $n=1$, clearly $x_1=S$; for $n=2$, we can also show that $x_1=x_2=S/2$. So we'll take $n\ge 3$ from now on. The theory of Lagrange multipliers says that the minima of your function (for fixed $n$ and $S$) must be found among the saddle points of $$ G(\mathbf{x}, \lambda) = F(\mathbf{x}) + \lambda \left(\sum_i x_i - S\right), $$ where $F(\mathbf{x})=\sum_i (x_i^3 - x_i^2)$ is what you want to minimize. Since $$ \frac{\partial G}{\partial x_i} = \frac{\partial F}{\partial x_i} + \lambda = 3x_i^2 - 2x_i + \lambda = 0, $$ we have $$ x_i = \frac{2 \pm \sqrt{4 - 12\lambda}}{6} = \frac{1\pm\sqrt{1-3\lambda}}{3} $$ for each $i$ (and so $\lambda \le 1/3$). Moreover, we need $$ \frac{\partial G}{\partial \lambda} = \sum_i x_i - S = 0. $$ If $0 \le k \le n$ of the $x_i$ are equal to $(1+\sqrt{1-3\lambda})/3$, and the remaining $n-k$ are equal to $(1-\sqrt{1-3\lambda})/3$, then this latter constraint gives $$ k(1 + \sqrt{1-3\lambda}) + (n-k)(1-\sqrt{1-3\lambda})=n + (2k-n)\sqrt{1-3\lambda}=3S, $$ or $$ \lambda = \frac{1}{3}\left(1 - \left(\frac{3S-n}{2k-n}\right)^2\right). $$ After some algebra, then, each $x_i$ satisfies $$ x_i^3 - x_i^2 = x_i^2(1-x_i) = \frac{1}{27}\left(-2 \pm (2+3\lambda)\sqrt{1-3\lambda}\right), $$ depending on the chosen sign for that $i$; and if $k$ are positive and the rest are negative, we finally arrive at $$ \begin{eqnarray} F(\mathbf{x}) &=& -\frac{2n}{27} + \frac{2k-n}{27}(2 + 3\lambda)\sqrt{1-3\lambda} \\ &=& -\frac{2n}{27}+\frac{1}{27}\left(3 - \left(\frac{3S-n}{2k-n}\right)^2\right)(3S-n)\cdot\text{sgn}(2k-n). \end{eqnarray} $$ This needs to be minimized over $k \in \{0,1,\ldots,n\} \setminus \{n/2\}$. We'll always choose $k>n/2$ or $k<n/2$ depending on the sign of the resulting contribution to $F$, so in fact we can minimize $$ F(\mathbf{x}) = -\frac{2n}{27} - \frac{1}{27}\cdot\left|3 - \left(\frac{3S-n}{2k-n}\right)^2\right|\cdot\left|3S-n\right| $$ over $0 \le k < n/2$. So we want the maximum of the term $$ \left|3 - \left(\frac{3S-n}{2k-n}\right)^2\right|, $$ which can occur when $k=0$, or when $|2k-n|=1$ (or $k=(n\pm 1)/2$, if $n$ is odd), or when $|2k-n|=2$ (or $k=n/2 \pm 1$, if $n$ is even). Putting everything together, the structure of the minimizer is just going to depend on $\alpha \equiv |3S-n|$, and on $n$. We have $$ F_{\text{min}} = -\frac{2n}{27} - \frac{\alpha}{27} \max({ |3-\alpha^2 / n^2|, |3- \alpha^2 / P^2 |}), $$ where $P=1$ if $n$ is odd and $P=2$ if $n$ is even. If the first term is the maximum, then all $x_i$ are equal. If the second term is the maximum, then the $x_i$ assume two different values, with about half equal to each. When is $|3-\alpha^2/n^2| \ge |3 - \alpha^2/P^2|$? Certainly this holds whenever $\alpha \le P\sqrt{3}$. It also holds when $\alpha < P\sqrt{6}$ and $n \ge (P\alpha) / \sqrt{6P^2 - \alpha^2}$. These are the cases where all $x_i$ are equal. In all other cases... specifically, $\alpha \ge P\sqrt{6}$, or $\alpha > P\sqrt{3}$ and $n < (P\alpha)/\sqrt{6P^2-\alpha^2}$... the $x_i$ assume two distinct values.

Note that we can express the sum $F(x_1,\cdots,x_n)=\sum (x_i^3 - x_i^2)$ in terms of elementary symmetric polynomials. Specifically,

$$ F=e_1^3-e_1^2+(2-3e_1)e_2+3e_3. $$

From the constraint we know that $e_1=S$. Therefore we just need to minimize

$$ (2-3S)e_2+3e_3. $$

If $S<2/3$, we want $e_2$ and $e_3$ as small as possible. Note that $e_2=e_3=0$ when all but one variable is $0$, that is,

$$ x_i=\begin{cases} S, & i=j,\\ 0, & i\neq j. \end{cases} $$

where $1\leq j\leq n$ can be any integer.

If $S=2/3$, we want $e_3=0$, which means at most two variables are non-zero. These two variables can take any non-negative values that satisfy $x_{j_1}+x_{j_2}=S$.

If $S>2/3$, we have a tradeoff between $e_2$ and $e_3$.

We observe that: $$ x^3 - x^2 + \frac{1}{4}x = x\left(x^2 - x + \frac{1}{4}\right) = x\left(x - \frac{1}{2}\right)^2 \ge 0, $$

thus, for all $x\ge 0$: $$ x^3 - x^2 \ge -\frac{1}{4}x, $$ where equality is reached when $x=0$ or $x=1/2$.

Summing over all $i$: $$ F = \sum (x_i^3 - x_i^2) \ge -\frac{1}{4} \sum x_i = -\frac{S}{4}. $$

When $S$ is a multiple of $1/2$ and $S\le n/2$ we can set $2S$ variables to $1/2$ and the others to $0$.

(The red curve is $f(x) = x^3-x^2+x/4$ and the blue line is its derivative.)

Otherwise, if $S \ge n/2$, assigning $x_i = 1/2$ to all $n$ variables is insufficient, leaving leftover $r = S - n/2 > 0$. The sum $\sum f(x_i)$ is minimized when all variables are equal (“spreading out” $r$ across all variables). The minimal value is then

$$ F = n f(S/n) - \frac{S}{4} = S \left(\frac{1}{2} - \frac{S}{n}\right)^2 - \frac{S}{4}. $$

If $S <n/2$, we can assign $x_i = 1/2$ to as many variables as possible, say $k = \lfloor 2S \rfloor$, and set the rest to zero. The remaining sum $r = S - k/2 \le 1/2$ needs to be distributed across variables. We only need to compare two strategies (I obtained this from the graph; might need to rigorously prove it later):

---

EDIT: This part is wrong. See the other answers for counterexample.

---

1. Distribute $r$ across all variables with value $1/2$ to make them $1/2+r/k$.
2. Put all of $r$ into one variable with value $0$ to make it $r$.

The minimum values are:

$$ F_A = kf(1/2 + r/k) -\frac{S}{4}=r^2\left(\frac{1}{2k}+\frac{r}{k^2}\right) -\frac{S}{4} $$

and

$$ F_B=f(r) -\frac{S}{4}=\frac{r}{4}-r^2+r^3 -\frac{S}{4}. $$

$F_A \le F_B$ iff $r\le r_k$ where

$$ r_k=\frac{k\big(2k-\sqrt{4k+5}+1\big)}{4(k^2-1)}\qquad (k\ge2). $$

For any $a\ge0$, let $D=\{(x,y)\in[0,c]^2: x\le y,\ x+y=a\}$ and $g:D\ni(x,y)\mapsto x^3-x^2+y^3-y^2$. The value of $g$ is then identical to the value of the univariate quadratic function $x\mapsto(3a-2)(x^2-ax) + (a^3-a^2)$. Since the latter function is strictly concave when $a<\frac23$ and convex when $a\ge\frac23$, we see that

1. $g(x,y)$ has a unique global minimum at $(x,y)=(0,a)$ if $a<\frac23$;
2. $g(x,y)$ has a global minimum at $(x,y)=(\frac{a}{2},\frac{a}{2})$ if $a\ge\frac23$.

Now suppose $n\ge2$, $S>0$ and $\mathbf x$ is a global minimum of your $F$. Reindex the $x_i$s so that $x_1\le\cdots\le x_n$. There are two possibilities:

• There exists a maximum index $i_0\ge2$ such that $x_{i-1}+x_i<\frac23$ for every $i\le i_0$. Since the $x_i$s are arranged in ascending order, the sum of any pair of distinct elements in $\{x_1,\ldots,x_{i_0}\}$ is $<\frac23$. Therefore, by (1), at most one element in this set is nonzero and this element must be $x_{i_0}$. Thus $x_1=\cdots=x_{i_0-1}=0$ and by the definition of $i_0$, the sum of any two distinct elements in $\{x_{i_0},\ldots,x_n\}$ is $\ge\frac23$.
• The sum of any pair of distinct elements in $\{x_1,\ldots,x_n\}$ is $\ge\frac23$.

In either case, $\{x_1,\ldots,x_n\}$ can be partitioned into two multisets $X$ and $Y$, where $X$ is either empty or a multiset containing only zero values, and $Y$ is a non-empty multiset in which the sum of any pair of distinct elements is $\ge\frac23$. So, by (2), we can keep modifying the elements of $Y$ by taking pairwise average without changing the objective function value. In the limit, all elements in $Y$ will be identical to $\frac{S}{m}$ where $m=|Y|$. In other words, $F$ always achieves its global minimum at some point of the form $$ \mathbf x=\bigg(\,\underbrace{\frac{S}{m},\ldots,\frac{S}{m}}_{m\text{ terms}},0,\ldots,0\bigg), $$ with $F(\mathbf x)=\frac{S^3}{m^2}-\frac{S^2}{m}$. For an $\mathbf x$ of this form, since the differentiable function $t\mapsto\frac{S^3}{t^2}-\frac{S^2}{t}$ on $(0,\infty)$ is strictly decreasing on $(0,2S)$ and strictly increasing on $(2S,\infty)$, the minimum possible value of $F(\mathbf x)$ can only be achieved when $m$ is the nearest integer in $\{1,\ldots,n\}$ to $2S$ from the left or from the right. So, if we put $$ m_1=\min\{\max\{1,\lfloor 2S\rfloor\},n\} \quad\text{and}\quad m_2=\min\{\max\{1,\lceil 2S\rceil\},n\}, $$ then \begin{align*} \min F(\mathbf x) &= \min\left\{ F\left(\frac{S}{m_1},\ldots,\frac{S}{m_1},0,\ldots,0\right),\ F\left(\frac{S}{m_2},\ldots,\frac{S}{m_2},0,\ldots,0\right) \right\} \\ &=\min\left\{ \frac{S^3}{m_1^2}-\frac{S^2}{m_1},\ \ \frac{S^3}{m_2^2}-\frac{S^2}{m_2} \right\}. \end{align*}

E.g. when $n=3$ and $S=\frac89$, $\min F(\mathbf x)=\min\{F(\frac89,0,0),F(\frac49,\frac49,0)\}=-\frac{160}{729}$, which is approximately $-0.219479$ (to six dec. places).