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

Question

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

Answer 1

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.

Answer 2

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}$.

Answer 3

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.