How to minimize l1-norm constrained by "infinity norm" Let $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m $.  I have the following two problems:
P.1.
\begin{equation}
\underset{x\in\mathbb{R}^n}{\text{minimize}} \| Ax-b \|_1 \\
\text{s.t. } \| x \|_{\infty} \leq 1
\end{equation}
P.2.
\begin{equation}
\underset{x\in\mathbb{R}^n}{\text{minimize}} \| x \|_1 \\
\text{s.t. } \| Ax-b \|_{\infty} \leq 1
\end{equation}
How can one reduce each of those problems to a linear program?
 A: This work like this: The $\infty$-norm constraints are straigtforward. In the first  problem you write
$$
-1 \leq x_i \leq 1
$$
or, more explicitely
$$
x_i\leq 1\\-x_i\leq 1.
$$
One could even just write $x\leq 1$ and $-x\leq 1$ with the all-ones vector.
In the second problem you get
$$
Ax\leq 1+b\\
-Ax\leq 1-b.
$$
For the objective you introduce new variables: In the second case use $x^+$ and $x^-$ (which are to positive and the negative part of $x$, i.e. $x=x^+-x^-$) and use the objective
$$
\sum_i x^+_i + x^-_i
$$
and the constraints $x^+\geq 0$, $x^-\geq 0$. In the first case you could introduce $y=Ax-b$ and proceed like in the second case.
I may also suggest that you use the $\ell^1$-Houdini, the homotopy method from "A Primal-Dual Homotopy Algorithm for ℓ1-Minimization with ℓ∞-Constraints" (https://doi.org/10.1007/s10589-018-9983-4, http://www.optimization-online.org/DB_HTML/2016/10/5700.html) from Christoph Brauer to solve the second problem. Code is available at https://github.com/chrbraue/l1Houdini.
(By the way, the title contains the word "Frobenius" but the question does not seem to be about Frobenius norms…)
