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$.
 A: 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.
A: Step 1 : proving concavity of the objective function 
We first prove that$$f(\mathbf{x})=\left\lVert \mathbf{x} \right\rVert_1 - \left\lVert \mathbf{x} -  \overline x \,\mathbf{1}_n\right\rVert_1$$ is concave.
Proof
From the triangle inequality and for $0<\theta<1$ we obtain$$\theta|x_i-\bar x|+(1-\theta)|y_i-\bar y|\ge\left|\theta x_i+(1-\theta)y_i-\Big\{\theta\bar x+(1-\theta)\bar y\Big\}\right|$$
therefore
$$\theta\sum_{i=1}^n|x_i-\bar x|+(1-\theta)\sum_{i=1}^n|y_i-\bar y|\ge \sum _{i=1}^{n}\left|\theta x_i+(1-\theta)y_i-\Big\{\theta\bar x+(1-\theta)\bar y\Big\}\right|$$and by subtracting $\sum_{i=1}^{n}\theta x_i+(1-\theta)y_i$ from both sides we conclude
$$\theta\sum_{i=1}^nx_i-|x_i-\bar x|+(1-\theta)\sum_{i=1}^ny_i-|y_i-\bar y|\\\le \sum _{i=1}^{n}\theta x_i+(1-\theta)y_i-\left|\theta x_i+(1-\theta)y_i-\Big\{\theta\bar x+(1-\theta)\bar y\Big\}\right|$$in a simpler way$$\theta f(x)+(1-\theta)f(y)\le f[\theta x+(1-\theta )y]$$and the proof is complete $\blacksquare$
Step 2 : analyzing optimization
Since the objective function and the feasible region are concave and convex respectively, an optimal solution exists on the boundary of the feasible region, i.e. $x_i\in\{0,1\}$. We assume that exactly $m$ number of $x_i$s are set to $1$ and the rest are $0$. Therefore$$f(\mathbf{x}){=m-m\left(1-{m\over n}\right)-(n-m)\left({m\over n}\right)\\= {m^2\over n}-m+{m^2\over n}\\={2m^2\over n}-m\\={2\over n}\left(m-{n\over 4}\right)^2-{n\over 8}}$$Finally
$$
\begin{cases}
m={n\over 4}&,\quad n=4k
\\m={n- 1\over 4}&,\quad n=4k+1
\\m={n- 2\over 4}&,\quad n=4k+2
\\m={n+1\over 4}&,\quad n=4k+3
\end{cases}
$$
and the optimal value is

$$
\min=\begin{cases}
-{n\over 8}&,\quad n=4k
\\{1\over 8n}-{n\over 8}&,\quad n=4k\pm1
\\{1\over 2n}-{n\over 8}&,\quad n=4k+2
\end{cases}
$$

P.S.
To show why we consider the points with $x_i\in\{0,1\}$, let For example let $\mathbf{\hat x}$ be a vector lying on the boundary of the feasible region with n $\hat x_i$ components. Let all those components be $0$, $1$ or an interior point of $[0,1]$ namely $\epsilon$. Let $\hat x_j$ be the $\epsilon$-value component. Then define$$g(t)=f((\hat x_1,\cdots,\hat x_{j-1},0,\hat x_{j+1},\cdots,\hat x_n)+t\cdot e_j)$$where $e_j$ is a binary vector where only its $j$-th component is $1$. Since $g(t)$ is concave we can write$$\theta g(1)+(1-\theta) g(0)\le g(\theta)$$therefore by choosing $\theta=\epsilon$ we have$$\min\{g(0),g(1)\}\le g(\epsilon)$$or equivalently$$\text{either } g(0)\le g(\epsilon)\text{ or } g(1)\le g(\epsilon)$$which means that if $g(\epsilon)$ is an optimal value then so is either $g(0)$ or $g(1)$. So we can set all non-binary components of $\mathbf{x}$ to $0$ or $1$ and the proof is complete.
A: Let us write 
$$
S(\mathbf{x})
= ||\mathbf{x}-\bar x\mathbf{1}||_1 - ||\mathbf{x}||_1
= \sum_i |x_i-\bar x|-x_i
= \sum_i \left\{\begin{array}{lr}
 -\bar x&\text{if }x_i\ge\bar x\\
 \bar x-2x_i&\text{if }x_i<\bar x
 \end{array}\right.
$$
where $\bar x=\frac1n\sum x_i$, so that the problem is to maximize $S(\mathbf{x})$ for $\mathbf{x}\in[0,1]^n$.
Note that $S(\mathbf{x})$ is piecewise linear within the linear regions bounded by $x_i\in\{0,\bar x, 1\}$, and where the boundaries defined by $x_i=0$, $x_i=\bar x$, and $x_i=1$ are also defined by linear equations. So the maxima of $S(\mathbf{x})$ must lie, not only at the boundaries, but at the corners where the boundaries meet: ie, the maximum must be attained at a point where all $x_i\in\{0,\bar x, 1\}$.
If $p$ of the $x_i$ equal 1, and $q$ of the $x_i$ equal 0, the remaining $n-p-q$ of the $x_i$ must equal $\bar x$. This makes $\bar x=p/(p+q)$ and
$$
S(\mathbf{x}) = (2q-n)\bar x = \frac{p(2q-n)}{p+q}.
$$
If we try to maximize this without being constrained to integer values, we would get $p=n/4$ and $q=3n/4$, but this only works for integer values if $n=4k$.
For the general case, let $r=p+q\le n$, are express $S$ as
$$
S = \frac{p(2r-n-2p)}{r}
= \frac{(2r-n)^2-(4p-2r+n)^2}{8r}
$$
Keeping $r$ fixed and optimising in $p$, we find the maximum at $p_\max=\lfloor\frac{2r-n+2}{4}\rfloor$: ie the real value optimum rounded to the nearest integer. The rouding error leaves $4p_\max-2r+n\in\{-2, -1, 0, 1\}$.
Note that we must have $2r-n>0$ as $2q-n$ is required to get $S>0$: only exceptions to this is $n=1,2$ for which $S_\max=0$.
Expanding $S$ further gives us
$$
2S = r-n+\frac{n^2}{4r}-\frac{(4p_\max-2r+n)^2}{4r}.
$$
If $r$ is increased by 1, $S$ will increase no matter how the right-most error term changes (assuming $n\ge3$), so $r$ should be chosen maximal, leading the $r_\max=n$.
So, the maximum of $S$ is attained when $p+q=n$ and $p=\lfloor\frac{n+2}{4}\rfloor$. Plugging these values into $S$, we get
$$
S_{\max} = \frac{p_\max(n-2p_\max)}{n}\quad\text{where}\quad
p_\max=\left\lfloor\frac{n+2}{4}\right\rfloor.
$$
The original question was the minimum of $-S(\mathbf{x})$, which is then $-S_{\max}$.
