 # Consider a minimization problem: <mtable columnalign="right left right left right left right Hector Petersen 2022-06-22 Answered
Consider a minimization problem:
$\begin{array}{rl}& min\sum _{i=1}^{n}|{x}_{i}|,\\ & Ax=b,\end{array}$
where $A$ is an $m×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!
You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it alisonhleel3
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

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}\left({x}_{i}^{+}+{x}_{i}^{-}\right)$ subject to $A\left({x}^{+}-{x}^{-}\right)=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 $\left(2n-m\right)-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.)