<s>[INST] Minimize $\left\lVert \mathbf{x} \right\rVert_1 - \left\lVert \mathbf{x} - \overline x \,\mathbf{1}_n\right\rVert_1$ over the unit $n$-cube I want to solve the following minimization problem
$$\min_{\mathbf{x} \in [0, 1]^n} \left\lVert \mathbf{x} \right\rVert_1 - \left\lVert \mathbf{x} -  \overline x \,\mathbf{1}_n\right\rVert_1$$
where $\mathbf{x} = (x_1,x_2,\dots,x_n)$ and 
$$\overline x := \frac{1}{n} \sum_{i=1}^{n} x_i = \frac{1}{n} \mathbf{1}_n^\top \mathbf{x}$$
I can prove $- \left\lVert \mathbf{x} -  \overline x \,\mathbf{1}_n\right\rVert_1$, subject to $x_i \in [0, 1]$, takes the minimum value when half $x_i=0$ and the other half $x_i=1$. However, I have no idea how to find the minimum after adding the $1$-norm $\left\lVert \mathbf{x}\right\rVert_1$.
 [/INST] We need to minimize the following expression
$$
S = \sum_{i=1}^n (x_i - |x_i - \overline{x}|)
$$
where $x_i \in [0,1]$.
We can rewrite it as
$$
S = \sum_{i\in I_{>}} (x_i - (x_i - \overline{x})) + \sum_{i \in I_{<}} (x_i - (\overline{x} - x_i)).
$$
Here
$$
I_{>} = \{i\in \{1,2,\ldots n\}: x_i \ge \overline{x} \},
$$
$$
I_{<} = \{i\in \{1,2,\ldots n\}: x_i < \overline{x} \}.
$$
Hence
$$
S = \overline{x} (|I_{>}| - |I_{<}|) + 2 \sum_{i\in I_{<}} x_i,
$$
where $|A|$ is a number of elements in the set $A$.
Our goal is to make this expression as small as possible. Let $|I_{>}| =k$. Then $|I_{<}| = n-k$ and
$$
S = \overline{x} (2k - n) + 2 \sum_{i \in I_{<}} x_i.
$$
First of all, $2k -n$ must be negative in order for $S$ to have the smallest value. It's also easy to see that we should take all $k$ values of $x_i$ for $i$ from $I_{>}$ to be equal to $1$, since in that case $\overline{x}$ will be bigger and $\overline{x}(2k-n)$ will be smaller.
So,
$$
S = \frac{k+ \sum_{i \in I_{<}}x_i}{n} (2k-n) + 2 \sum_{i \in I_{<}} x_i = \frac{k(2k-n)}{n} + \sum_{i \in I_{<}} x_i \bigg(\frac{2k}{n} + 1\bigg).
$$
The previous expression have the smallest value when all $x_i = 0$ for $i \in I_{<}$.
Hence,
$$
\min S = \min_{1 \le k \le (n-1)} \Big\{\frac{k(2k-n)}{n} \Big\} = \min_{1 \le k \le (n-1)} \Big\{ \frac{2k^2}{n} -k \Big\}.
$$
Next consider a function
$$
f(x) = \frac{2x^2}{n} - x
$$
and determine it's minimum using calculus:
$$
f^{'}(x) = \frac{4x}{n} - 1 = 0 \implies x = \frac{n}{4}.
$$
So, for $n = 4l$ we get $k = l$ and the answer is
$$
\frac{2l^2}{n} - l = -\frac{n}{8}.
$$
For other values of $n$ the answer will be either $\lceil n/4 \rceil$ or $\lfloor n/4 \rfloor$.
Let's consider other values of $n$.
Case $n = 4l+1$. Then $\lfloor n/4 \rfloor = l$ and $\lceil n/4 \rceil = l +1$
$$
\frac{2l^2}{4l+1} - l = -\frac{2l^2+l}{4l+1}
$$
$$
\frac{2(l + 1)^2}{4l+1} - (l+1) = -\frac{2l^2+l - 1}{4l+1}
$$
This shows that in this case $k = \lfloor n/4 \rfloor$ gives the right answer.
Case $n = 4l+2$.
$$
\frac{2l^2}{4l+2} - l = -\frac{2l^2+2l}{4l+2}
$$
$$
\frac{2(l + 1)^2}{4l+2} - (l+1) = -\frac{2l^2+2l}{4l+2}
$$
This shows that in this case $k = \lfloor n/4 \rfloor$ and $k =\lceil n/4 \rceil$ both give the right answer.
Finally case $n = 4l+3$.
$$
\frac{2l^2}{4l+3} - l = -\frac{2l^2+3l}{4l+3}
$$
$$
\frac{2(l + 1)^2}{4l+3} - (l+1) = -\frac{2l^2+3l+1}{4l+3}
$$
This shows that in this case $k =\lceil n/4 \rceil$ gives the right answer.
</s>