# Howto solve $\min |x_1| + |x_2|$ with linear programming?

Consider this optimization problem:
$$\begin{matrix}\min & |x_1| + |x_2| && \\ s.t & a_{11}x_1 + a_{12}x_2 & = b_1 \\ & a_{21}x_1 + a_{22}x_2 & = b_2 \end{matrix}$$ Which $a_{ij}$ and $b_j$ are constant and fixed real number and $x_i\in\mathbb{R}$. Can i solve this problem with linear programming methods? If i can, how?

• This system does not have a guaranteed solution, is that ok? – user130512 Feb 26 '14 at 16:07
• yes, for example if $a_{11}=a_{21}$ and $a_{12}=a_{22}$ but $b_1 \neq b_2$. – Stefano Feb 26 '14 at 17:18
• math.stackexchange.com/questions/432003/… – Opt Dec 17 '17 at 13:29

## 2 Answers

You can! Set $x_1=x_1^+ - x_1^-$ where $x_1^+ \geq 0$ and $x_1^- \geq 0$ then $|x_1|=x_1^+ + x_1^-$. Same for $x_2$.

This works since it is a minimization problem.

• To be more clear: every real number can be written as a difference. If $x_1$ is negative the problem is going to set $x_1^-=x_1$ and $x_1^+=0$ since it wants to minimize their sum. – Stefano Feb 26 '14 at 16:16

You can divide the problem up in four parts. One part is minimizing $x_1 + x_2$ subject to your constraints and $x_1, x_2 \geq 0$.

Another part would be minimizing $-x_1 + x_2$ subject to your constraints and $x_1 \leq 0$, $x_2 \geq 0$, and so on. One part for each quadrant.

Each part can be solved by linear programming methods, and the lowest minimum of all is the minimum of the original problem.