Maximize/Minimize $ \sum_{i=1}^n x_i^3$ subject to $\sum_{i=1}^n x_i = 0$ and $\sum_{i=1}^n x_i^2 =1 $

Question

This question comes from a master thesis's course I followed in Optimization. The problem is the following

---

Maximize/Minimize $ \sum\limits_{i=1}^n x_i^3$ subject to $\sum\limits_{i=1}^n x_i = 0$ and $\sum\limits_{i=1}^n x_i^2 =1 $.

Or, if we prefer \begin{align*} \min/\max f(\pmb x) &= \sum_{i=1}^n x_i^3 \\ \text{s.t.} \quad h_1(\pmb x) &= \sum_{i=1}^n x_i = 0 \\ h_2(\pmb x) &= \sum_{i=1}^n x_i^2 - 1 = 0 \end{align*}

---

My approach

Let $\Omega = \{\pmb x \in \mathbb R^n : h_1(\pmb x) = 0, h_2(\pmb x) = 0 \}$

1. The interesting cases are for $n \ge 3$;
2. $\Omega$ is compact;
3. $\Omega$ is simmetric (i.e. for every $\pmb x \in \Omega$ we have that $-\pmb x \in \Omega$);
4. $f$ is globally odd (i.e. $f(- \pmb x) = -f(\pmb x)$ for every $\pmb x \in \Omega$);
5. If $\pmb x_{\text{max}}$ is a local maximum, then $-\pmb x_{\text{max}} $ is a local minimum; hence we can reduce to the minimization case.

I apply the KKT condition and with a lot of calculus I obtained

$$ f(\pmb x_\text{min}^*)= - \frac{n-2}{\sqrt{n^2-n}} $$

and the minimum is

$$ \pmb x_\text{min}= \left(\frac{1}{\sqrt{n^2-n}},\frac{1}{\sqrt{n^2-n}},\dots,\frac{1}{\sqrt{n^2-n}},- \sqrt{\frac{n-1}{n}} \right) $$ (and, of course, every permutation with this structure).

Assumed my solution is correct, the question is : is there another way to prove this solution with some clever algebraic trick?

Answer 1

With Lagrange multipliers we want to minimize$$L:=\sum_ix_i^3+\lambda\left(1-\sum_ix_i\right)+\mu\left(1-\sum_ix_i^2\right)$$using$$0=\frac{\partial L}{\partial x_i}=3x_i^2-\lambda-2\mu x_i.$$Each solution can only have at most two values for the $x_i$, as they must be roots of $3x^2-2\mu x-\lambda$. A one-value option requires $x_i=0$, contradicting $x_i^2=1$. Instead let $k$ of the $x_i$ be $(n-k)c$ and the other $n-k$ be $-kc$, so$$1=k(n-k)^2c^2+(n-k)^2k^2c=nk(n-k)c^2\implies c=\pm\frac{1}{\sqrt{nk(n-k)}},$$obtaining$$\sum_ix_i^3=k(n-k)^3c^3-(n-k)k^3c^3=\pm\frac{n-2k}{\sqrt{nk(n-k)}}.$$This is easiest to extremize with$$\frac{n-2k}{\sqrt{nk(n-k)}}=\sqrt{\frac{n-k}{k}}-\sqrt{\frac{k}{n-k}}.$$As you found, the minimum is$$k=n-1,\,c=\frac{1}{\sqrt{n(n-1)}},\,\sum_ix_i^3=\frac{2-n}{\sqrt{n(n-1)}}.$$By contrast, the maximum is$$k=1,\,c=\frac{1}{\sqrt{n(n-1)}},\,\sum_ix_i^3=\frac{n-2}{\sqrt{n(n-1)}}.$$This is an important sanity check: $x_i\mapsto-x_i$ preserves the problem, so the extrema should be of the form $\pm M$.

Answer 2

Here are solutions without Lagrange multipliers.

Let's start with a solution for the maximum:

Notice that $\displaystyle\sum_{i=1}^n x_i=0$ implies that $$x_m^2=\bigg(\sum_{\substack{i=1\\ i\not=m}}^n x_i\bigg)^2\leq (n-1)\sum_{\substack{i=1\\ i\not=m}}^n x_k^2=(n-1)(1-x_m^2)$$ using Chebyshev's sum inequality and $\displaystyle\sum_{i=1}^n x_i^2=1$. Hence we obtain $nx_m^2\leq n-1\Leftrightarrow |x_m|\leq \sqrt{\tfrac{n-1}{n}}$. Hence we have, using $\sum_{i=1}^n x_i=0$ : \begin{align*}\begin{split}&\sum_{i=1}^n (x_i-\sqrt{\tfrac{n-1}{n}})(x_i+\sqrt{\tfrac{1}{n(n-1)}})^2\leq0\\ \Leftrightarrow \sum_{i=1}^n x_i^3 &\leq (n-3)\sqrt{\tfrac{1}{n(n-1)}}\sum_{i=1}^n x_i^2+\sum_{i=1}^n \sqrt{\tfrac{1}{n^3(n-1)}}\\ &= (n-2)\sqrt{\tfrac{1}{n(n-1)}}\end{split}\end{align*} This is the required result if it can be shown that it is tight, which of course is the case since equality holds for $x_1 = x_2 = \cdots = x_{n-1} = - \sqrt{\tfrac{1}{n(n-1)}}$ and $x_{n} = \sqrt{\tfrac{n-1}{n}}$ or any permutation thereof.

The solution for the minimum follows the same idea, with changed signs:

Again, using $\sum_{i=1}^n x_i=0$, we write : \begin{align*}\begin{split}&\sum_{i=1}^n (x_i+\sqrt{\tfrac{n-1}{n}})(x_i-\sqrt{\tfrac{1}{n(n-1)}})^2\geq0\\ \Leftrightarrow \sum_{i=1}^n x_i^3 &\geq -(n-3)\sqrt{\tfrac{1}{n(n-1)}}\sum_{i=1}^n x_i^2-\sum_{i=1}^n \sqrt{\tfrac{1}{n^3(n-1)}}\\ &= -(n-2)\sqrt{\tfrac{1}{n(n-1)}}\end{split}\end{align*} Again, this is the required result if it can be shown that it is tight, which is the case since equality holds for $x_1 = x_2 = \cdots = x_{n-1} = \sqrt{\tfrac{1}{n(n-1)}}$ and $x_{n} = - \sqrt{\tfrac{n-1}{n}}$ or any permutation thereof.