Minimize sum of absolute value with linear constraint

Question

Consider a minimization problem: $$ \begin{aligned} & \min \sum_{i=1}^n |x_i|,\\ & A x = b, \end{aligned} $$ where $A$ is an $m\times n$ matrix of rank $m$. I know that the minimum points contains one where at least $n-m$ components of $x$ is zero and I have proved this conclusion. My problem is that, I think this should be a developed proposition but I am not familiar with optimization theory, so I don't know where to find a reference. Could anybody help me find a reference like a book or article? Thanks!

Answer 1

One standard linearization of absolute value is to introduce a new variable $y_i$ to represent $|x_i|$, and the resulting linear programming (LP) problem is to minimize $\sum_{i=1}^n y_i$ subject to \begin{align} Ax &= b \\ y_i &\ge x_i &&\text{for all $i$}\\ y_i &\ge -x_i &&\text{for all $i$} \end{align} This LP has $2n$ variables and $m+2n$ constraints. A standard result from LP theory is that there exists an optimal solution with at most $m+2n$ nonzero values.

A different standard linearization of absolute value is to introduce two new nonnegative variables $x_i^+$ and $x_i^-$ to represent $|x_i|$, and the resulting LP is to minimize $\sum_{i=1}^n (x_i^+ + x_i^-)$ subject to $A(x^+ - x^-) = b$. This LP has $2n$ variables and $m$ constraints. A standard result from LP theory is that there exists an optimal solution with at most $m$ nonzero values, hence at least $2n-m$ zero values, hence at least $(2n-m)-n=n-m$ zero values among the original $x_i$ variables. (Note that $x_i^+ x_i^- = 0$ at optimality because otherwise we can improve the objective value and preserve feasibility by decreasing both $x_i^+$ and $x_i^-$ by the same amount, but this observation is not required to obtain the desired result.)

Answer 2

Here is an relevant result. I have seen similar constructions in many LP related proofs (mostly showing equivalence of basic feasible solutions and extreme points), but never as an explicit result.

Suppose $S$ is a linear subspace of dimension $l$ and $x^* \in \mathbb{R}^n$ has $p<l$ zeros. Then there is some $h^* \in S$ such that $\|x^*+h^*\|_1 \le \|x^*\|_1$ and $x^*+h^*$ has at least $p+1$ zeros.

Let $T= \operatorname{sp} \{ e_k \}_{x^*_k \neq 0}$, that is the subspace spanned by the unit vectors corresponding to the non zero elements of $x^*$. Note that $\dim T = n-p > n-l$. Note that $x^* \in T$ and that $\dim S \cap T \ge 1$.

For any non zero $h \in T$, let $T = \inf \{ -{x_k \over h_k} | h_k \neq 0, {x_k \over h_k} = {|x_k| \over (\operatorname{sgn} x^*_K)h_k} <0 \}$. $T$ may be infinite, but $0 < T$.

If $0 \le t \le T$, then $\|x^*+th\|_1 = \sum_k (\operatorname{sgn} x^*_k)(x^*_k+th_k) = \|x\|_1+t \sum_k (\operatorname{sgn} x^*_k) h_k$.

Let $d=(\operatorname{sgn} x^*_1, \cdots, \operatorname{sgn} x^*_n)$ and note that as long as $h \in T$, $h \neq 0$, $d^T h \le 0$ and $t \in [0,T]$ then $\|x^*+th\|_1 \le \|x^*\|_1$. Furthermore, in this case we must have $T<\infty$ and at least one component of $x^*+Th$ is zero.

Finally, since $S \cap T$ must have a non trivial intersection with the closed halfspace $H=\{ h | d^T h \le 0 \}$, we can find some non zero $h \in S \cap T \cap H$, and letting $h^* = Th$ as above, we see that $\|x^*+h^*\|_1 \le \|x^*\|_1$ and $x^*+h^*$ has at least $p+1$ zeros.

In particular, if $S$ is a linear subspace of dimension $l$ and $x^* \in \mathbb{R}^n$ then there is some $h^* \in S$ such that $\|x^*+h^*\|_1 \le \|x^*\|_1$ and $x^*+h^*$ has at least $l$ zeros.

Finally, suppose $x^*$ is a solution to the problem in the question. Note that with $S= \ker A$, we have $l = \dim S = n-m$. Hence there is some $h^* \in S$ such that $x^*+h^*$ has at least $l=n-m$ zeros and $\|x^*+h^*\|_1 \le \|x^*\|_1$. Since $x^*+h^*$ is feasible and $x^*$ is a solution, we must have $\|x^*+h^*\|_1 = \|x^*\|_1$.