# Converting a first norm into a linear program

I want to convert the following problem into a linear program. $$\min_{x \in \mathbb{R}^n} \qquad \lvert\lvert Ax - b \rvert\rvert_1$$

Here $$A \in \mathbb{R}^{m\times n}$$, $$x \in \mathbb{R}^n$$ and $$b \in \mathbb{R}^m$$

This was my train of thought so far:

By definition, the first norm is,

$$\lvert \lvert y\rvert \rvert_1 = \lvert y_1\rvert + \lvert y_2 \rvert + ...+ \lvert y_n\rvert$$ Now I know that an absolute value can be represented by replacing the variable with two non-negative variables. But I know it only for a single variable: $$\lvert x \rvert = x^+ - x^-$$ I have no idea how to do this when the expression is in the format $$\lvert a_i^Tx - b_i\rvert$$ where $$a_i^T$$ is a row of the matrix $$A$$. (Yes I am dumb, I know it).

The best I could think of is adding a constraint $$y = Ax -b$$ and using $$y$$ as my variable:

\begin{align} \min_{y_i^+, y_i^- \in \mathbb{R}} \quad & y_1^+ + y_1^- + y_2^+ + y_2^- + y_3^+ + y_3^-+ \dots + y_m^+ + y_m^-\\ s.t. \quad & a_1^Tx - b_1 = y_1^+ - y_1^- \\ & a_2^Tx - b_2 = y_2^+ - y_2^- \\ & a_3^Tx - b_3 = y_3^+ - y_3^- \\ \vdots & a_m^Tx - b_m = y_m^+ - y_m^- \end{align}

This is all I can think. Is this the right way to go? Is there anything missing? Or is this entirely wrong? Any help would be appreciated.

Seems fine. Don't forget to include the nonnegative constraints for your $$y_i^+$$ and $$y_i^-$$.

Alternatively

$$\min \sum_{i=m}^n z_i$$

$$z_i \ge a_i^Tx-b_i$$

$$z_i \ge -(a_i^Tx-b_i)$$

$$\forall i \in \{1, \ldots, m\}$$.

• Thank you very much! – PPGoodMan Dec 4 '18 at 14:28