Maximizing the Sum of Cubes

Question

I have ten variables, $x_1$ through $x_{10}$. $-1 \leq x_i \leq 1$, and $\sum x_i = 0$. What is the maximum of $\sum x_i^3$? I've tried to use Lagrange multipliers, but writing the restricted domain as a constraint seems, if not impossible, then very difficult.

Answer 1

We need the following

Lemma. The maximal configuration has $k\geq0$ of the $x_i$ equal to $-s$ for some $s>0$ and the remaining $10-k$ of the $x_i$ equal to $1$.

This lemma enforces $ks=10-k$, or $s={10-k\over k}$. The condition $s\leq1$ implies $k\geq5$. We then have to maximize $$f(k):=-k s^3+(10-k)=-{(10-k)^3\over k^2}+10-k\qquad(5\leq k\leq 10)\ .$$ The maximal obtainable value is $f(7)={120\over49}>0$.

Proof of the lemma: As $f(7)>0$ the choice $x_i=0$ for all $i$ is not optimal. The optimal solution therefore will contain negative $x_i$, maybe zero $x_i$, and positive $x_i$.

Let $(x_i)_{1\leq i\leq 10}$ be an admissible configuration. If there is an $x_i$ with $0<x_i<1$ find an $x_j<0$, and write $x_j=m-h$, $x_i=m+h$ with $h>0$. We then have $$x_j^3+x_i^3=2m^3+6mh^2\ .$$ If $m>0$ we can increase $h$ and then replace $x_i$ with $x_i'=1$, whereby $x_j$ decreases at the same time to an $x_j'>-1$, and $\sum_{i=1}^{10}x_i^3$ has increased. If $m\leq0$ then we may choose $h=0$ and obtain a larger (or equal) sum $\sum_{i=1}^{10}x_i^3$. Doing this for every $x_i\in\>]0,1[\>$ we obtain a configuration with a larger $\sum_{i=1}^{10}x_i^3$, but all $x_i\leq0$ or $=1$. Since the function $t\mapsto t^3$ is concave when $t\leq0$ we can finally collect the $k$ entries $x_i\leq 0$ into a single $-s<0$, which is assumed $k$ times, and thereby increase $\sum_i x_i^3$ again. Now we are in the situation described in the claim of the lemma.

Answer 2

You can write it in a standard form \begin{equation}\notag \begin{split} \min & -\sum_{i=1}^{10} x_i^3 \\ \mathrm{s.t.} \hspace{1ex}& x_i - 1 \leq 0 \\ & -1 -x_i \leq 0 \hspace{1ex} \forall i \in [1, 10]\\ & \sum_{i=1}^{10} x_i = 0 \\ \end{split} \end{equation}

Then the Lagrange Dual will be \begin{equation} L(x,\lambda, \mu)=-\sum_{i=1}^{10} x_i^3+\sum_{i=1}^{10} \lambda_i (x_i-1) - \sum_{i=1}^{10} \mu_i (x_i+1) + \gamma \sum_{i=1}^{10} x_i \hspace{2ex} \lambda_i, \mu_i \geq 0 \end{equation}