Return to Revisions

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} = 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 sign of the resulting contribution to $F$, so in fact we can minimize $$ F(\mathbf{x}) = -\frac{2}{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$.