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$.
Best Answer
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.